数据结构 二叉树的删除 （带图详解_设计一个算法,删除一颗二叉树t

第二个例子没选好…将就用5.5凑合一下把

#include<iostream>
using namespace std;

typedef struct ElemType {
	int key;
}ElemType;

typedef struct BSTNode {
	ElemType data;
	BSTNode* lchild, * rchild;
}BSTNode, * BSTree;

void DeleteBST(BSTree& T, char key) {
	BSTree p = T; BSTree f = NULL;
	BSTree q;
	BSTree s;
	while (p) {
		//找到p的位子
		if (p->data.key == key) break;
		f = p;//f标记p的父节点
		if (p->data.key > key)  p = p->lchild;
		else p = p->rchild;
	}
	if (!p)return;//如果被删除的节点不存在则return
	if (p->lchild && p->rchild) {
		//如果被删除的节点同时有左子树和右子树
		//可以用左子树中的最大值或右子树中的最小值进行替换
		//这里选择用第一种方法
		q = p;
		s = p->lchild;
		while (s->rchild) {
			q = s;
			s = s->rchild;
		}//这里要注意的就是这样移动之后s一定不会存在右子树
		p->data = s->data;//用s的值将p进行替换
		if (q != p) {
			q->rchild = s->lchild;
		}
		else {
			//如果q==p 说明在上面q没有进行移动
			//说明s不存在右子树 即s是最大值
			q->lchild = s->lchild;
		}	
		delete s;
	}
	else {
		if (p->rchild) {
			//如果只有右子树
			q = p;
			p = p->rchild;
		}
		else if (p->lchild) {
			//如果只有左子树
			q = p;
			p = p->lchild;//直接用p的左子树进行连接
		}
		if (!f) {
			//如果待删除的节点没有父节点 说明为根节点
			T = p;//又因为p只有左孩子/右孩子 p在上述代码中进行了移动 那么就是整个树直接从下一个位置开始
		}
		else if (q == f->lchild) {
			//如果待删除节点在父节点的左子树中
			//直接改变父节点的左子树指向
			f->lchild = p;
		}
		else {
			f->rchild = p;
		}
		delete q;
	}
}

int main() {

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75