BinarySearchTree二叉搜索树的实现

  1 // BinarySearchTree.cpp : 定义控制台应用程序的入口点。
  2 //
  3 
  4 #include "stdafx.h"
  5 #include <iostream>
  6 
  7 using std::cin;
  8 using std::cout;
  9 using std::endl;
 10 
 11 struct BinarySearchTreeNode{
 12     int key;
 13     BinarySearchTreeNode *parent;
 14     BinarySearchTreeNode *left;
 15     BinarySearchTreeNode *right;
 16 };
 17 
 18 struct BinarySearchTree{
 19     BinarySearchTreeNode *root;
 20     int nodes;
 21 };
 22 
 23 void initeTree(BinarySearchTree &T)
 24 {
 25     T.root = nullptr;
 26     T.nodes = 0;
 27 }
 28 
 29 void allocateNodeSpace(BinarySearchTreeNode **node)
 30 {
 31     *node = (BinarySearchTreeNode *)malloc(sizeof(BinarySearchTreeNode));
 32     if (*node == NULL)
 33         cout << "allocte space error!"<<endl;
 34     else
 35     {
 36         (*node)->left = nullptr;
 37         (*node)->right = nullptr;
 38         (*node)->parent = nullptr;
 39         (*node)->key = 0;
 40     }
 41 }
 42 
 43 
 44 
 45 void inorderVisit(BinarySearchTreeNode *node)
 46 {
 47     if (node != nullptr)
 48     {
 49         inorderVisit(node->left);
 50         cout << node->key << ‘ ‘;
 51         inorderVisit(node->right);
 52     }
 53 }
 54 
 55 //递归实现
 56 BinarySearchTreeNode &searchOneNode(BinarySearchTreeNode* node,int key)
 57 {
 58     if (node == nullptr || node->key == key)
 59         return *node;
 60     if (node->key < key)
 61         return searchOneNode(node->right, key);
 62     else
 63         return searchOneNode(node->left,key);
 64         
 65 }
 66 
 67 //迭代实现
 68 BinarySearchTreeNode &searchOneNode1(BinarySearchTreeNode* node, int key)
 69 {
 70     while (node != nullptr && key != node->key)
 71     {
 72         if (node->key < key)
 73             node = node->right;
 74         else
 75             node = node->left;
 76     }
 77     return *node;
 78 }
 79 
 80 //查找某个结点子树中的最小元素
 81 BinarySearchTreeNode & findMinmum(BinarySearchTreeNode *node)
 82 {
 83     while (node->left != nullptr)
 84     {
 85         node = node->left;
 86     }
 87     return *node;
 88 }
 89 
 90 //查找某个结点子树中的最大元素
 91 BinarySearchTreeNode & findMaxmum(BinarySearchTreeNode *node)
 92 {
 93     while (node->right != nullptr)
 94     {
 95         node = node->right;
 96     }
 97     return *node;
 98 }
 99 
100 //获取一个结点的后继
101 BinarySearchTreeNode & getNodeSuccessor(BinarySearchTreeNode *node)
102 {
103     BinarySearchTreeNode *ptr = nullptr;
104     ptr = node->right;
105     while (ptr != nullptr && ptr->left != nullptr)
106     {
107         ptr = ptr->left;
108     }
109     if (ptr == nullptr)
110         ptr = node->parent;
111     return *ptr;
112 }
113 
114 //建立一棵二叉搜索树，即向二叉搜索树中增加结点
115 void inserTreeNode(BinarySearchTree &T,BinarySearchTreeNode *node)
116 {
117     BinarySearchTreeNode *parentPtr = nullptr;
118     BinarySearchTreeNode *temPtr = T.root;
119     while (temPtr != nullptr)
120     {
121         parentPtr = temPtr;
122         if (node->key < temPtr->key)
123             temPtr = temPtr->left;
124         else
125             temPtr = temPtr->right;
126     }
127     node->parent = parentPtr;
128     if (parentPtr == nullptr)
129         T.root = node;
130     else if (node->key < parentPtr->key)
131         parentPtr->left = node;
132     else
133         parentPtr->right = node;
134 }
135 
136 //建立一棵二叉搜索树，即
137 void createTree(BinarySearchTree &T)
138 {
139     int key = -1;
140     BinarySearchTreeNode *temNode = nullptr;
141     while (cin>>key,key!=-1)
142     {
143 
144         allocateNodeSpace(&temNode);
145         temNode->key = key;
146         inserTreeNode(T,temNode);
147     }
148 }
149 
150 //用一棵子树v替换另一棵子树u并成为其（u）双亲的孩子结点。
151 void transplantUV(BinarySearchTree &T,BinarySearchTreeNode *u, BinarySearchTreeNode *v)
152 {
153     if (u->parent == nullptr)
154         T.root = v;
155     else if (u == u->parent->left)
156         u->parent->left = v;
157     else
158         u->parent->right = v;
159     if (v != nullptr)
160         v->parent = u->parent;
161 }
162 //从二叉搜索树中删除一个结点
163 /*
164 从一棵二叉搜索树中删除一个结点node，可以分为三种情况：
165 1）如果node没有孩子结点，那么可以直接删除该结点；
166 2）如果node只有一个孩子结点，那么就让该孩子结点取代node的位置；
167 3）如果node有两个孩子结点，那么找到node的后继结点afterNode（一定在node的右子树中），并让afterNode取代node的位置。
168 并让node原来的右子树成为afterNode新的右子树，node的左子树成为afterNode的左子树。
169 对于情况3）又可以分为两种情况：
170 3.1）afterNode是node的右孩子，那么直接让afterNode取代node的位置，不做其它变换。
171 3.2）afterNode是node的右子树中的左子树的一个结点，但不是node的右孩子，那么先让afterNode的右孩子取代afterNode的位置，
172 然后让afterNode取代node的位置，并让node的右子树成为afterNode新的右子树。
173 */
174 void deleteTreeNode(BinarySearchTree &T, int key)
175 {
176     BinarySearchTreeNode *node = &searchOneNode1(T.root,key);
177     if (node->left == nullptr)
178         transplantUV(T, node, node->right);
179     else if (node->right == nullptr)
180         transplantUV(T,node,node->left);
181     else
182     {
183         BinarySearchTreeNode *temPtr = &findMinmum(node->right);
184         if (temPtr->parent != node)
185         {
186             transplantUV(T,temPtr,temPtr->right);
187             temPtr->right = node->right;
188             temPtr->right->parent = temPtr;
189         }
190         transplantUV(T, node, temPtr);
191         temPtr->left = node->left;
192         node->left->parent = temPtr;
193     }
194     free(node);
195 }
196 
197 void main(void)
198 {
199     cout << "1.首先构建一棵二叉搜索树:" << endl;
200     BinarySearchTree T;
201     initeTree(T);
202     createTree(T);
203     cout << "2.中序遍历二叉搜索树:" << endl;
204     inorderVisit(T.root);
205     //cout << endl;
206     //cout << "3.输入出一个结点的后继结点:" << endl;
207     //cout << "请输入要查找的结点的关键字Key:" << endl;
208     //int keyValue;
209     //cin >> keyValue;
210     //BinarySearchTreeNode *temPtr = &searchOneNode1(T.root,keyValue);
211     //BinarySearchTreeNode *successorPtr = &getNodeSuccessor(temPtr);
212     //cout << successorPtr->key;
213     //cout << "请输入要删除的结点的关键字:" << endl;
214     //cin >> keyValue;
215     int keyValue;
216     cin >> keyValue;
217     deleteTreeNode(T, keyValue);
218     inorderVisit(T.root);
219 }