【c++】二叉搜索树-阿里云开发者社区

1. 二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

二叉树的中序遍历就相当于从小往大排序

2.二叉搜索树的基本操作

结构体的构建

template<class K>
struct BSTreeNode
{
  BSTreeNode<K>* _left;
  BSTreeNode<K>* _right;
  K _key;
  BSTreeNode(const K& key)
    :_left(nullptr)
    , _right(nullptr)
    , _key(key)
  {
  }
};

使用初始化列表初始化变量

类封装搜索二叉树

template<class K>
class BSTree
{
  typedef BSTreeNode<K> Node;
public:
  
private:
  Node* _root = nullptr;
};

为了方便使用结构体，我们将搜索二叉树的结构体重定义为Node,对于一个搜索二叉树，我们需要定义一个变量存放二叉树根节点的地址，我们在这里相当于给初始化列表给缺省值了

二叉搜索树的插入

由于二叉搜索树是不能出现重复的，我们在遍历查找的时候，如果是第一个插入的话就申请节点，插入函数返回值表示该值是否能插入，如果是第一个节点，就能插入，return true;定义一个遍历指针，刚开始让这个指针指向头结点，然后如果指针指向的结点的值小于要插入的值，则让该指针去右子树寻找，因为右子树是比该节点的值大的。如果指针指向的结点的值大于要插入的值，则让该指针去右子树寻找.如果该指针指向的结点的值等于要插入的·值，直接返回fasle;因为二叉树不能出现重复的数，等到找到要插入值的位置，让他的父节点指向他，但是按照上述的做法，他的父节点根本没有记录到，所以我们在循环里面遍历指针在去下一个位置的时候，需要将当前位置保存在父节点里面。除此之外，需要考虑要插入的结点应该链接到父节点的左边，还是右边，我们必须判断如果要插入的结点值比父节点的值大，就链接到父节点的右边，如果比父节点小的话就链接到父亲节点的左边，然后返回true,表示可以插入

bool insert(const K& key)
    {
    if (_root == nullptr)
    {
      _root = new Node(key);
      return _root;
    }
    Node* parent = nullptr;
    Node* cur =_root;
    while (cur)
    {
      if (cur->_key < key)
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_key > key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else
      {
        return false;
      }
    }
    cur = new Node(key);
    if (parent->_key < key)
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
    return true;
  }

中序遍历

搜索二叉树的中序遍历就相当于从小到大排序，我们使用中序遍历来验证我们的插入.

因为我们的root是私有成员变量

所以我们采用一个共有的函数来调用私有的函数，这个私有的函数用来中序遍历

void _inorder()
  {
    return inorder(_root);
  
  
  }

void inorder(Node* root)
  {
    if (root == nullptr)
      return;
    inorder(root->_left);
    cout <<root->_key << " ";
    inorder(root->_right);
  }

二叉搜索树的查找

二叉树的查找和插入基本思路差不多，如果找到值一样的返回true;当遍历完没有一样的，就返回false;如果根节点是空的话就肯定没有要找的值返回false;

bool find(const K& key)
  {
    if (_root == nullptr)
    {
      return false;
    }
    Node* cur = _root;
    while (cur)
    {
      if (cur->_key < key)
      {
        cur = cur->_right;
      }
      else if (cur->_key > key)
      {
        cur = cur->_left;
 
      }
      else
      {
        return true;
      }
    }
    return false;
  
  }

测试

void test()
{
  bstree<int>st;
  int a[] = { 8,3,1,10,6,4,7,14,13 };
  for (auto e : a)
  {
    st.insert(e);
  }
  int ret=st.find(3);
  int ret1 =st.find(100);
   //st._inorder();
  cout << ret << " ";
  cout << ret1 << " ";
  
}

二叉搜索树的删除

情况1（叶子节点）

情况2（有一个孩子）

我们发现情况1可以归并到情况2中去.

情况3（有两个孩子）

bool earse(const K& key)
  {
    if (_root == nullptr)
      return false;
    Node* cur = _root;
    Node* parent = cur;
    
    while (cur)
    {   
      if (cur->_key < key)
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_key > key)
      {
        parent = cur;
        cur = cur->_left;
      }  //往上是在找值
      else//找到了
      {
    
        if (cur->_left == nullptr)//处理情况2
        {  
          
          else
          {
            if (parent->_left == cur)
            {
              parent->_left = cur->_right;
            }
            else
            {
              parent->_right = cur->_right;
            }
          }
          
          delete cur;
        }
        else if (cur->_right == nullptr)//处理情况2
        {
          
          else
          {
            if (parent->_left == cur)
            {
              parent->_left = cur->_left;
            }
            else
            {
              parent->_right = cur->_left;
            }
          }
          
          delete cur;
        }
        else//处理情况3，这里和图中不同的是去右子树找最左
        {
          Node* per = cur;
          Node* nex = cur->_right;
          while (nex->_left)
          {
            per = nex;
            nex = nex->_left;
          }
          cur->_key = nex->_key;
        
          
            per->_left = nex->_right;
          
          delete nex;
          
        }
        return true;
      }
    }
  
    return false;
  
  
  
  
  }

情况1测试

情况2测试

情况3测试

这里还有一个问题，就是如果8没有右节点的话，也会崩溃.

同理左节点也是.

代码修改如下：

bool earse(const K& key)
  {
    if (_root == nullptr)
      return false;
    Node* cur = _root;
    Node* parent = cur;
    while (cur)
    {
      if (cur->_key < key)
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_key > key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else
      {
                 if (cur->_left == nullptr)
        {
            if (cur == _root)
             {
               _root = cur->_right;
             }
             else
             {
          if (parent->_left == cur)
          {
            parent->_left = cur->_right;
          }
          else
          {
            parent->_right = cur->_right;
          }
          }
          delete cur;
        
        }
        
        else if (cur->_right == nullptr)
        { if (cur == _root)
         {
           _root = cur->_left;
         }
         else
         {
        
          if (parent->_left == cur)
          {
            parent->_left = cur->_left;
          }
          else
          {
            parent->_right = cur->_left;
          }
          }
          delete cur;
        }
        else
        {
          Node* per = cur;
          Node* nex = cur->_right;
          while (nex->_left)
          {
            per = nex;
            nex = nex->_left;
          }
          cur->_key = nex->_key;
          
          
          if (per->_left == nullptr)
          {
            per->_left = nex->_right;
          }
          else
          {
            per->_right = nex->_right;
          }
          delete nex;
        }
        return true;
      }
    }
    return false;
  }

3.源代码

tree.h

#pragma once
#include<iostream>
using namespace std;
template<class K>
struct bstreenode
{
  bstreenode <K>* _left;
  bstreenode <K>* _right;
  K _key;
  bstreenode(const K& key)
    :_left(nullptr)
    , _right(nullptr)
    , _key(key)
  {
  }
};
template<class K>
class bstree
{
  typedef bstreenode<K> Node;
public:
  bool insert(const K& key)
  {
    if (_root == nullptr)
    {
      _root = new Node(key);
      return _root;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
      if (cur->_key < key)
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_key > key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else
      {
        return false;
      }
    }
    cur = new Node(key);
    if (parent->_key < key)
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
    return true;
  }
  void _inorder()
  {
    return inorder(_root);
  }
  bool find(const K& key)
  {
    if (_root == nullptr)
    {
      return false;
    }
    Node* cur = _root;
    while (cur)
    {
      if (cur->_key < key)
      {
        cur = cur->_right;
      }
      else if (cur->_key > key)
      {
        cur = cur->_left;
      }
      else
      {
        return true;
      }
    }
    return false;
  }
  bool earse(const K& key)
  {
    if (_root == nullptr)
      return false;
    Node* cur = _root;
    Node* parent = cur;
    while (cur)
    {
      if (cur->_key < key)
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_key > key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else
      {
                 if (cur->_left == nullptr)
        {
            if (cur == _root)
             {
               _root = cur->_right;
             }
             else
             {
          if (parent->_left == cur)
          {
            parent->_left = cur->_right;
          }
          else
          {
            parent->_right = cur->_right;
          }
          }
          delete cur;
        
        }
        
        else if (cur->_right == nullptr)
        { if (cur == _root)
         {
           _root = cur->_left;
         }
         else
         {
        
          if (parent->_left == cur)
          {
            parent->_left = cur->_left;
          }
          else
          {
            parent->_right = cur->_left;
          }
          }
          delete cur;
        }
        else
        {
          Node* per = cur;
          Node* nex = cur->_right;
          while (nex->_left)
          {
            per = nex;
            nex = nex->_left;
          }
          cur->_key = nex->_key;
          
          
          if (per->_left == nullptr)
          {
            per->_left = nex->_right;
          }
          else
          {
            per->_right = nex->_right;
          }
          delete nex;
        }
        return true;
      }
    }
    return false;
  }
private:
    Node* _root = nullptr;
  void inorder(Node* root)
  {
    if (root == nullptr)
      return;
    inorder(root->_left);
    cout <<root->_key << " ";
    inorder(root->_right);
  }
};
void test()
{
  bstree<int>st;
  int a[] = { 8,3,1,10,6,4,7,14,13 };
  for (auto e : a)
  {
    st.insert(e);
  }
  st.earse(10);
  st.earse(14);
  st.earse(13);
    st.earse(8);
    st._inorder();
  
  
}

.cpp

#include"tree.h"
int main()
{
  test();
}

【c++】二叉搜索树

1. 二叉搜索树概念

2.二叉搜索树的基本操作

结构体的构建

类封装搜索二叉树

二叉搜索树的插入

中序遍历

二叉搜索树的查找

二叉搜索树的删除

3.源代码

热门文章

最新文章

相关课程

相关电子书