一个较完整的二叉查找树，实现如下功能
(1) 插入一个节点
(2) 删除一个节点
(3) 删除整棵树
(4) 查找一个节点
(5) 前序遍历，递归和非递归
(6) 中序遍历，递归和非递归
(7) 后序遍历，递归和非递归
(8) 查找最大的节点
(9) 查找最小的节点
(10) 查找某个节点的前驱
(11) 查找某个节点的后继
(12) 打印某一层内的节点
(13) 分层遍历二叉树，每一层内的节点占一行
1 struct BstNode 2 { 3 int data; 4 bool isVisisted; 5 BstNode * left, * right; 6 BstNode * father; 7 BstNode(int _data=0, bool _isVisisted=false, BstNode * _left=NULL, BstNode * _right=NULL, BstNode * _father=NULL) 8 { 9 this->data = _data; 10 this->isVisisted = _isVisisted; 11 this->left = _left; 12 this->right = _right; 13 this->father = _father; 14 } 15 }; 16 17 class BinarySearchTree 18 { 19 public: 20 BinarySearchTree(BstNode * _root = NULL); 21 ~BinarySearchTree(); 22 void insertNode(int _data); 23 void deleteNode(int _data); 24 void destroyTree(); 25 bool findNode(int _data, BstNode * & pt, BstNode * & father); 26 void preOrderPrint(); 27 void midOrderPrint(); 28 void postOrderPrint(); 29 void loopPreOrderPrint(); 30 void loopPreOrderPrint2(); 31 void loopMidOrderPrint(); 32 void loopPostOrderPrint(); 33 void loopPostOrderPrint2(); 34 BstNode * maximumTree(BstNode * node); 35 BstNode * minimumTree(BstNode * node); 36 BstNode * predecessor(BstNode * node); 37 BstNode * successor(BstNode * node); 38 void printNodeByLevel(); 39 int printNodeAtLevel(int level); 40 private: 41 void dfsInsertNode(BstNode * pt,int data); 42 void dfsDestroyTree(BstNode * & pt); 43 void dfsPreOrderPrint(BstNode * pt); 44 void dfsMidOrderPrint(BstNode * pt); 45 void dfsPostOrderPrint(BstNode * pt); 46 int dfsPrintNodeAtLevel(BstNode * root,int level); 47 BstNode * root; 48 }; 49 50 BinarySearchTree::BinarySearchTree(BstNode * _root) 51 { 52 this->root = _root; 53 } 54 55 BinarySearchTree::~BinarySearchTree() 56 { 57 destroyTree(); 58 } 59 60 BstNode * BinarySearchTree::maximumTree(BstNode * node) 61 { 62 if (node == NULL) 63 { 64 return NULL; 65 } 66 while(node->right != NULL) 67 { 68 node = node->right; 69 } 70 return node; 71 } 72 73 BstNode * BinarySearchTree::minimumTree(BstNode * node) 74 { 75 if (node == NULL) 76 { 77 return NULL; 78 } 79 while(node->left != NULL) 80 { 81 node = node->left; 82 } 83 return node; 84 } 85 86 BstNode * BinarySearchTree::predecessor(BstNode * node) 87 { 88 if (node->left != NULL) 89 { 90 return maximumTree(node->left); 91 } 92 BstNode * fatherNode = node->father; 93 while(fatherNode != NULL && node==fatherNode->left) 94 { 95 node = fatherNode; 96 fatherNode = fatherNode->father; 97 } 98 return fatherNode; 99 }100 101 BstNode * BinarySearchTree::successor(BstNode * node)102 {103 if (node->right != NULL)104 {105 return minimumTree(node->right);106 }107 BstNode * fatherNode = node->father;108 while(fatherNode != NULL && node==fatherNode->right)109 {110 node = fatherNode;111 fatherNode = fatherNode->father;112 }113 return fatherNode;114 }115 116 bool BinarySearchTree::findNode(int _data, BstNode * & pt, BstNode * & father)117 {118 pt = root;119 while(pt != NULL)120 {121 if (pt->data == _data)122 {123 return true;124 }125 father = pt;126 if (_data < pt->data)127 {128 pt = pt->left;129 }130 else131 {132 pt = pt->right;133 }134 }135 return false;136 }137 138 void BinarySearchTree::insertNode(int _data)139 {140 dfsInsertNode(root,_data);141 }142 143 void BinarySearchTree::dfsInsertNode(BstNode * pt,int data)144 {145 if (root == NULL)146 {147 root = new BstNode(data);148 return;149 }150 if (pt == NULL)151 {152 return;153 }154 if (data < pt->data)155 {156 if (pt->left == NULL)157 {158 pt->left = new BstNode(data);159 pt->left->father = pt;160 }161 else162 {163 dfsInsertNode(pt->left,data);164 }165 }166 else167 {168 if (pt->right == NULL)169 {170 pt->right = new BstNode(data);171 pt->right->father = pt;172 }173 else174 {175 dfsInsertNode(pt->right,data);176 }177 }178 }179 180 void BinarySearchTree::deleteNode(int _data)181 {182 BstNode * pt = NULL, * fathePt = NULL;183 bool flag = findNode(_data,pt,fathePt);184 if (!flag)185 {186 return;187 }188 if (pt->left==NULL && pt->right==NULL)189 {190 if (pt == root)191 {192 delete root;193 root = NULL;194 }195 else196 {197 if (pt==fathePt->left)198 {199 fathePt->left = NULL;200 }201 else202 {203 fathePt->right = NULL;204 }205 delete pt;206 }207 }208 else if(pt->left != NULL && pt->right == NULL)209 {210 if (pt == root)211 {212 BstNode * tmp = pt->left;213 delete root;214 root = tmp;215 }216 else217 {218 if (pt == fathePt->left)219 {220 fathePt->left = pt->left;221 }222 else223 {224 fathePt->right = pt->left;225 }226 delete pt;227 }228 }229 else if (pt->right != NULL && pt->left == NULL)230 {231 if (pt == root)232 {233 BstNode * tmp = pt->right;234 delete root;235 root = tmp;236 }237 else238 {239 if (pt == fathePt->left)240 {241 fathePt->left = pt->right;242 }243 else244 {245 fathePt->right = pt->right;246 }247 delete pt;248 }249 }250 else251 {252 BstNode * tpt = successor(pt);253 int tdata = tpt->data;254 BstNode * tfatherPt = tpt->father;255 if (tpt == tfatherPt->left)256 {257 tfatherPt->left = tpt->right;258 }259 else260 {261 tfatherPt->right = tpt->right;262 }263 pt->data = tdata;264 delete tpt;265 }266 }267 268 void BinarySearchTree::destroyTree()269 {270 dfsDestroyTree(root);271 }272 273 void BinarySearchTree::dfsDestroyTree(BstNode * & pt)274 {275 if (pt != NULL)276 {277 dfsDestroyTree(pt->left);278 dfsDestroyTree(pt->right);279 pt = NULL;280 }281 }282 283 void BinarySearchTree::preOrderPrint()284 {285 dfsPreOrderPrint(root);286 }287 288 void BinarySearchTree::dfsPreOrderPrint(BstNode * pt)289 {290 if (pt != NULL)291 {292 cout< data <<" ";293 dfsPreOrderPrint(pt->left);294 dfsPreOrderPrint(pt->right);295 }296 }297 298 void BinarySearchTree::midOrderPrint()299 {300 dfsMidOrderPrint(root);301 }302 303 void BinarySearchTree::dfsMidOrderPrint(BstNode * pt)304 {305 if (pt != NULL)306 {307 dfsMidOrderPrint(pt->left);308 cout< data <<" ";309 dfsMidOrderPrint(pt->right);310 }311 }312 313 void BinarySearchTree::postOrderPrint()314 {315 dfsPostOrderPrint(root);316 }317 318 void BinarySearchTree::dfsPostOrderPrint(BstNode * pt)319 {320 if (pt != NULL)321 {322 dfsPostOrderPrint(pt->left);323 dfsPostOrderPrint(pt->right);324 cout< data <<" ";325 }326 }327 328 void BinarySearchTree::loopPreOrderPrint()329 {330 stack stk;331 BstNode * pt = root;332 while(pt!=NULL || !stk.empty())333 {334 if (pt != NULL)335 {336 cout< data <<" ";337 stk.push(pt);338 pt = pt->left;339 }340 else341 {342 pt = stk.top();343 stk.pop();344 pt = pt->right;345 }346 }347 }348 349 void BinarySearchTree::loopPreOrderPrint2()350 {351 if (root == NULL)352 {353 return;354 }355 stack stk;356 stk.push(root);357 while(!stk.empty())358 {359 BstNode * top = stk.top();360 stk.pop();361 cout< data <<" ";362 if (top->right != NULL)363 {364 stk.push(top->right);365 }366 if (top->left != NULL)367 {368 stk.push(top->left);369 }370 }371 }372 373 void BinarySearchTree::loopMidOrderPrint()374 {375 stack stk;376 BstNode * pt = root;377 while(pt!=NULL || !stk.empty())378 {379 if (pt != NULL)380 {381 stk.push(pt);382 pt = pt->left;383 }384 else385 {386 pt = stk.top();387 stk.pop();388 cout< data <<" ";389 pt = pt->right;390 }391 }392 }393 394 void BinarySearchTree::loopPostOrderPrint()395 {396 stack stk;397 BstNode * pt = root;398 while(pt!=NULL || !stk.empty())399 {400 if (pt != NULL)401 {402 pt->isVisisted = false;403 stk.push(pt);404 pt = pt->left;405 }406 else407 {408 pt = stk.top();409 if(pt->isVisisted) 410 { 411 cout< data<<" "; 412 stk.pop(); 413 pt = NULL; 414 } 415 else 416 { 417 pt->isVisisted = true;418 pt=pt->right; 419 } 420 }421 }422 }423 424 void BinarySearchTree::loopPostOrderPrint2()425 {426 stack stk;427 BstNode * preNode = NULL; //指向前一个被访问的节点428 BstNode * pt = root; //指向当前要检查的节点429 while(pt!=NULL || !stk.empty())430 {431 while(pt != NULL) //一直向左走直到为空432 {433 stk.push(pt);434 pt = pt->left;435 }436 pt = stk.top();437 //当前节点的右孩子如果为空或者已经被访问，则访问当前节点438 if (pt->right == NULL || pt->right==preNode)439 {440 cout< data <<" ";441 stk.pop();442 preNode = pt;443 pt = NULL;444 }445 else //否则访问右孩子446 {447 pt = pt->right;448 }449 }450 }451 452 int BinarySearchTree::printNodeAtLevel(int level)453 {454 return dfsPrintNodeAtLevel(root,level);455 }456 457 int BinarySearchTree::dfsPrintNodeAtLevel(BstNode * root,int level)458 {459 if (root==NULL || level<0)460 {461 return 0;462 }463 if (level == 0)464 {465 cout< data <<" ";466 return 1;467 }468 return dfsPrintNodeAtLevel(root->left,level-1)+dfsPrintNodeAtLevel(root->right,level-1);469 }470 471 void BinarySearchTree::printNodeByLevel() 472 {473 if (root == NULL)474 {475 return;476 }477 vector vec;478 vec.push_back(root);479 int cur = 0, last = 1;480 while(cur < vec.size())481 {482 last = vec.size();483 while(cur < last)484 {485 cout< data <<" ";486 if (vec[cur]->left != NULL)487 {488 vec.push_back(vec[cur]->left);489 }490 if (vec[cur]->right != NULL)491 {492 vec.push_back(vec[cur]->right);493 }494 cur++;495 }496 cout<