一、二叉排序树（二叉查找树）的概念
（1）若左子树非空，则左子树上所有结点的值均小于根节点的值
（2）若右子树非空，则右子树上所有结点的值均大于根节点的值
（3）左右子树分别也是一棵二叉排序树
tip：可以是一棵空树
二、二叉排序树的判别
（1）因为二叉排序树的中序遍历是一个有序递增序列，可以对已经建立的二叉树进行中序遍历，如果满足则判断是
三、二叉排序树的创建（creat、insert）
树结点的结构体：
struct tree{
int data;
struct tree* lchild;
struct tree* rchild;
};
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21//递归创建结点 void Creat(int a,tree* &T){ if(T==NULL){ T=new tree; T->data=a; T->lchild=NULL; T->rchild=NULL; } else if(a>T->data){ Creat(a,T->rchild); } else{ Creat(a,T->lchild); } } //传入数组，一次性插入 void Insert(tree* &T,int A[],int len){ for(int i=0;i<=len;i++){ Creat(A[i],T); } }
四、二叉排序树的插入
复制代码
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//查找指定结点(输出当前结点是否存在)，如果没有就插入 void find(tree* &T,int a){ tree* K=T; //T指针指向二叉排序树的根节点，K为工作指针 tree* pre; //pre指向当前工作指针的上一个结点，用于插入确定插入位置 while(K!=NULL&&a!=K->data){ if(a>K->data){ pre=K; K=K->rchild; }else{ pre=K; K=K->lchild; } } if(K==NULL){ tree* P; //工作指针 P=new tree; P->data=a; if(P->data>pre->data){ pre->rchild=P; P->lchild=NULL; P->rchild=NULL; } else{ pre->lchild=P; P->lchild=NULL; P->rchild=NULL; } cout<<"不存在，已插入 "<<a<<" 这个结点"<<endl; }else{ cout<<"存在"<<endl; } }
五、二插排序树的删除
复制代码
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//删除某一结点，若不存在则提示 //①当该结点是叶子结点时，直接删除 //②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置 //③当左右孩子都存在时找中序遍历的下一个(或上一个)结点代替其位置 void delect(tree* &T,int a){ //首先找到要删除的结点 tree* Pre; tree* P=T; //定义工作指针 while(P!=NULL&&a!=P->data){ //这两个判定条件不能颠倒 if(a>P->data){ Pre=P; P=P->rchild; }else{ Pre=P; P=P->lchild; } } if(P==NULL){ cout<<"要删除的结点不存在"<<endl; }else{ // ①当该结点是叶子结点时，直接删除 if(P->lchild==NULL&&P->rchild==NULL){ if(P->data>Pre->data){ Pre->rchild=NULL; }else{ Pre->lchild=NULL; } cout<<"已删除 "<<a<<endl; } //②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置 if((P->lchild!=NULL&&P->rchild==NULL)||(P->rchild!=NULL&&P->lchild==NULL)){ if(P->data>Pre->data){ if(P->lchild!=NULL){ Pre->rchild=P->lchild; }else{ Pre->rchild=P->rchild; } } if(P->data<Pre->data){ if(P->lchild!=NULL){ Pre->lchild=P->lchild; }else{ Pre->lchild=P->rchild; } } cout<<"已删除 "<<a<<endl; } //③当左右孩子都存在时找中序遍历的下一个（或上一个结点）结点代替其位置 (讨巧一点用前驱的最后一个结点) if(P->lchild!=NULL&&P->rchild!=NULL){ tree* q; tree* s; q=P; s=P->lchild; while(s->rchild) //在结点p的左子树中继续查找其前驱结点,即最右下结点 { q=s; s=s->rchild; //向右到尽头 } P->data=s->data; //结点s中的数据顶替被删结点p中的 if(q!=P) //重新连接结点q的右子树 q->rchild=s->lchild; else //重新连接结点q的左子树 q->lchild=s->lchild; delete(s); //释放s } cout<<"已删除 "<<a<<endl; } }
六、完整代码（可以运行）
复制代码
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147#include<iostream> using namespace std; struct tree{ int data; struct tree* lchild; struct tree* rchild; }; //建立创建，传入一个完整的数组 void Creat(int a,tree* &T){ if(T==NULL){ T=new tree; T->data=a; T->lchild=NULL; T->rchild=NULL; } else if(a>T->data){ Creat(a,T->rchild); } else{ Creat(a,T->lchild); } } //传入数组，一次性插入 void Insert(tree* &T,int A[],int len){ for(int i=0;i<=len;i++){ Creat(A[i],T); } } //中序遍历 void midorder(tree* T){ if(T!=NULL){ midorder(T->lchild); cout<<T->data<<" "; midorder(T->rchild); } } //查找指定结点(输出当前结点是否存在)，如果没有就插入 void find(tree* &T,int a){ tree* K=T; //T指针指向二叉排序树的根节点，K为工作指针 tree* pre; //pre指向当前工作指针的上一个结点，用于插入确定插入位置 while(K!=NULL&&a!=K->data){ if(a>K->data){ pre=K; K=K->rchild; }else{ pre=K; K=K->lchild; } } if(K==NULL){ tree* P; //工作指针 P=new tree; P->data=a; if(P->data>pre->data){ pre->rchild=P; P->lchild=NULL; P->rchild=NULL; } else{ pre->lchild=P; P->lchild=NULL; P->rchild=NULL; } cout<<"不存在，已插入 "<<a<<" 这个结点"<<endl; }else{ cout<<"存在"<<endl; } } //删除某一结点，若不存在则提示 //①当该结点是叶子结点时，直接删除 //②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置 //③当左右孩子都存在时找中序遍历的下一个(或上一个)结点代替其位置 void delect(tree* &T,int a){ //首先找到要删除的结点 tree* Pre; tree* P=T; //定义工作指针 while(P!=NULL&&a!=P->data){ //这两个判定条件不能颠倒 if(a>P->data){ Pre=P; P=P->rchild; }else{ Pre=P; P=P->lchild; } } if(P==NULL){ cout<<"要删除的结点不存在"<<endl; }else{ // ①当该结点是叶子结点时，直接删除 if(P->lchild==NULL&&P->rchild==NULL){ if(P->data>Pre->data){ Pre->rchild=NULL; }else{ Pre->lchild=NULL; } cout<<"已删除 "<<a<<endl; } //②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置 if((P->lchild!=NULL&&P->rchild==NULL)||(P->rchild!=NULL&&P->lchild==NULL)){ if(P->data>Pre->data){ if(P->lchild!=NULL){ Pre->rchild=P->lchild; }else{ Pre->rchild=P->rchild; } } if(P->data<Pre->data){ if(P->lchild!=NULL){ Pre->lchild=P->lchild; }else{ Pre->lchild=P->rchild; } } cout<<"已删除 "<<a<<endl; } //③当左右孩子都存在时找中序遍历的下一个（或上一个结点）结点代替其位置 (讨巧一点用前驱的最后一个结点) if(P->lchild!=NULL&&P->rchild!=NULL){ tree* q; tree* s; q=P; s=P->lchild; while(s->rchild) //在结点p的左子树中继续查找其前驱结点,即最右下结点 { q=s; s=s->rchild; //向右到尽头 } P->data=s->data; //结点s中的数据顶替被删结点p中的 if(q!=P) //重新连接结点q的右子树 q->rchild=s->lchild; else //重新连接结点q的左子树 q->lchild=s->lchild; delete(s); //释放s } cout<<"已删除 "<<a<<endl; } } int main(){ tree* T=NULL; int A[]={23,89,65,12,17,3,9,90,21,63,71}; Insert(T,A,10); midorder(T); delect(T,89); midorder(T); find(T,89); midorder(T); return 0; }
总结
本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注靠谱客的更多内容！
最后
以上就是快乐草丛最近收集整理的关于C语言二叉排序树的创建,插入和删除的全部内容，更多相关C语言二叉排序树内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复