C++ 二叉搜刮树代码

C++ 二叉搜刮树代码

2. #include <iostream>
3. using namespace std;
5. template<typename T>
6. struct TreeNode{
7.         T val;
8.         TreeNode *left;
9.         TreeNode *right;
10.         TreeNode():val(0), left(NULL), right(NULL){}
11.         TreeNode(T x):val(x), left(NULL), right(NULL){}
12. };
14. template<typename T>
15. class BinarySearchTree{
16. private:
17.         TreeNode<T> *root;
18.        
19.         TreeNode<T>* insertNode(TreeNode<T> *node, T value);
20.         TreeNode<T>* removeNode(TreeNode<T> *node, T value);
21.         bool searchNode(TreeNode<T> *node, T value);
22.         void inOrder(TreeNode<T> *node);
23. public:
24.         BinarySearchTree(): root(NULL){}
25.         ~BinarySearchTree();
26.        
27.         void insert(T value){
28.                 root = insertNode(root, value);
29.         }
30.        
31.         void remove(T value){
32.                 root = removeNode(root, value);
33.         }
34.        
35.         bool search(T value){
36.                 return searchNode(root, value);
37.         }
38.         void inOrderTraversal(){
39.                 inOrder(root);
40.                 cout << endl;
41.         }
42. };
44. template<typename T>
45. BinarySearchTree<T>::~BinarySearchTree(){
46.         while(root){
47.                 remove(root->val);
48.         }
49. }
51. template<typename T>
52. TreeNode<T>* BinarySearchTree<T>::insertNode(TreeNode<T> *node, T value){
53.         if(node == NULL){
54.                 return new TreeNode<T>(value);
55.         }
56.         if(value < node->val){
57.                 node->left = insertNode(node->left, value);
58.         }else if(value > node->val){
59.                 node->right = insertNode(node->right, value);
60.         }
61.         return node;
62. }
64. template<typename T>
65. TreeNode<T>* BinarySearchTree<T>::removeNode(TreeNode<T> *node, T value){
66.         if(node == NULL){
67.                 return NULL;
68.         }
69.         if(value < node->val){
70.                 node->left = removeNode(node->left, value);
71.         }else if(value > node->val){
72.                 node->right = removeNode(node->right, value);
73.         }else{
74.                 if(node->left == NULL && node->right == NULL){
75.                         delete node;
76.                         return NULL;
77.                 }else if(node->left == NULL){
78.                         TreeNode<T> *rightChild = node->right;
79.                         delete node;
80.                         return rightChild;
81.                 }else if(node->right == NULL){
82.                         TreeNode<T> *leftChild = node->left;
83.                         delete node;
84.                         return leftChild;
85.                 }else{
86.                         TreeNode<T> *replacement = node->right;
87.                         while(replacement->left){
88.                                 replacement = replacement->left;
89.                         }
90.                         node->val = replacement->val;
91.                         node->right = removeNode(node->right,replacement->val);
92.                 }
93.         }
94.         return node;
95. }
97. template<typename T>
98. bool BinarySearchTree<T>::searchNode(TreeNode<T> *node, T value){
99.         if(node == NULL){
100.                 return false;
101.         }
102.         if(value < node->val){
103.                 return searchNode(node->left, value);
104.         }else if(value > node->val){
105.                 return searchNode(node->right, value);
106.         }
107.     return true;
108. }
110. template<typename T>
111. void BinarySearchTree<T>::inOrder(TreeNode<T> *node){
112.         if(node){
113.                 inOrder(node->left);
114.                 cout << node->val << ',';
115.                 inOrder(node->right);
116.         }
117. }
119. int main()
120. {
121.     BinarySearchTree<int> bst;
122.         bst.insert(50);
123.         bst.insert(40);
124.         bst.insert(60);
125.         bst.insert(80);
126.         bst.insert(90);
127.         bst.insert(10);
128.         bst.insert(20);
129.         bst.insert(30);
130.         bst.insert(70);
131.         bst.inOrderTraversal();
132.         cout << bst.search(9090) << endl;
133.         cout << bst.search(70) << endl;
134.         bst.remove(70);
135.         bst.inOrderTraversal();
136.         bst.insert(65);
137.         bst.inOrderTraversal();
138.     return 0;
139. }

复制代码