二叉排序樹的插入與刪除，二叉排序樹
一、二叉排序樹的插入
首先檢查要插入的數據是否已存在，若存在則不插入，若不存在，則把元素插入到在二叉樹上查找失敗時的結點的左孩子和右孩子上。需要考慮的特殊情況是插入第一個元素前，二叉樹為空。
1 bool insert(BiTreeNode *&root,DataType *item) {
2 BiTreeNode *current = NULL,*parent = NULL,*p = NULL;
3 current = root;
4 while(current != NULL) {
5 if(current->data.key == item->key)return false;
6 parent = current;
7 if(current->data.key < item->key)
8 current = current->rightChild;
9 else
10 current = current->leftChild;
11 }
12 p = new BiTreeNode;
13 p->data = *item;
14
15 //the new node is root node
16 if(parent == NULL)
17 root = p;
18 //as leftChild
19 else if(item->key < parent->data.key)
20 parent->leftChild = p;
21 //as rightChild
22 else
23 parent->rightChild = p;
24 return true;
25 }
二、二叉排序樹的刪除
刪除操作的要求是：首先檢查要刪除的元素是否存在，若不存在，直接返回若存在，理論上需要考慮2*4種情況。
a、要刪除的節點為根節點。
b、要刪除的節點不為根節點。
1、該節點無孩子節點。
sln1:直接刪除該節點。
2、該節點只有左孩子節點。
sln2:被刪除節點的父節點指向該節點的左孩子節點，被刪除節點是其父節點的左節點還是右節點，亦或是根節點，則需要判斷。
3、該節點只有右孩子節點。
sln3:類似sln2。
4、該節點有左、右孩子節點。
sln4:首先：尋找數據元素關鍵字大於要刪除節點關鍵字的最小值，即要刪除節點右子樹的最左子樹，例如為Kdata。
然後：把Kdata的數據賦給要刪除的元素。
最後：以要刪除元素的右子樹為根節點，以Kdata為要刪除的數據，遞歸調用刪除算法。
1 bool deleteNode(BiTreeNode *&root,DataType item) {
2 BiTreeNode *current = root,*parent = NULL,*p = NULL,*kmin = NULL;
3 bool flag = false;
4 //尋找要刪除的節點和其父節點
5 while(current != NULL) {
6 if(current->data.key == item.key) {
7 flag = true;
8 break;
9 }
10 parent = current;
11 if(current->data.key < item.key)
12 current = current->rightChild;
13 else current = current->leftChild;
14 }
15 //未找到要刪除的元素
16 if(flag == false) {
17 cout<<"delete error:item not found"<<endl;
18 return false;
19 }
20 if(current->leftChild == NULL) {
21 p = current;
22 if(parent != NULL) {
23 if(parent->leftChild != NULL && parent->leftChild->data.key == current->data.key)
24 parent->leftChild = current->rightChild;
25 else parent->rightChild = current->rightChild;
26 } else {
27 root = current->rightChild;
28 }
29 delete p;
30 } else if(current->rightChild == NULL) {
31 p = current;
32 if(parent != NULL) {
33 if(parent->leftChild != NULL && parent->leftChild->data.key == current->data.key)
34 parent->leftChild = current->leftChild;
35 else parent->rightChild = current->leftChild;
36 } else {
37 root = current->leftChild;
38 }
39 delete p;
40 } else {
41 kmin = current->rightChild;
42 while(kmin->leftChild != NULL) {
43 kmin = kmin->leftChild;
44 }
45 if(parent != NULL)
46 current->data = kmin->data;
47 else
48 root->data = kmin->data;
49 deleteNode(current->rightChild,kmin->data);
50 }
51 return true;
52 }
完整測試代碼：
![]()
1 #include <iostream>
2 #include <stdlib.h>
3 #include <stdio.h>
4
5 using namespace std;
6
7 struct DataType {
8 int key;
9 };
10
11 typedef struct node {
12 DataType data;
13 struct node *leftChild;
14 struct node *rightChild;
15 node() {
16 leftChild = NULL;
17 rightChild = NULL;
18 }
19 } BiTreeNode;
20
21 BiTreeNode *search(BiTreeNode *root,DataType item) {
22 BiTreeNode *p = NULL;
23 if(root!=NULL) {
24 p = root;
25 while(p!=NULL) {
26 if(p->data.key == item.key)
27 return p;
28 if(item.key > p->data.key)
29 p = p->rightChild;
30 else
31 p = p->leftChild;
32 }
33 }
34 return NULL;
35 }
36
37 bool insert(BiTreeNode *&root,DataType *item) {
38 BiTreeNode *current = NULL,*parent = NULL,*p = NULL;
39 current = root;
40 while(current != NULL) {
41 if(current->data.key == item->key)return false;
42 parent = current;
43 if(current->data.key < item->key)
44 current = current->rightChild;
45 else
46 current = current->leftChild;
47 }
48 p = new BiTreeNode;
49 p->data = *item;
50
51 //the new node is root node
52 if(parent == NULL)
53 root = p;
54 //as leftChild
55 else if(item->key < parent->data.key)
56 parent->leftChild = p;
57 //as rightChild
58 else
59 parent->rightChild = p;
60 return true;
61 }
62
63 void inTraverse(BiTreeNode *root) {
64 if(root == NULL) {
65 cout<<"inTraverse error:root = NULL"<<endl;
66 return;
67 }
68 if(root->leftChild != NULL)
69 inTraverse(root->leftChild);
70 cout<<root->data.key<<" ";
71 if(root->rightChild != NULL)
72 inTraverse(root->rightChild);
73 }
74
75 bool deleteNode(BiTreeNode *&root,DataType item) {
76 BiTreeNode *current = root,*parent = NULL,*p = NULL,*kmin = NULL;
77 bool flag = false;
78 //尋找要刪除的節點和其父節點
79 while(current != NULL) {
80 if(current->data.key == item.key) {
81 flag = true;
82 break;
83 }
84 parent = current;
85 if(current->data.key < item.key)
86 current = current->rightChild;
87 else current = current->leftChild;
88 }
89 //未找到要刪除的元素
90 if(flag == false) {
91 cout<<"delete error:item not found"<<endl;
92 return false;
93 }
94 if(current->leftChild == NULL) {
95 p = current;
96 if(parent != NULL) {
97 if(parent->leftChild != NULL && parent->leftChild->data.key == current->data.key)
98 parent->leftChild = current->rightChild;
99 else parent->rightChild = current->rightChild;
100 } else {
101 root = current->rightChild;
102 }
103 delete p;
104 } else if(current->rightChild == NULL) {
105 p = current;
106 if(parent != NULL) {
107 if(parent->leftChild != NULL && parent->leftChild->data.key == current->data.key)
108 parent->leftChild = current->leftChild;
109 else parent->rightChild = current->leftChild;
110 } else {
111 root = current->leftChild;
112 }
113 delete p;
114 } else {
115 kmin = current->rightChild;
116 while(kmin->leftChild != NULL) {
117 kmin = kmin->leftChild;
118 }
119 if(parent != NULL)
120 current->data = kmin->data;
121 else
122 root->data = kmin->data;
123 deleteNode(current->rightChild,kmin->data);
124 }
125 return true;
126 }
127
128 void createFile(int n) {
129 FILE *fp = fopen("file.txt","w");
130 while(n--) {
131 fprintf(fp,"%d ",rand()%10000);
132 }
133 fclose(fp);
134 }
135
136 int *readFile(int n) {
137 int *num = new int[n],i=0;
138 FILE *fp = fopen("file.txt","r");
139 while(!feof(fp)) {
140 fscanf(fp,"%d ",&num[i++]);
141 }
142 return num;
143 }
144
145 int main() {
146 BiTreeNode *root = NULL;
147 int n = 100,*num = NULL,i;
148 createFile(n);
149 num = readFile(n);
150 for(i=0; i<n; i++) {
151 DataType x;
152 x.key = num[i];
153 insert(root,&x);
154 }
155 for(i=0; i<n; i++) {
156 cout<<endl<<"del:"<<num[i]<<endl;
157 DataType m;
158 m.key = num[i];
159 deleteNode(root,m);
160 inTraverse(root);
161 }
162 //BiTreeNode *root = NULL;
163 return 0;
164 }
View Code
