二叉搜索树BST

总阅读量次

二叉搜索树(Binary Search Tree)又名二叉查找树、二叉排序树，它要么是一棵空树，要么满足以下条件:

若其左子树不为空，则左子树所有节点的值小于根节点的值；
若其右子树不为空，则其右子树所有节点值均大于他的根节点的值；
其左右子树也为二叉查找树。

一、特点

　　通过中序遍历二叉搜索树可以得到一个有序的序列。另一方面，通过对一个序列构造二叉搜索树可以将其变为有序，构造构造过程即为排序过程。

优点

　　如果BST左右子树的节点数目保持平衡，即所有非叶子节点的左右子树数目差不多，则它的搜索性能堪比二分查找；二分查找应用于以连续内存空间存储且有序的数组，而以树这种数据结构存储时，对于插入节点和删除节点则比数组这种数据结构高效很多，甚至能达到常数时间。

缺点

　　如果构造二叉搜索树时，没有选好根节点那么构造的二叉搜索树可能会成为这个样子，

这样的结构则完全失去了二叉搜索树的优势。所以要尽量让二叉搜索树保持平衡，关于保持平衡就要涉及平衡二叉搜索树(AVL)，红黑树(RBT)等数据结构，本文先不介绍。

二、实践

　　以一个公司职员管理系统为例，其底层数据结构用二叉搜索树实现，具备增加加节点，删除节点，修改节点，搜索节点基本功能，主要是实践出真知。二叉树的一个节点也为一个职员，其节点类型如下：

  typedef struct Node
  {
    struct Node *left = nullptr;            // 左子树指针
    struct Node *right = nullptr;            // 右子树指针
    string name;                        // 职员姓名
    string gender;                        // 职员性别
    string num;                            // 节点的关键字，为社保号，唯一
    string date;                            // 入职日期
    int salary = 0;                        // 薪资
    static int total;                        // 静态变量记录公司职员总人数。
    Node() {}
    Node(string na, string gen, string number, string da, int s)        // 构造方法
    {
        name.assign(na);
        gender.assign(gen);
        num.assign(number);
        date.assign(da);
        salary = s;
        total++;                            // 每构造一个对象总数加一
    }
    ~Node() {}
  } Staff;
  int Staff::total = 0;

下面是增、删、改、查的一些成员函数，分别用递归和非递归实现:

增加节点

　　即二叉搜索树增加节点，逻辑清晰：

判定二叉搜索树是否为空，是则直接加入新节点。否则执行第二步
将新节点的关键字与根节点的关键字相比，小于则进入左子树继续比较以寻找叶子节点并加入新节点，大于则进入右子树寻找加入新节点的位置，

递归

void addStaff(Staff **r, string m[])        // 传递指针的指针，可在任何地方修改指针指向的地址的内容而不用返回被改变的根节点。
{
   if(nullptr == (*r))                     // 如果二叉搜索树或节点为空，直接添加新节点。    
   {
       *r = new Staff(m, m[1], m[2], m[3], atoi(m[4].c_str()));
       cout << "添加职员成功！" << endl;
       return;
   }
   if(m[2] < (*r)->num)            // 关键字值小于根节点的关键字，新节点加在左子树里面
   {
       addStaff(&(*r)->left, m);
   }
   else                            // 关键字值大于根节点的关键字，新节点加在右子树里面
   {
       addStaff(&(*r)->right, m);
   }
}

非递归

void addStaff(Staff **r, string m[])      // 传递指针的指针，可在任何地方修改指针指向的地址的内容而不用返回。
{
  if(r == nullptr)                    // 二叉搜索树为空，直接加入节点。
  {    
      *r = new Staff(m[0], m[1], m[2], m[3], atoi(m[4].c_str()));
      cout<<"添加成功!"<<endl;
      return;
  }
  while(r != nullptr)                
  {
     if(m[2] < (*r)->num)            // 新节点关键字小于根节点，进入左子树寻找
      {
          r = &(*r)->left;
      }
      else                            // 进入右子树寻找位置
      {
          r = &(*r)->right;
      }
      if(nullptr == (*r))                
      {
          *r = new Staff(m[0], m[1], m[2], m[3], atoi(m[4].c_str()));
          cout<<"添加成功!"<<endl;
          break;
      }
  }
}

删除节点

　　删除节点情况稍微复杂一些，考虑一下：

要删除的节点只有左子树或右子树，或都没有：考虑删除的节点只有左子树，直接将其左子树赋给该节点：反之将右子树赋给该节点。如果删除的是叶子节点，则直接删除该节点(亦左子树或右子树都可以赋给它)。
要删除的节点既有左子树又有右子树，找出其右子树最小节点数据覆盖被删除的节点信息，并删除该最小节点。

递归

int deleteStaff(Staff *&r,string num)
{
  if(nullptr == r)        // BST为空
  {
      return -1;
  }
  if(r->num > num)        // 搜索左子树
  {
      return deleteStaff(r->left,num);
  }
  else if(r->num < num)   // 搜索右子树
  {
      return deleteStaff(r->right,num);
  }
  else
  {
      if(r->left == nullptr || r->right == nullptr)       // 删除的节点只有左子树或右子树
      {
          r = (r->left != nullptr)?r->left:r->right;
          return 1;
      }
      else
      {
          Staff *temp = r->right;      // 从右子树找一个最小节点并用它来代替被删除的节点，再删除该最小节点。
          while(temp->left != nullptr)
          {
              temp = temp->left;
          }
          // 覆盖信息
          r->name = temp->name;
          r->gender = temp->gender;
          r->num = temp->num;
          r->date = temp->date;
          r->salary = temp->salary;
          // 删除最小节点
          deleteStaff(r->right,temp->num);
          return 1;
      }
  }
  return -1;
}

修改节点和查询节点

　　其原理和遍历二叉搜索树相似，直接介绍递归与非递归的中序遍历。

中序遍历二叉搜索树

递归

void inOrderTraverse(Staff *r )      // 中序遍历BST
{       if(r == nullptr)
      {
          return;
      }
  if(r != nullptr) 
  {          // 递归中序遍历BST
      inOrderTraverse(r->left);
      cout << r->name << "\t" << r->gender << "\t" << r->num << "\t" << r->date << "\t" << r->salary << endl;
      inOrderTraverse(r->right);
      }
}

非递归

void inOrderTraverse(Staff *r )      //非递归 中序遍历BST
{  
  if(r == nullptr)
  {
          return;
  }
  stack<Staff*> s;
  Staff *p=r;
  while(p != nullptr || !s.empty())   // 到叶子节点或栈空
  {
      while(p != nullptr)                // 先放入相对根节点，次放其左子树，直到左子树空
      {
          s.push(p);
          p = p->left;
      }                        
      if(!s.empty())                    // 访问节点：左、根、右
      {
          p = s.top();
          cout << p->name << "\t" << p->gender << "\t" << p->num << "\t" << p->date << "\t" << p->salary << endl; 
          s.pop();
          p = p->right;
      }
  }
}

完整职员管理系统请转移至我的Github。如果有错误，万望能帮我指出来，不胜感激。

月之燃梦

完全属于自己的安静的一隅

二叉搜索树BST

一、特点

优点

缺点

二、实践

增加节点

删除节点

修改节点和查询节点

中序遍历二叉搜索树

一、 特点

优点

缺点

二、实践

增加节点

删除节点

修改节点和查询节点

中序遍历二叉搜索树

一、特点