二叉查找树的实现
查找树是一种数据结构,它支持很多动态的操作,包括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 }
分类: 数据结构
标签: 数据结构
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did48511