查找树是一种数据结构,它支持很多动态的操作,包括search,maximum,predecessor,successor,insert,delete等操作!它既可以当作字典,又可以当作优先队列!
二叉查找树所有的基本操作与树的高度成正比,对于一棵含n个节点的完全二叉树,这些基本操作的最坏的运行情况是O(lgn)这对于一些基本的数据结构来讲,具有优势!
下面简要的实现这些基本的函数!
注意二叉查找树的性质 :对于任何一个节点,它的左子树的值是小于该节点的,而它右子树的任意节点是大于该节点的!
1 #include <cstdlib> 2 #include <iostream> 3 using namespace std; 4 typedef struct node 5 { 6 int data; 7 struct node* left; 8 struct node* right; 9 struct node* parent; 10 }_node,*pnode; 11 void insert(pnode &root,int value) 12 { 13 pnode y=NULL; 14 pnode x=root; 15 while (x!=NULL) 16 { 17 y=x; 18 if(value<x->data) 19 { 20 x=x->left; 21 } 22 else 23 x=x->right; 24 } 25 pnode q=new _node; 26 q->data=value; 27 q->parent=y; 28 if(y==NULL) 29 root=q; 30 else if(q->data<y->data) 31 y->left=q; 32 else 33 y->right=q; 34 35 36 } 37 //中序遍历 38 void inorder(pnode root) 39 { 40 if(root!=NULL) 41 { 42 inorder(root->left); 43 cout<<root->data<<endl; 44 inorder(root->right); 45 } 46 } 47 pnode tree_search(pnode root ,int key) 48 { 49 if(root==NULL||key==root->data) 50 return root; 51 if(key<root->data) 52 return tree_search(root->left,key); 53 else 54 return tree_search(root->right,key); 55 } 56 //求出这个二叉查找树的最小值 57 pnode tree_minimum(pnode root) 58 { 59 while(root->left!=NULL) 60 { 61 root=root->left; 62 tree_minimum(root); 63 } 64 return root; 65 66 } 67 //求出这个二叉查找树的最大值 68 pnode tree_maxnum(pnode root) 69 { 70 while(root->right!=NULL) 71 { 72 root=root->right; 73 tree_maxnum(root); 74 } 75 return root; 76 } 77 //按中序遍历后的后继 78 pnode tree_successor(pnode x) 79 { 80 if(x->right!=NULL) 81 return tree_minimum(x->right); 82 pnode y=x->parent; 83 while(y!=NULL&&x==y->right) 84 { 85 x=y; 86 y=y->parent; 87 } 88 89 90 return y; 91 } 92 //按中序遍历后的前驱 93 pnode tree_presuccessor(pnode x) 94 { 95 if(x->left!=NULL) 96 return tree_maxnum(x->left); 97 pnode y=x->parent; 98 while(y!=NULL&&x==y->left) 99 { 100 x=y; 101 y=y->parent; 102 } 103 return y; 104 } 105 pnode tree_delete(pnode &root ,pnode z ) 106 { 107 pnode y;//确定要删除的节点! 108 pnode x; 109 if(z->left==NULL||z->right==NULL) 110 y=z; 111 else 112 y=tree_successor(z); 113 if(y->left!=NULL) 114 x=y->left; 115 else 116 x=y->right; 117 if(x!=NULL) 118 x->parent=y->parent; 119 if(y->parent==NULL) 120 root=x; 121 else if(y==y->parent->left) 122 y->parent->left=x; 123 else 124 y->parent->right=x; 125 if(y!=z) 126 z->data=y->data; 127 return y; 128 129 } 130 131 int main(int argc, const char *argv[]) 132 { 133 134 pnode root=NULL; 135 int i; 136 int size; 137 cout<<"you want to build the size of the binary search tree:"<<endl; 138 cin>>size; 139 for (i = 0; i < size ; i++) { 140 int value; 141 cin>>value; 142 insert(root,value); 143 } 144 cout<<"you want to search:"; 145 int search_num; 146 cin>>search_num; 147 pnode q=tree_search(root,search_num); 148 if(q==NULL) 149 cout<<"fail to find"<<endl; 150 else 151 cout<<"find it "<<endl; 152 153 cout<<"inorder root:"<<endl; 154 inorder(root); 155 cout<<"the max num of the binary tree is :\n"; 156 q=tree_maxnum(root); 157 cout<<q->data<<endl; 158 cout<<"the min num of the binary tree is :\n"; 159 q=tree_minimum(root); 160 cout<<q->data<<endl; 161 cout<<"please input the number you want to look at the successor of it:\n"; 162 int num; 163 cin>>num; 164 pnode q1=tree_search(root,num); 165 q=tree_successor(q1); 166 cout<<"the successor is:"<<endl; 167 cout<<q->data<<endl; 168 q=tree_presuccessor(q1); 169 cout<<"the presuccessor is :"<<endl; 170 cout<<q->data<<endl; 171 cout<<"after delete the presuccessor :\n"; 172 tree_delete(root,q1); 173 inorder(root); 174 return 0; 175 }