二叉搜索树ADT_BSTree

淩亂°似流年 2022-08-10 09:37 9阅读 0赞

二叉搜索树或是一颗空二叉树, 或是具有以下性质的二叉树:

1.若左子树不为空, 则左子树上所有结点的关键字值均小于根结点的关键字值.

2.若右子树不为空, 则右子树上所有结点的关键字值均大于根结点的关键字值.

3.左右子树也分别是二叉搜索树.

性质: 若以中序遍历一颗二叉搜索树, 将得到一个以关键字值递增排列的有序序列.

1.搜索实现: 若二叉树为空, 则搜索失败. 否则, 将x与根结点比较. 若x小于该结点的值, 则以同样的方法搜索左子树, 不必搜索右子树. 若x

大于该结点的值, 则以同样的方法搜索右子树, 而不必搜索左子树. 若x等于该结点的值, 则搜索成功终止.

search()为递归搜索, search1()为迭代搜索.

2.插入实现: 插入一个新元素时, 需要先搜索新元素的插入位置. 如果树种有重复元素, 返回Duplicate. 搜索达到空子树, 则表明树中不包

含重复元素. 此时构造一个新结点p存放新元素x, 连至结点q, 成为q的孩子, 则新结点p成为新二叉树的根.

3.删除实现: 删除一个元素时, 先搜索被删除结点p, 并记录p的双亲结点q. 若不存在被删除的元素, 返回NotPresent.

(1)若p有两颗非空子树, 则搜索结点p的中序遍历次序下的直接后继结点, 设为s. 将s的值复制到p中.

(2)若p只有一颗非空子树或p是叶子, 以结点p的唯一孩子c或空子树c = NULL取代p.

(3)若p为根结点, 删除后结点c成为新的根. 否则若p是其双亲确定左孩子, 则结点c也应成为q的左孩子, 最后释放结点p所占用的空间.

实现代码:

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  \#include "iostream"  
2.  \#include "cstdio"  
3.  \#include "cstring"  
4.  \#include "algorithm"  
5.  \#include "cmath"  
6.  \#include "utility"  
7.  \#include "map"  
8.  \#include "set"  
9.  \#include "vector"  
10. using namespace std;  
11. typedef long long ll;  
12. const int MOD = 1e9 + 7;  
13. enum ResultCode\{ Underflow, Overflow, Success, Duplicate, NotPresent \}; // 赋值为0, 1, 2, 3, 4, 5  
14.   
15. template <class T>  
16. class DynamicSet  
17. \{  
18. public:  
19.     virtual ~DynamicSet() \{\}  
20.     virtual ResultCode Search(T &x) const = 0;  
21.     virtual ResultCode Insert(T &x) = 0;  
22.     virtual ResultCode Remove(T &x) = 0;  
23.     /\* data \*/  
24. \};  
25.   
26. template <class T>  
27. struct BTNode  
28. \{  
29.     BTNode() \{ lChild = rChild = NULL; \}  
30.     BTNode(const T &x) \{  
31.         element = x;  
32.         lChild = rChild = NULL;  
33.     \}  
34.     BTNode(const T &x, BTNode<T> \*l, BTNode<T> \*r) \{  
35.         element = x;  
36.         lChild = l;  
37.         rChild = r;  
38.     \}  
39.     T element;  
40.     BTNode<T> \*lChild, \*rChild;  
41.     /\* data \*/  
42. \};  
43.   
44. template <class T>  
45. class BSTree : public DynamicSet<T>  
46. \{  
47. public:  
48.     explicit BSTree() \{ root = NULL; \} // 只可显示转换  
49.     virtual ~BSTree() \{ Clear(root); \}  
50.     ResultCode Search(T &x) const;  
51.     ResultCode Search1(T &x) const;  
52.     ResultCode Insert(T &x);  
53.     ResultCode Remove(T &x);  
54. protected:  
55.     BTNode<T> \*root;  
56. private:  
57.     void Clear(BTNode<T> \*t);  
58.     ResultCode Search(BTNode<T> \*p, T &x) const;  
59.     /\* data \*/  
60. \};  
61.   
62. template <class T>  
63. void BSTree<T>::Clear(BTNode<T> \*t)  
64. \{  
65.     if(t) \{  
66.         Clear(t -> lChild);  
67.         Clear(t -> rChild);  
68.         cout << "delete" << t -> element << "..." << endl;  
69.         delete t;  
70.     \}  
71. \}  
72.   
73. template< class T>  
74. ResultCode BSTree<T>::Search(T &x) const  
75. \{  
76.     return Search(root, x);  
77. \}  
78. template <class T>  
79. ResultCode BSTree<T>::Search(BTNode<T> \*p, T &x) const  
80. \{  
81.     if(!p) return NotPresent;  
82.     if(x < p -> element) return Search(p -> lChild, x);  
83.     if(x > p -> element) return Search(p -> rChild, x);  
84.     x = p -> element;  
85.     return Success;  
86. \}  
87.   
88. template <class T>  
89. ResultCode BSTree<T>::Search1(T &x) const  
90. \{  
91.     BTNode<T> \*p = root;  
92.     while(p) \{  
93.         if(x < p -> element) p = p -> lChild;  
94.         else if(x > p -> element) p = p -> rChild;  
95.         else \{  
96.             x = p -> element;  
97.             return Success;  
98.         \}  
99.     \}  
100.     return NotPresent;  
101. \}  
102.   
103. template <class T>  
104. ResultCode BSTree<T>::Insert(T &x)  
105. \{  
106.     BTNode<T> \*p = root, \*q = NULL;  
107.     while(p) \{  
108.         q = p;  
109.         if(x < p -> element) p = p -> lChild;  
110.         else if(x > p -> element) p = p -> rChild;  
111.         else \{  
112.             x = p -> element;  
113.             return Duplicate;  
114.         \}  
115.     \}  
116.     p = new BTNode<T>(x);  
117.     if(!root) root = p;  
118.     else if(x < q -> element) q -> lChild = p;  
119.     else q -> rChild = p;  
120.     return Success;  
121. \}  
122.   
123. template <class T>  
124. ResultCode BSTree<T>::Remove(T &x)   
125. \{  
126.     BTNode<T> \*c, \*s, \*r, \*p = root, \*q = NULL;  
127.     while(p && p -> element != x) \{  
128.         q = p;  
129.         if(x < p -> element) p = p -> lChild;  
130.         else p = p -> rChild;  
131.     \}  
132.     if(!p) return NotPresent;  
133.     x = p -> element;  
134.     if(p -> lChild && p -> rChild) \{  
135.         s = p -> rChild;  
136.         r = p;  
137.         while(s -> lChild) \{  
138.             r = s;  
139.             s = s -> lChild;  
140.         \}  
141.         p -> element = s -> element;  
142.         p = s;  
143.         q = r;  
144.     \}  
145.     if(p -> lChild) c = p -> lChild;  
146.     else c = p -> rChild;  
147.     if(p == root) root = c;  
148.     else if(p == q -> lChild) q -> lChild = c;  
149.     else q -> rChild = c;  
150.     delete p;  
151.     return Success;  
152. \}  
153. int main(int argc, char const \*argv\[\])  
154. \{  
155.     BSTree<int> bst;  
156.     int x = 28; bst.Insert(x);  
157.     x = 21; bst.Insert(x);  
158.     x = 25; bst.Insert(x);  
159.     x = 36; bst.Insert(x);  
160.     x = 33; bst.Insert(x);  
161.     x = 43; bst.Insert(x);  
162.     return 0;  
163. \}

[view plain]: http://blog.csdn.net/gkhack/article/details/49910083#