您的位置: 首页  >  文章  >  二叉搜索树

二叉搜索树

分类: 文章 • 2023-11-21 17:42:10

定义

二叉搜索树(Binary Search Tree)或称二叉查找树，也称二叉排序树(Binary Sort Tree)。它或者是一棵空树，或者是具有下列性质的二叉树：
  1. 若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  3. 左、右子树也分别为二叉搜索树；

性质

二叉搜索树与普通二叉树相比，有一些优秀的特征或性质：
  1. 由于节点是有序排放的：左子树<根节点<右子树。故在查找一个节点的时候，只需先和根节点比较，再决定是进入左子树还是右子树查找。而普通二叉树需要一个一个地遍历。
  2. 查找、插入的时间复杂度是O(h)，h是树的高度。即当树的高度尽量低(比较平衡)时，效率高。

算法解释

不得不说，非线性结构的操作确实难于线性结构的，有些算法的逻辑比较复杂。下面对代码中给出的部分算法进行解释，便于阅读。
  1. 构造方法：BinarySearchTree();建树的过程就是一个插入的过程，所以插入操作是重要的。
  2. 求叶子节点数：int leaf();按某种方式遍历树，若左右孩子皆为空，即为叶子节点。代码中是按中序遍历的。
  3. 查找指定节点：bool search(ElemType);根据二叉搜索树节点的分布特点，查找只需在左或右子树中进行，并且插入树中已有的节点也算插入失败。插入操作逻辑比较清楚，代码易看懂。
  4. 获取指定节点的前驱：BTNode* predecessor(ElemType);这个操作在普通二叉树中是没有的。在二叉搜索树中，某节点的前驱指的是中序遍历时的前驱。故该操作本质上是一个中序遍历的过程。稍微不同的是，在遍历的过程中需要记录最近一次遍历的节点plastVisit，并判断当前访问的节点是否是指定节点。若是，则返回plastVisit。
  5. 获取后继和获取前驱的道理是一样的。
  6. 获取最小节点：BTNode* minimum();二叉搜索树中的最小节点一定是位于左子树(如果存在)。于是，不断遍历左子树即可，比较简单。
  7. 获取最大节点：BTNode* maximum();二叉搜索树中的最大节点一定是位于右子树(如果存在)。于是，不断遍历右子树即可，比较简单。
  8. 插入节点：bool insertNode(ElemType);插入的过程本质上也是查找，需要记住的是：新节点会插入到叶子节点处。
  9. 遍历：void traverse();二叉搜索树的遍历可以是多样的，各种遍历方式也在上一篇二叉树中实现了，这里只给出中序遍历。因为，对一棵二叉搜索树进行中序遍历会得到节点从小到大的排序序列。
  10. 删除节点：bool deleteNode(ElemType);删除的规则是这样的：
  • 若待删节点无左子树，则用其右子树的根节点替换它。
  • 若待删节点有左子树，则在左子树中寻找中序遍历的最后一个节点，用该节点替换它。
删除规则比较好看懂，但具体实施时，细节繁多，很不容易。这也是所有操作中最复杂的。画图理解：
二叉搜索树
其它操作在上一篇二叉树中已有所解释，不再赘述。具体细节还得看代码，代码较长，建议以方法为单位来理解，

代码

类定义

[cpp] view plain copy
  1. #include<iostream>  
  2. #include<iomanip>  
  3. #include<stack>  
  4. #include<queue>  
  5. using namespace std;  
  6. typedef int ElemType;  
  7. //二叉树节点  
  8. class BTNode   //Binary Tree Node  
  9. {  
  10. public:  
  11.     ElemType data;  
  12.     BTNode* lchild;   //左孩子  
  13.     BTNode* rchild;   //右孩子  
  14.     BTNode(ElemType d, BTNode* left = NULL, BTNode* right = NULL)  
  15.         :data(d), lchild(left), rchild(right){}  
  16. };  
  17. //二叉搜索树  
  18. class BinarySearchTree  
  19. {  
  20. private:  
  21.     //树根  
  22.     BTNode* Root;  
  23.     //节点总数  
  24.     int size;  
  25. public:  
  26.     //构造方法  
  27.     BinarySearchTree();  
  28.     //析构方法  
  29.     ~BinarySearchTree();  
  30.     //判断树空  
  31.     bool empty()  
  32.     {return Root == NULL;}  
  33.     //求节点总数  
  34.     int getSize()  
  35.     {return size;}  
  36.     //求叶子节点数  
  37.     int leaf();  
  38.     //查找  
  39.     bool search(ElemType);  
  40.     //获取父节点  
  41.     BTNode* parent(ElemType);  
  42.     //获取前驱  
  43.     BTNode* predecessor(ElemType);  
  44.     //获取后继  
  45.     BTNode* successor(ElemType);  
  46.     //获取最小节点  
  47.     BTNode* minimum();  
  48.     //获取最大节点  
  49.     BTNode* maximum();  
  50.     //插入新节点  
  51.     bool insertNode(ElemType);  
  52.     //删除节点  
  53.     bool deleteNode(ElemType);  
  54.     //中序遍历  
  55.     void traverse()  
  56.     {inOrderWithoutRecursion();}  
  57.     void inOrderWithoutRecursion();  
  58. };  

类实现

[cpp] view plain copy
  1. //构造方法  
  2. BinarySearchTree::BinarySearchTree()  
  3. {  
  4.     size = 0;  
  5.     Root = NULL;  
  6.     ElemType data;  
  7.     cout << "建树，输入节点，输入0结束：";  
  8.     while (cin >> data && data)  
  9.         insertNode(data);  
  10. }  
  11. //析构方法  
  12. BinarySearchTree::~BinarySearchTree()  
  13. {  
  14.     if (!empty())  
  15.     {  
  16.         queue<BTNode*> q;  
  17.         q.push(Root);  
  18.         BTNode* p = NULL;  
  19.         while (!q.empty())  
  20.         {  
  21.             p = q.front();  
  22.             q.pop();  
  23.             //左孩子不为空，则左孩子入队  
  24.             if (p->lchild)  
  25.                 q.push(p->lchild);  
  26.             //右孩子不为空，则右孩子入队  
  27.             if (p->rchild)  
  28.                 q.push(p->rchild);  
  29.             //释放内存  
  30.             delete p;  
  31.         }  
  32.     }  
  33. }  
  34. //求叶子节点数  
  35. int BinarySearchTree::leaf()  
  36. {  
  37.     int num = 0;  
  38.     //按中序遍历  
  39.     if (!empty())  
  40.     {  
  41.         stack<BTNode*> s;  
  42.         BTNode* p = Root;  
  43.         while (!s.empty() || p)  
  44.         {  
  45.             if (p)  
  46.             {  
  47.                 s.push(p);  
  48.                 p = p->lchild;  
  49.             }  
  50.             else  
  51.             {  
  52.                 p = s.top();  
  53.                 s.pop();  
  54.                 //左右子树均为空，则为叶子节点  
  55.                 if (p->lchild == NULL && p->rchild == NULL)  
  56.                     num++;  
  57.                 p = p->rchild;  
  58.             }  
  59.         }  
  60.     }  
  61.     return num;  
  62. }  
  63. //查找  
  64. bool BinarySearchTree::search(ElemType data)  
  65. {  
  66.     if (!empty())  
  67.     {  
  68.         BTNode* p = Root;  
  69.         while (p)  
  70.         {  
  71.             if (data == p->data)  
  72.                 return true;  
  73.             else if (data < p->data)  
  74.                 p = p->lchild;  
  75.             else  
  76.                 p = p->rchild;  
  77.         }  
  78.     }  
  79.     //树空或查找失败  
  80.     return false;  
  81. }  
  82. BTNode* BinarySearchTree::parent(ElemType data)  
  83. {  
  84.     if (!empty())  
  85.     {  
  86.         //根节点的父节点为空  
  87.         if (Root->data == data)  
  88.             return NULL;  
  89.         stack<BTNode*> s;  
  90.         BTNode* p = Root;  
  91.         while (!s.empty() || p)  
  92.         {  
  93.             if (p)  
  94.             {  
  95.                 s.push(p);  
  96.                 p = p->lchild;  
  97.             }  
  98.             else  
  99.             {//左子树访问完后，访问右子树  
  100.                 p = s.top();  
  101.                 s.pop();  
  102.                 if ((p->lchild && p->lchild->data == data) || (p->rchild && p->rchild->data == data))  
  103.                     return p;  
  104.                 p = p->rchild;  
  105.             }  
  106.         }  
  107.     }  
  108.     return NULL;  
  109. }  
  110. //获取前驱  
  111. BTNode* BinarySearchTree::predecessor(ElemType data)  
  112. {  
  113.     BTNode* pcur, *plastVisit;  
  114.     pcur = plastVisit = NULL;  
  115.     if (!empty())  
  116.     {  
  117.         stack<BTNode*> s;  
  118.         pcur = Root;  
  119.         while (!s.empty() || pcur)  
  120.         {  
  121.             if (pcur)  
  122.             {  
  123.                 //plastVisit = pcur;  
  124.                 s.push(pcur);  
  125.                 pcur = pcur->lchild;  
  126.             }  
  127.             else  
  128.             {  
  129.                 pcur = s.top();  
  130.                 s.pop();  
  131.                 if (pcur->data == data)  
  132.                     return plastVisit;  
  133.                 else  
  134.                     plastVisit = pcur;  
  135.                 pcur = pcur->rchild;  
  136.             }  
  137.         }  
  138.     }  
  139.     return plastVisit;  
  140. }  
  141. //获取后继  
  142. BTNode* BinarySearchTree::successor(ElemType data)  
  143. {  
  144.     BTNode* pcur = NULL;  
  145.     pcur = Root;  
  146.     if (!empty())  
  147.     {  
  148.         stack<BTNode*> s;  
  149.         while (!s.empty() || pcur)  
  150.         {  
  151.             if (pcur)  
  152.             {  
  153.                 s.push(pcur);  
  154.                 pcur = pcur->lchild;  
  155.             }  
  156.             else  
  157.             {  
  158.                 pcur = s.top();  
  159.                 s.pop();  
  160.                 if (pcur->data == data)  
  161.                     return pcur->rchild;  
  162.                 pcur = pcur->rchild;  
  163.             }  
  164.         }  
  165.     }  
  166.     //空树  
  167.     return NULL;  
  168. }  
  169. //获取最小节点  
  170. BTNode* BinarySearchTree::minimum()  
  171. {  
  172.     //最小节点在左子树最下边  
  173.     if (!empty())  
  174.     {  
  175.         BTNode* p = Root;  
  176.         while (p->lchild)  
  177.             p = p->lchild;  
  178.         return p;  
  179.     }  
  180.     //树空  
  181.     return NULL;  
  182. }  
  183. //获取最大节点  
  184. BTNode* BinarySearchTree::maximum()  
  185. {  
  186.     //最大节点在右子树最下边  
  187.     if (!empty())  
  188.     {  
  189.         BTNode* p = Root;  
  190.         while (p->rchild)  
  191.             p = p->rchild;  
  192.         return p;  
  193.     }  
  194.     //树空  
  195.     return NULL;  
  196. }  
  197. //插入新节点  
  198. bool BinarySearchTree::insertNode(ElemType data)  
  199. {  
  200.     /* 
  201.      新节点都会被插入到叶子处 
  202.      插入一般不会失败，除非是插入了重复节点。 
  203.     */  
  204.     if (Root == NULL)  
  205.     {  
  206.         Root = new BTNode(data);  
  207.         size++;  
  208.         return true;  
  209.     }  
  210.     else  
  211.     {  
  212.         BTNode* p = Root;  
  213.         while (true)  
  214.         {  
  215.             if (data < p->data)  
  216.             {  
  217.                 //如果有左子树，则继续遍历左子树  
  218.                 if (p->lchild)  
  219.                     p = p->lchild;  
  220.                 else  
  221.                 {//否则，插入节点，下同  
  222.                     p->lchild = new BTNode(data);  
  223.                     break;  
  224.                 }  
  225.             }  
  226.             else if (data > p->data)  
  227.             {  
  228.                 if (p->rchild)  
  229.                     p = p->rchild;  
  230.                 else  
  231.                 {  
  232.                     p->rchild = new BTNode(data);  
  233.                     break;  
  234.                 }  
  235.             }  
  236.             else//遇到重复节点  
  237.                 return false;  
  238.         }  
  239.         //插入新节点成功，节点总数加一  
  240.         size++;  
  241.         return true;  
  242.     }  
  243. }  
  244. //删除节点  
  245. bool BinarySearchTree::deleteNode(ElemType data)  
  246. {  
  247.     /* 
  248.     删除规则 
  249.     1.若待删节点无左子树，则用其右子树的根节点替换它。 
  250.     2.若待删节点有左子树，则在左子树中寻找中序遍历的最后一个节点，用该节点替换它。 
  251.     */  
  252.     if (!empty())  
  253.     {  
  254.         //树中无此节点，删除失败  
  255.         if (!search(data))  
  256.             return false;  
  257.         /* 
  258.         p:待删结点 
  259.         Parent:待删除节点的父节点 
  260.         temp:替换节点 
  261.         tempp:替换节点的父节点 
  262.         */  
  263.         BTNode* p, *Parent, *temp, *tempp;  
  264.         p = Parent = temp = tempp = NULL;  
  265.         //获取待删除节点的父节点  
  266.         Parent = parent(data);  
  267.         //根据父节点，确定待删结点  
  268.         if (Parent->lchild && Parent->lchild->data == data)  
  269.             p = Parent->lchild;  
  270.         else  
  271.             p = Parent->rchild;  
  272.         //如果左子树不为空，查找其中序遍历的最后一个节点  
  273.         if (p->lchild)  
  274.         {  
  275.             temp = p->lchild;  
  276.             while (temp->rchild)  
  277.             {  
  278.                 tempp = temp;  
  279.                 //不断遍历右子树  
  280.                 temp = temp->rchild;  
  281.             }  
  282.             //如果p的左孩子即是替换节点  
  283.             if (tempp == NULL)  
  284.                 p->lchild = temp->lchild;  
  285.             else//替换节点的左子树作为其父节点的右子树(这句难以理解，需要多想想)  
  286.                 tempp->rchild = temp->lchild;  
  287.             //替换节点继承待删结点的左右孩子  
  288.             temp->lchild = p->lchild;  
  289.             temp->rchild = p->rchild;  
  290.         }  
  291.         else  
  292.             temp = p->rchild;  
  293.         //替换节点替换掉待删结点(这也是为什么需要找到待删结点的父节点)  
  294.         if (Parent == NULL)  //待删结点恰为根节点  
  295.             Root = temp;  
  296.         else if (Parent->lchild == p)  //待删结点本身处于左子树  
  297.             Parent->lchild = temp;  
  298.         else//待删结点本身处于右子树  
  299.             Parent->rchild = temp;  
  300.         //删除待删结点  
  301.         delete p;  
  302.         //节点总数减一  
  303.         size--;  
  304.         return true;  
  305.     }  
  306.     //树空  
  307.     return false;  
  308. }  
  309. //中序遍历  
  310. void BinarySearchTree::inOrderWithoutRecursion()  
  311. {  
  312.     if (!empty())  
  313.     {  
  314.         stack<BTNode*> s;  
  315.         BTNode* p = Root;  
  316.         while (!s.empty() || p)  
  317.         {  
  318.             if (p)  
  319.             {  
  320.                 s.push(p);  
  321.                 p = p->lchild;  
  322.             }  
  323.             else  
  324.             {  
  325.                 p = s.top();  
  326.                 s.pop();  
  327.                 cout << setw(4) << p->data;  
  328.                 p = p->rchild;  
  329.             }  
  330.         }  
  331.         cout << endl;  
  332.     }  
  333. }  

主函数

[cpp] view plain copy
  1. int main()  
  2. {  
  3.     cout << "******二叉搜索树***by David***" << endl;  
  4.     BinarySearchTree tree;  
  5.     cout << "中序遍历" << endl;  
  6.     tree.traverse();  
  7.     cout << "树中节点总数 " << tree.getSize() << endl;  
  8.     cout << "叶子节点数 " << tree.leaf() << endl;  
  9.     BTNode* p = NULL;  
  10.     p = tree.minimum();  
  11.     p ? cout << "最小节点是 " << p->data << endl : cout << "树空！" << endl;  
  12.     p = tree.maximum();  
  13.     p ? cout << "最大节点是 " << p->data << endl : cout << "树空！" << endl;  
  14.     ElemType data = 2;  
  15.     cout << endl << "查找节点 " << data << endl;  
  16.     if (tree.search(data))  
  17.     {  
  18.         cout << "节点 " << data << " 查找成功！" << endl;  
  19.         p = tree.predecessor(data);  
  20.         p ? cout << "节点 " << data << " 的前驱是 " << p->data << endl : cout << "无前驱！" << endl;  
  21.         p = tree.successor(data);  
  22.         p ? cout << "节点 " << data << " 的后继是 " << p->data << endl : cout << "无后继！" << endl;  
  23.     }  
  24.     else  
  25.         cout << "节点 " << data << "不在树中！" << endl;  
  26.     data = 6;  
  27.     cout << endl <<"删除节点 " << data << endl;  
  28.     if (tree.deleteNode(data))  
  29.     {  
  30.         cout << "删除成功！" << endl;  
  31.         cout << "中序遍历" << endl;  
  32.         tree.traverse();  
  33.         cout << "树中节点总数 " << tree.getSize() << endl;  
  34.         cout << "叶子节点数 " << tree.leaf() << endl;  
  35.         data = 5;  
  36.         cout << endl << "查找节点 " << data << endl;  
  37.         if (tree.search(data))  
  38.         {  
  39.             cout << "节点 " << data << " 查找成功！" << endl;  
  40.             p = tree.predecessor(data);  
  41.             p ? cout << "节点 " << data << " 的前驱是 " << p->data << endl : cout << "无前驱！" << endl;  
  42.             p = tree.successor(data);  
  43.             p ? cout << "节点 " << data << " 的后继是 " << p->data << endl : cout << "无后继！" << endl;  
  44.         }  
  45.         else  
  46.             cout << "节点 " << data << "不在树中！" << endl;  
  47.     }  
  48.     else  
  49.         cout << "删除失败！" << endl;  
  50.     cout << endl;  
  51.     system("pause");  
  52.     return 0;  
  53. }  

运行

二叉搜索树二叉搜索树

算法优化

插入算法的一个优化版本
[cpp] view plain copy
  1. //插入新节点  
  2. bool BinarySearchTree::insertNode(ElemType data)  
  3. {  
  4.     BTNode *parent, *child;  
  5.     parent = NULL;  
  6.     child = Root;  
  7.     while (child)  
  8.     {  
  9.         parent = child;  
  10.         if (data < child->data)  
  11.             child = child->lchild;  
  12.         else if (data > child->data)  
  13.             child = child->rchild;  
  14.         else//插入相同关键字的节点，返回false  
  15.             return false;  
  16.     }  
  17.     //此时parent要么为空，要么就是叶子节点  
  18.     if (parent == NULL)//空树  
  19.         Root = new BTNode(data);  
  20.     else if (data < parent->data)  
  21.         parent->lchild = new BTNode(data);  
  22.     else  
  23.         parent->rchild = new BTNode(data);  
  24.     size++;  
  25.     return true;  
  26. }  

相关推荐