首页 > 代码库 > 二叉排序树的插入与删除
二叉排序树的插入与删除
一、二叉排序树的插入
首先检查要插入的数据是否已存在，若存在则不插入，若不存在，则把元素插入到在二叉树上查找失败时的结点的左孩子和右孩子上。需要考虑的特殊情况是插入第一个元素前，二叉树为空。
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 else10 current = current->leftChild;11 }12 p = new BiTreeNode;13 p->data = http://www.mamicode.com/*item;14 15 //the new node is root node16 if(parent == NULL)17 root = p;18 //as leftChild19 else if(item->key < parent->data.key)20 parent->leftChild = p;21 //as rightChild22 else23 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 = http://www.mamicode.com/kmin->data;47 else48 root->data = http://www.mamicode.com/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 = http://www.mamicode.com/*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 = http://www.mamicode.com/kmin->data;121 else122 root->data = http://www.mamicode.com/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 }
二叉排序树的插入与删除
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。