二叉搜索树的插入、删除与遍历

柔光的暖阳◎ 2022-06-17 01:10 168阅读 0赞

## 二叉搜索树的插入 ##

二叉搜索树是有序的，插入之后要使插入后的树还是有序的，就必须比较每个节点的值，然后再选择合适的位置插入，首先先将树的节点设计如下：

typedef int Elemtype;
    typedef struct _BstNode
    {
        Elemtype data;
        _BstNode * leftchild;
        _BstNode * rightchild;
        _BstNode * parent;
    }BstNode;

插入的方式实现了两种，一种是递归方式，一种是非递归实现。  
**非递归：**  
**购买节点：**

BstNode * BuyNode()
    {
        BstNode*node = new BstNode();
        if (node == NULL)
            exit(-1);
        memset(node, 0, sizeof(BstNode));
        return node;
    }

```
    bool Insert(BstNode*&root, Elemtype e)
    {
        if (FindValue(root, e) != NULL)
            return false;
        BstNode*node = BuyNode();
        node->data = e;
        if (root == NULL)
        {
            root = node;
            return true;
        }
        BstNode* p = root;
        BstNode*s = NULL;
        while (p != NULL&&p->data != e)
        {
            s = p;
            p = p->data > e ? p->leftchild : p->rightchild;
        }
        node->parent = s;
        if (s->data > e)
            s->leftchild = node;
        else
            s->rightchild = node;
        return true;
    }

**递归实现：**

bool Insert_e(BstNode*&root, Elemtype e,BstNode*s)//利用递归实现插入
    {
    
        if (root == NULL)
        {
            BstNode*node = BuyNode();
            node->data = e;
            node->parent = s;
            root = node;
            return true;
        }
        else if (root->data == e)
                return false;
        return root->data > e ? Insert_e(root->leftchild, e,root) : Insert_e(root->rightchild, e,root);
    }

## 二叉搜索树的删除： ##

二叉搜索树的删除分为六种情况：  
1、向空树中删除节点。  
2、删除的节点没有找到。  
3、删除的节点为叶子节点。  
4、删除的节点为单分支节点。  
5、删除的节点为单分支根节点。  
6、删除的节点为双分支节点。  
**非递归实现：**

bool ReMove(BstNode*&root, Elemtype e)
    {
        if (root == NULL)
            return true;
        BstNode*p = FindValue(root, e);
        if (p == NULL)
            return true;
        if (p->leftchild != NULL&&p->rightchild != NULL)
        {
            BstNode*tmp = Next(p);
            p->data = tmp->data;
            p = tmp;
        }
        BstNode*child = p->leftchild;
        if (child == NULL)
            child = p->rightchild;
        BstNode*pa = p->parent;
        if (pa == NULL)
            root = child;
        else
        {
            if (pa->leftchild == p)
                pa->leftchild = child;
            else
                pa->rightchild = child;
        }
        if (child != NULL)
            child->parent = pa;
        free(p);
        return true;
    }

**递归实现：**

bool ReMove_ex(BstNode* &root, ElemType e)
    {
        if (root == NULL)
            return false;
        if (root->data > e)
            return ReMove_ex(root->leftchild, e);
        if (root->data < e)
            return ReMove_ex(root->rightchild, e);
        else
        {
            if (root->leftchild != NULL&&root->rightchild != NULL)
            {
                BstNode*child = Next(root);
                root->data = child->data;
                return ReMove_ex(root->rightchild, child->data);
            }
            BstNode*p = root->leftchild == NULL ? root->rightchild : root->leftchild;
            if (p != NULL)
                p->parent = root->parent;
            free(root);
            root = p;
            return true;
        }
    }

## 二叉搜索树遍历 ##

二叉搜索树的中序遍历就是一组从小大的排序，而中序遍历有一个特点就是如果是右孩子找双亲那么其左孩子和双亲一定遍历过，那么就继续找双亲，如果双亲为空那就是根节点了 ，就不用再继续寻找了。  
**代码实现：**

static BstNode*First(BstNode*p)
    {
        while (p != NULL&&p->leftchild != NULL)
        {
            p = p->leftchild;
        }
        return p;
    }
    static BstNode*Next(BstNode*p)//这里根据中序遍历的特点实现，还可以根据二叉排序树的值得大小进行遍历
    {
        if (p == NULL )
            return NULL;
        if (p->rightchild != NULL)
            return First(p->rightchild);
        BstNode*pa = p->parent;
        while (pa != NULL&&pa->rightchild == p)
        {
            p = pa;
            pa = pa->parent;
        }
        return pa;
    }
    void InOder_e(BstNode*root)
    {
        if (root == NULL)
            return;
        for (BstNode*p = First(root); p != NULL; p = Next(p))
        {
            cout << p->data << " ";
        }
        cout << endl;
    }