二叉搜索树 订阅
二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构,它既有链表的快速插入与删除操作的特点,又有数组快速查找的优势;所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。 [1] 展开全文
二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构,它既有链表的快速插入与删除操作的特点,又有数组快速查找的优势;所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。 [1]
信息
概    述
一种经典的数据结构
特    点
链表的快速插入与删除操作,数组快速查找
分    类
二叉树
中文名
二叉搜索树
学    科
计算机
外文名
Binary Search Tree
二叉搜索树原理
二叉搜索树(BST)又称二叉查找树或二叉排序树。一棵二叉搜索树是以二叉树来组织的,可以使用一个链表数据结构来表示,其中每一个结点就是一个对象。一般地,除了key和卫星数据之外,每个结点还包含属性lchild、rchild和parent,分别指向结点的左孩子、右孩子和双亲(父结点)。如果某个孩子结点或父结点不存在,则相应属性的值为空(NIL)。根结点是树中唯一父指针为NIL的结点,而叶子结点的孩子结点指针也为NIL。 [2] 
收起全文
精华内容
下载资源
问答
  • 二叉搜索树

    千次阅读 2020-02-10 18:46:21
    二叉搜索树 一、 二叉搜索树的概念 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有...

    二叉搜索树

    一、 二叉搜索树的概念

    • 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
    • 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
    • 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
    • 它的左右子树也分别为二叉搜索树
      在这里插入图片描述

    二、 二叉搜索树操作

    • 二叉搜索树的查找

    在这里插入图片描述

    • 2.二叉搜索树的插入

    在这里插入图片描述

    • 3.二叉树的删除

    首先查找元素是否在二叉搜索树中,如果不存在,则返回, 否则要删除的结点可能分下面四种情况:

    • a. 要删除的结点无孩子结点
    • b. 要删除的结点只有左孩子结点
    • c. 要删除的结点只有右孩子结点
    • d. 要删除的结点有左、右孩子结点

    看起来有待删除节点有4中情况,实际情况a可以与情况b或者c合并起来,因此真正的删除过程如下:

    • 情况b:删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点
    • 情况c:删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
    • 情况d:在它的右子树中寻找最小节点即中序下的第一个结点(关键码最小)或者在它的左子树中寻找最大节点,用它的值填补到被删除节点中,再来处理该结点的删除问题
    • 4.二叉搜索树的实现
    #include <iostream>
    #include <assert.h>
    #include <stdlib.h>
    #include <string.h>
    #include <cstdio>
    using namespace std;
    
    template<class T>
    struct BSTNode
    {
      BSTNode(const T& data = T())
        :_pLeft(nullptr)
         ,_pRight(nullptr)
         ,_data(data)
      {}
    
      BSTNode<T>* _pLeft;
      BSTNode<T>* _pRight;
      T _data;
    };
    
    template<class T>
    class BSTree
    {
      typedef BSTNode<T> Node;
      public:
        BSTree()
          :_pRoot(nullptr)
        {}
    
        ~BSTree()
        {
          Destory(_pRoot);
        }
    
        Node* Find(const T& data)
        {
            assert(_pRoot);
            
            Node* cur = _pRoot;
            while(cur)
            {
              if(cur->_data == data)
              {
                return cur;
              }
              else if(cur->_data > data)
              {
                cur = cur->_pLeft;
              }
              else
              {
                cur = cur->_pRight;
              }
            }
            cout<<"this bstree is no data node!"<<endl;
            return nullptr;
        }
    
        void Print()
        {
          Print(_pRoot);
          cout<<endl;
        }
    
        bool Insert(const T& data)
        {
          if(nullptr == _pRoot)
          {
            _pRoot = new Node(data);
            return true;
          }
    
          Node* cur = _pRoot;
          Node* pParent = nullptr;
          while(cur)
          {
            pParent = cur;
            if(cur->_data > data)
            {
              cur = cur->_pLeft;
            }
            else if(cur->_data < data)
            {
              cur = cur->_pRight;
            }
            else 
            {
              return false;
            }
          }
          cur = new Node(data);
          if(pParent ->_data > data)
          {
            pParent->_pLeft = cur;
          }
          else if(pParent->_data < data)
          {
            pParent->_pRight = cur;
          }
          
          return true;
        }
    
        bool Erase(const T& data)
        {
          if(_pRoot == nullptr)
          {
            return false;
          }
    
          Node* cur = _pRoot;//指向待删除节点
          Node* pParent = nullptr;//除根结点外,指向待删除结点的父亲节点
          //注意这里的循环,pParent开始是为空的,如果待删除结点刚好为根节点,就应该另外判断,否者会出错
          while(cur)
          {
            if(cur->_data == data)
            {
              break;
            }
            else if(cur->_data > data)
            {
              pParent = cur;
              cur = cur->_pLeft;
            }
            else 
            {
              pParent = cur;
              cur = cur->_pRight;
            }
          }
          //出while循环的方法有2种,1:break出来,代表找到待删除节点cur;2:cur == nullptr 出来,代表该树内没有
          //data节点
    
          if(cur == nullptr)
          {
            perror("this tree is no data");
            return false;//没找到data的节点
          }
    
          //走到这里代表找到待删除节点,就分情况删除即可
    
          //待删除节点没有左右孩子:直接删除
          if(cur->_pRight == nullptr && cur->_pLeft == nullptr)
          {
            return RLNULL(_pRoot,pParent,cur);
          }
          //待删除节点的右孩子为空:把待删除节点的父亲节点指向待删除节点的左孩子
          else if(cur->_pRight == nullptr && cur->_pLeft != nullptr)
          {
            return RNULL(_pRoot,pParent,cur);
          }
          //待删除节点的左孩子为空:把待删除结点的父亲节点指向待删除结点的右孩子
          else if(cur->_pLeft == nullptr && cur->_pRight != nullptr)
          {
            return LNULL(_pRoot,pParent,cur);
          }
          //待删除节点的左右孩子都不为空:两种方法:1:在其左子树中找最大的节点进行替换;2:在其右子树中
          //找最小节点进行替换。然后进行删除(这里采用第2种方法)
          else 
          {
            //输出型参数
            Node* pcur;//替换节点
            Node* ppParent;//代替换节点的父亲节点
    
            //找到替换节点
            GetNode(cur,ppParent,pcur);
    
            swap(cur->_data,pcur->_data);//把待删除节点和替换节点进行交换,然后删除替换节点,
            //就把原本待删除节点左右孩子都存在转化为只有右孩子或这没有右孩子的情况(因为找的替换节点是
            //右子树中最小的节点,根据二叉搜索树的性质,该节点一定在子树的最左边,所以找到的节点要么没有
            //孩子,要么只有右孩子,不可能有左孩子)
    
            if(pcur->_pRight)//有右孩子
            {
              return LNULL(_pRoot,ppParent,pcur);
            }
    
            //没有孩子
            return RLNULL(_pRoot,ppParent,pcur);
          }
    
          return true;
        }
    
      private:
        bool RLNULL(Node*& _pRoot,Node*& pParent,Node*& cur)
        {
          if(cur == _pRoot)
          {
            delete _pRoot;
            _pRoot = nullptr;
            return true;
          }
          
          if(pParent->_pLeft == cur)
          {
            pParent->_pLeft = nullptr;
          }
          else if(pParent->_pRight == cur)
          {
            pParent->_pRight = nullptr; 
          }
    
          delete cur;
          cur = nullptr;
    
          return true;
        }
    
        bool RNULL(Node*& _pRoot,Node*& pParent,Node*& cur)
        {
          if(cur == _pRoot)
          {
            Node* pcur = _pRoot->_pLeft;
            delete _pRoot;
            _pRoot = pcur;
            return true;
          }
    
          if(pParent->_pLeft == cur)
          {
            pParent->_pLeft = cur->_pLeft;
          }
          else if(pParent->_pRight == cur)
          {
            pParent->_pRight = cur->_pLeft; 
          }
          
          delete cur;
          cur = nullptr;
          return true;
        }
    
        bool LNULL(Node*& _pRoot,Node*& pParent,Node*& cur)
        {
          if(cur == _pRoot)
          {
            Node* pcur = _pRoot->_pRight;
            delete _pRoot;
            _pRoot = pcur;
            return true;
          }
    
          if(pParent->_pLeft == cur)
          {
            pParent->_pLeft = cur->_pRight;
          }
          else if(pParent->_pRight == cur)
          {
            pParent->_pRight = cur->_pRight; 
          }
          
          delete cur;
          cur = nullptr;
          return true;
    
        }
    
        void GetNode(Node* pRoot,Node*& pParent,Node*& cur)
        {
    
          cur = Inorder(pRoot->_pRight);
    
          //如果替换节点等于子树的根节点,直接返回替换节点的父亲节点
          if(cur->_data == pRoot->_pRight->_data)
          {
           pParent = pRoot; 
          }
          else //反之进行循环查找替换节点的父亲节点
          {
            Node* p = pRoot->_pRight;
            Node* temp = Inorder(pRoot->_pRight);
    
            Node* pp = p->_pLeft;
    
            while(pp->_data != temp->_data)
            {
              p = pp;
              pp = pp->_pLeft;
            }
            pParent = p;
    
          }
        }
    
        Node* Inorder(Node* pRoot)//找到替换节点
        {
          if(pRoot)
          {
            Node* cur = pRoot->_pLeft;//如果cur为空,代表子树的根节点没有左孩子,那么就可以直接返回
            if(cur == nullptr)
            {
              return pRoot;
            }
            //反之发明会子树的最左边的节点
            Inorder(cur);
            return cur;
          }
        }
    
        void Destory(Node*& pRoot)
        {
          if(pRoot)
          {
            Destory(pRoot->_pLeft );
            Destory(pRoot->_pRight);
            delete pRoot;
            pRoot = nullptr;
          }
        }
    
        void Print(Node* _pRoot)
        {
          if(_pRoot)
          {
            Print(_pRoot->_pLeft);
            cout<<_pRoot->_data<<" ";
            Print(_pRoot->_pRight);
          }
        }
    
        Node* _pRoot;
    };
    
    
    
    展开全文
  • 1.二叉搜索树的建立 2.二叉搜索树节点的查找 3.二叉搜索树节点的删除 4.二叉搜索树的中序、后序递归遍历 5.二叉搜索树的中序、后序非递归遍历 6.二叉搜索树查找某个节点的前驱(下一个值比当前节点x大的节点)

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 40,471
精华内容 16,188
关键字:

二叉搜索树