c++ 搜索二叉树 插入，删除，遍历操作

搜索二叉树是一种具有良好排序和查找性能的二叉树数据结构，包括多种操作，本篇只介绍插入，排序（遍历），和删除操作，重点是删除操作比较复杂，用到的例子也是本人亲自画的

用到的测试图数据例子

第一、构建节点

 template <typename T> class BST;
 template <typename T> class BSTNode {
 public:
     friend class BST<T>;
     BSTNode() {
         lChild = rChild = parent = NULL;
         data = NULL;
     }
     BSTNode(T d) {
         lChild = rChild = parent = NULL;
         data = d;
     }
 private:
     BSTNode<T> *lChild, *rChild, *parent;
     T data;
 };

第二、二叉树头文件定义

 template<typename T> class BST {
 public:
     BST() { } 

     //插入操作
     void insert(BSTNode<T>*node);

     //二叉查找树的中序遍历，就相当于排序了
     void inSort(BSTNode<T>*node);

     //按节点删除
     void deleteNode(BSTNode<T>* node);

     //按数值删除
     void deleteNode(const T& t);

     BSTNode<T>* search(T key);
     BSTNode<T>* root=NULL;

 private:
     int count;
 };

第三、搜索二叉树的插入

1）如果二叉树查找树为空节点，则插入节点就为根节点

2）如果二叉查找树为非空节点，就需要先找到待插入节点，查找原则就是从根节点开始，如果大于根就右边走，小于根就左边走，直到找到合适节点，

下面代码中的最终找到的temp 就是待插入节点.

 template<typename T>
 void BST<T>::insert(BSTNode<T>* node)
 {
     BSTNode<T>* curr, *temp = NULL;
     curr = root;
     while (NULL!= curr) //遍历二叉树，找到应该插入的父节点
     {
         temp = curr;
         if (node->data>curr->data)
         {
             curr = curr->rChild;
         }
         else {
             curr = curr->lChild;
         }
     }
     node->parent = temp;//temp 代码当前最后遍历的node，设置node->parent为该节点
     if (temp==NULL)
     {
         root = node;
         count++;
     }
     else {
         if (node->data<temp->data)
         {
             temp->lChild = node;
             count++;
         }
         else {
             temp->rChild = node;
             count++;
         }
     }
 }

第四、搜索二叉树的删除

删除包含多种情况，

1. 如果节点没有子女，修改其父节点指针为NULL，删除即可

2. 如果该节点有左孩子情况，修改其父亲节点的指针和其左孩子的parent指针即可

3. 如果该节点有右孩子情况，修改其父亲节点的指针和其右孩子的parent指针即可

4.如果同时有左右孩子的情况，情况比较复杂，一般有2种方法处理

1） 用节点右边孩子的最小值替换该节点，其他节点位置保持不变（本篇用这种方法）

2）用节点左边孩子的最大值替换该节点，其他节点位置保持不变

后面测试例子是删除18 node，通过程序找到右边最小值20，用20 替换18，其他节点位置保持不动。

 template<typename T>
 inline void BST<T>::deleteNode(BSTNode<T>* node)
 {
     BSTNode<T>*p = node->parent;//获取node的父节点，这里很重要
     if (node->lChild==NULL && node->rChild==NULL) //叶子节点直接删除
     {
         if (node==node->parent->lChild)
         {
             node->parent->lChild = NULL;
         }
         else {
             node->parent->rChild = NULL;
         }
         delete node;
         count--;
     }
     else if (node->rChild != NULL && node->lChild == NULL) {//存在右孩子
         if (p==NULL)//说明节点为根节点
         {
             root = node->rChild;
             count--;
         }
         else {
             node->rChild->parent = p;
             if (p->lChild==node) //判断是父节点的左孩子还是右孩子
             {
                 p->lChild = node->rChild;
             }
             else {
                 p->rChild = node->rChild;
             }
             delete node;
             count--;
         }
     }
     else if (node->lChild!=NULL && node->rChild==NULL)//存在左孩子
     {
         if (p==NULL)
         {
             root = root->lChild;
             count--;
         }
         else {
             node->lChild->parent = p;
             if (p->lChild==node)
             {
                 p->lChild = node->lChild;
             }
             else {
                 p->rChild = node->lChild;
             }
             delete node;
             count--;
         }
     }
     else {
         BSTNode<T>*left, *curp=NULL;
         left = node->rChild; //本方案是找右侧最小值，替换node节点，其他节点保持不动即可
         while (left!=NULL)
         {
             curp = left;
             left = left->lChild;
         }

         if (curp->rChild!=NULL)
         {
             if (curp->lChild==curp)
             {
                 curp->parent->lChild = curp->rChild;
             }
             else {
                 curp->parent->rChild = curp->rChild;
             }
         }
         else {
             if (curp->parent->lChild==curp)
             {
                 curp->parent->lChild = NULL;
             }
             else {
                 curp->parent->rChild = NULL;
             }
             //curp->parent->lChild = NULL;
         }
         //替curp 替换 node
         curp->parent = p;
         curp->lChild = node->lChild;
         curp->rChild = node->rChild;

         if (p->lChild==node)//判断node 是p 的左孩子还是右孩
         {
             p->lChild = curp;
         }
         else {
             p->rChild = curp;
         }
         delete node;
         count--;
     }
 }

第五、二叉树的搜索查找

由于搜索二叉树本身是已经排序好的，查找过程相对简单，从根节点，逐个排查，大于根向右，小于根向左，直到叶子节点.

template<typename T>
inline BSTNode<T>* BST<T>::search(T k)
{
    BSTNode<T>*node = root;
    while (node!=NULL)
    {
        if (k<node->data)
        {
            node = node->lChild;
        }
        else if (k> node->data)
        {
            node = node->rChild;
        }
        else {
            break;
        }
    }
    return node;
}

第六、二叉搜索树的排序

根据二叉所有树的特性，这里所谓排序，其实就是二叉树的中序遍历，其他的几种遍历不在这里赘述，知识调整下结构即可

template<typename T>
void BST<T>::inSort(BSTNode<T>* node)
{
    if (node!=NULL)
    {
        inSort(node->lChild);
        std::cout << node->data<<",";
        inSort(node->rChild);
    }
}

第七、测试程序

 #include "pch.h"
 #include <iostream>
 #include "BSTree.h"
 using namespace std;

 int main()
 {
     // 树结构示意
     //     30
     //    /  \
     //  15   25
     // /  \
     //9    18
     //   /   \
     //  16   25
     //      /  \
     //    20    26
     BST<int> sbt;
     sbt.insert(new BSTNode<int>());
     sbt.insert(new BSTNode<int>());
     sbt.insert(new BSTNode<int>());
     sbt.insert(new BSTNode<int>());
     sbt.insert(new BSTNode<int>());
     sbt.insert(new BSTNode<int>());
     sbt.insert(new BSTNode<int>());
     sbt.insert(new BSTNode<int>());
     sbt.insert(new BSTNode<int>());

     cout << "搜索树排序后:";
     sbt.inSort(sbt.root);

     sbt.deleteNode();

     cout << endl << "删除18 后排序:";

     sbt.inSort(sbt.root);
 }

测试结果

所有完整程序代码

 #pragma once
 template <typename T> class BST;
 template <typename T> class BSTNode {
 public:
     friend class BST<T>;
     BSTNode() {
         lChild = rChild = parent = NULL;
         data = NULL;
     }
     BSTNode(T d) {
         lChild = rChild = parent = NULL;
         data = d;
     }
 private:
     BSTNode<T> *lChild, *rChild, *parent;
     T data;
 };

 template<typename T> class BST {
 public:
     BST() { } 

     //插入操作
     void insert(BSTNode<T>*node);

     //二叉查找树的中序遍历，就相当于排序了
     void inSort(BSTNode<T>*node);

     //按节点删除
     void deleteNode(BSTNode<T>* node);

     //按数值删除
     void deleteNode(const T& t);

     BSTNode<T>* search(T key);
     BSTNode<T>* root=NULL;

 private:
     int count;
 };

 template<typename T>
 void BST<T>::insert(BSTNode<T>* node)
 {
     BSTNode<T>* curr, *temp = NULL;
     curr = root;
     while (NULL!= curr) //遍历二叉树，找到应该插入的父节点
     {
         temp = curr;
         if (node->data>curr->data)
         {
             curr = curr->rChild;
         }
         else {
             curr = curr->lChild;
         }
     }
     node->parent = temp;//temp 代码当前最后遍历的node，设置node->parent为该节点
     if (temp==NULL)
     {
         root = node;
         count++;
     }
     else {
         if (node->data<temp->data)
         {
             temp->lChild = node;
             count++;
         }
         else {
             temp->rChild = node;
             count++;
         }
     }
 }

 template<typename T>
 void BST<T>::inSort(BSTNode<T>* node)
 {
     if (node!=NULL)
     {
         inSort(node->lChild);
         std::cout << node->data<<",";
         inSort(node->rChild);
     }
 }

 template<typename T>
 inline void BST<T>::deleteNode(BSTNode<T>* node)
 {
     BSTNode<T>*p = node->parent;//获取node的父节点，这里很重要
     if (node->lChild==NULL && node->rChild==NULL) //叶子节点直接删除
     {
         if (node==node->parent->lChild)
         {
             node->parent->lChild = NULL;
         }
         else {
             node->parent->rChild = NULL;
         }
         delete node;
         count--;
     }
     else if (node->rChild != NULL && node->lChild == NULL) {//存在右孩子
         if (p==NULL)//说明节点为根节点
         {
             root = node->rChild;
             count--;
         }
         else {
             node->rChild->parent = p;
             if (p->lChild==node) //判断是父节点的左孩子还是右孩子
             {
                 p->lChild = node->rChild;
             }
             else {
                 p->rChild = node->rChild;
             }
             delete node;
             count--;
         }
     }
     else if (node->lChild!=NULL && node->rChild==NULL)//存在左孩子
     {
         if (p==NULL)
         {
             root = root->lChild;
             count--;
         }
         else {
             node->lChild->parent = p;
             if (p->lChild==node)
             {
                 p->lChild = node->lChild;
             }
             else {
                 p->rChild = node->lChild;
             }
             delete node;
             count--;
         }
     }
     else {
         BSTNode<T>*left, *curp=NULL;
         left = node->rChild; //本方案是找右侧最小值，替换node节点，其他节点保持不动即可
         while (left!=NULL)
         {
             curp = left;
             left = left->lChild;
         }

         if (curp->rChild!=NULL)
         {
             if (curp->lChild==curp)
             {
                 curp->parent->lChild = curp->rChild;
             }
             else {
                 curp->parent->rChild = curp->rChild;
             }
         }
         else {
             if (curp->parent->lChild==curp)
             {
                 curp->parent->lChild = NULL;
             }
             else {
                 curp->parent->rChild = NULL;
             }
             //curp->parent->lChild = NULL;
         }
         //替curp 替换 node
         curp->parent = p;
         curp->lChild = node->lChild;
         curp->rChild = node->rChild;

         if (p->lChild==node)//判断node 是p 的左孩子还是右孩
         {
             p->lChild = curp;
         }
         else {
             p->rChild = curp;
         }
         delete node;
         count--;
     }
 }

 template<typename T>
 inline void BST<T>::deleteNode(const T & k)
 {
     BSTNode<T>*node = search(k);
     if (node!=NULL)
     {
         deleteNode(node);
     }
 }

 template<typename T>
 inline BSTNode<T>* BST<T>::search(T k)
 {
     BSTNode<T>*node = root;
     while (node!=NULL)
     {
         if (k<node->data)
         {
             node = node->lChild;
         }
         else if (k> node->data)
         {
             node = node->rChild;
         }
         else {
             break;
         }
     }
     return node;
 }

BSTree.h