二叉树之二叉搜索树的基本操作实现

发布时间：2016-10-25 09:18:38.817 作者：文章转自网络，版权归原作者所有，反馈可立刻删除 (该文来自笔记，点击查看原文)

这篇文章用来回顾二叉搜索数的以下操作:

遍历
- 前序遍历
- 中序遍历
- 后序遍历
- 层序遍历
查找
- 查找最大值
- 查找最小值
- 查找指定值

获取指定属性
- 获取总节点/叶节点数量
- 获取二叉树的高度(根的高度为1)
行为操作
- 插入
- 删除

二叉树的结构定义:

1 struct TreeNode{ 2  TreeNode():data(),left(nullptr),right(nullptr){} 3  ELEMENT data; 4  SearchTree left; 5  SearchTree right; 6 };

这是一些typedef,一般传参的时候用SearchTree,声明变量的时候用Position,避免混之.

1 struct TreeNode; 2 typedef int ELEMENT; 3 typedef TreeNode * Position; 4 typedef TreeNode *  SearchTree;

0.类中提供的API

 1 class CBinTree  2 {  3 public:  4 CBinTree(void);  5  6 ~CBinTree(void);  7  8 // Return true when it's empty  9 bool isEmpty() ; 10 11 // Insert a element. 12 size_t _insert_(ELEMENT &_data); 13 14 // Delete a element. 15 size_t _delete_(ELEMENT &_data); 16 17 // Traversal of preorder/inorder/postorder/sequence order. 18 void traversalPre(); 19 void traversalIn(); 20 void traversalPos(); 21 void traversalSeq(); 22 23 // Find something. 24  Position findMin(); 25  Position findMax(); 26 Position find(ELEMENT &_data); 27 28 // Get the number of node/leafnode. 29 void getNodeNum(int * _nodenum,int * _leafnodenum); 30 31 // Get the height of tree 32 int getTreeHeight(); 33 34 // Show this tree  35 void showThisTree(); 36 37 private: 38 // Record the size of nodes 39 int size; 40 // The root of binary tree  41  SearchTree stRoot; 42 private: 43 SearchTree insert_specific(ELEMENT &_data,SearchTree & _T); 44 45 SearchTree delete_specific(ELEMENT &_data,SearchTree &_T); 46 47 void traversalPre_specific(SearchTree _T); 48 49 void traversalIn_specific(SearchTree _T); 50 51 void traversalPos_specific(SearchTree _T); 52 53 void traversalSeq_specific(SearchTree _T); 54 55  Position findMin_specific(SearchTree _T); 56 57  Position findMax_specific(SearchTree _T); 58 59 Position find_specific(SearchTree _T,ELEMENT &_data); 60 61 int getTreeHeight_specific(SearchTree _T); 62 63 void getNodeNum_specific(SearchTree _T,int * _nodenum,int * _leafnodenum); 64 65 void showThisTree_specific(SearchTree _T); 66 };

具体实现都在对应的*_specific函数中;

1.遍历

因为二叉查找树的平均深度是O(logN),所以一般不用担心栈空间会被用尽.

由于前/中/后序遍历只是把输出函数换了个位置,故这里只放出中序遍历的代码:

1 void CBinTree::traversalIn_specific(SearchTree _T){ 2 if (_T) 3  { 4 traversalIn_specific(_T->left); 5 printf("%d ",_T->data); 6 traversalIn_specific(_T->right); 7  } 8 }

层序遍历:

利用了STL的队列.

 1 void CBinTree::traversalSeq_specific(SearchTree _T){  2 if (_T)  3  {  4 // Remember the first node  5 std::queue<Position> QNode;  6  QNode.push(_T);  7  8 // Save the dequeued node  9  Position popNode; 10 11 while (!QNode.empty()) 12  { 13 // DeQueue 14 popNode = QNode.front(); 15  QNode.pop(); 16 17 // Output the first node of QNode 18 printf("%d ",popNode->data); 19 20 // EnQueue  21 if (popNode->left) 22  { 23 QNode.push(popNode->left); 24  } 25 if (popNode->right) 26  { 27 QNode.push(popNode->right); 28  } 29  } 30  } 31 }

2.查找

这里我是用循环实现的,如此类似于链表的操作,简单易懂.

基于搜索二叉树的定义出发,代码如下:

 1 Position CBinTree::findMin_specific(SearchTree _T){  2 Position minNodePos = _T;  3 while (minNodePos->left)  4  {  5 minNodePos = minNodePos->left;  6  }  7 return minNodePos;  8 }  9 10 Position CBinTree::findMax_specific(SearchTree _T){ 11 Position minNodePos = _T; 12 while (minNodePos->right) 13  { 14 minNodePos = minNodePos->right; 15  } 16 return minNodePos; 17 } 18 19 Position CBinTree::find_specific(SearchTree _T,ELEMENT &_data){ 20 Position foundNode = _T; 21 while (foundNode) 22  { 23 if (_data > foundNode->data) 24  { 25 foundNode = foundNode->right; 26  } 27 else if (_data < foundNode->data) 28  { 29 foundNode = foundNode->left; 30  } 31 else 32  { 33 return foundNode; 34  } 35  } 36 return nullptr; 37 }

3.获取指定属性:

获取总结点和叶子节点的数量

利用层序遍历的方式可以直接解决这两个问题.

_nodenum是总结点的数量,_leafnodenum是叶节点的数量.调用者需要传递其指针以便计算.

 1 void CBinTree::getNodeNum_specific(SearchTree _T,int * _nodenum,int * _leafnodenum){  2 Position T = _T;  3 *_nodenum = 0;  4 *_leafnodenum = 0;  5 if (T)  6  {  7 // Remember the first node  8 std::queue<Position> QNode;  9  QNode.push(T); 10 (*_nodenum) ++ ; 11 // Save the dequeued node 12  Position popNode; 13 14 while (!QNode.empty()) 15  { 16 // DeQueue 17 popNode = QNode.front(); 18  QNode.pop(); 19 20 // Output the first node of QNode 21 // printf("%d\n",popNode->data); 22 23 // EnQueue  24 if (popNode->left) 25  { 26 QNode.push(popNode->left); 27 (*_nodenum) ++ ; 28  } 29 if (popNode->right) 30  { 31 QNode.push(popNode->right); 32 (*_nodenum) ++ ; 33  } 34 35 // To determine whether the leafnode 36 if (!popNode->left && !popNode->right) 37  { 38 (*_leafnodenum) ++; 39  } 40  } 41  } 42 }

获取二叉树的高度(根的高度为1)

这里的递归很奇妙:),递归都很有魔法不是么?

思路是递归计算每条分支的高度,相比较取最大的那个,听起来很简单.具体的实现方式居然是从叶子节点开始返回1,然后递归向上不断的加1,这一点很有趣.

这也是在最后"+1"的原因(魔法).

可以将这八行代码缩短为三行.但我认为这样阅读起来很舒服.

 1 int CBinTree::getTreeHeight_specific(SearchTree _T){  2 if (_T)  3  {  4  size_t  5 lh = getTreeHeight_specific(_T->left),  6 rh = getTreeHeight_specific(_T->right);  7 return (lh > rh)?lh+1:rh+1;  8  }  9 return 0; 10 }

4.行为操作:

插入

插入操作是利用二叉树天生的递归特性一个典例.

我以前一直不太理解递归如何保持新创建节点与其父节点的关联性.

后来发现漂亮的地方在与利用递归的返回值,与即将开始递归前的等待被赋值("_T->left ="),正是此赋值语句保持了节点之间的关系.

但是这也是一个问题,因为对于已经确定关系的节点而言岂不是要多次赋值(建立连接),即新节点加入之后,以上的节点还要继续赋值以再建立已经存在的连接.

而使用循环的话解可以避免这样的问题,只需新建立一个节点,与其父节点连接就大功告成,但是我试过,代码写起来没有递归的好看 :)

太漂亮了,献上代码敬之.

 1 SearchTree CBinTree::insert_specific(ELEMENT &_data,SearchTree & _T){  2 if (_T == nullptr)  3  {  4 // Create a new node   5 _T = new TreeNode;  6 _T->data = _data;  7 size++;  8 // Return to the father node ,tell him this node be created already.  9 // return T; 10  } 11 else if (_data < _T->data) 12  { 13 _T->left = insert_specific(_data,_T->left); 14  } 15 else if (_data > _T->data) 16  { 17 _T->right = insert_specific(_data,_T->right); 18  } 19 // Back to the above node,remain their linear relation. 20 return _T; 21 }

删除

花点时间总结删除操作.我确实花了点时间理解 :(

这里的递归也是太漂亮了.

删除节点的情况可以分为三种,即节点间的连接方式种类.

1. 有2个子节点
2. 有1个子节点
3. 有0个子节点

最困难的莫过于删除第一种情况的节点了.在此之前复习一下后两种的删除方法:
对于2.当前节点直接被非空的子节点替换即可,注意释放原先节点.

对于3.删除就好,在利用魔法的递归,将此节点(已经被置为nullptr)返回给他的父节点.

好了那么对于1.的解决办法如下:

将被删除的节点与右子树中最小值或者左子树中最大值替换(从比它小的中找个最大的,比它大的中找个最小的).

可行的理由是:对于一棵二叉树来说,最大值或最小值所在的节点的子节点数量是一个或两个.这不就转换为了2./3.种情况了嘛.

再调用处理2./3.的函数即可.

[8-15]行很像insert的查找过程.

[22-24]行是替换当前节点的值,再把那个用来替换的节点删除.

[30-40]行是在处理2./3.种情况,保存当前节点.在被替换后,释放保存节点,此处是任何删除操作的必经之处.很漂亮的处理.

 1 SearchTree CBinTree::delete_specific(ELEMENT &_data,SearchTree &_T){  2  3 if (_T)  4  {  5  Position tmp;  6  7 // Search node to delete  8 if (_data < _T->data)  9  { 10 _T->left = delete_specific(_data,_T->left); 11  } 12 else if (_data > _T->data) 13  { 14 _T->right = delete_specific(_data,_T->right); 15  } 16 // Search Done! 17 // Two chidren. 18 else if (_T->left && _T->right) 19  { 20 // Replace with smallest in right subtree. 21 // Or tmp = findMin_specific(_T->left); 22 tmp = findMin_specific(_T->right); 23 _T->data = tmp->data; 24 _T->right = delete_specific(tmp->data,_T->right); 25  } 26 // One or zero chidren. 27 else 28  { 29 tmp = _T; 30 if (!_T->left) 31  { 32 _T = _T->right; 33  } 34 else if (!_T->right) 35  { 36 _T = _T->left; 37  } 38 size--; 39 delete tmp; 40 tmp = nullptr; 41  } 42  } 43 return _T; 44 }