数据结构——二叉查找树（C语言）

骑猪看日落 2022-08-26 03:50 201阅读 0赞

## 定义： ##

二叉查找树是一棵二叉树，因此可以用链式结构来存储数据。若二叉查找树不为空，则应具有以下性质：

1.  关键字的值唯一
2.  若左子树不为空，则子树任何节点关键字值一定小于其根节点的关键字值
3.  若右子树不为空，则子树任何节点关键字值一定大于其根节点的关键字值
4.  左、右子树任然是二叉查找树

## 结构 ##

![SouthEast][]

## 二叉查找树的操作 ##

查找节点：

1.  若二叉查找树为空，则查找失败
2.  若该树非空且查找数据x等于根节点的值，则查找成功，返回根节点
3.  若该树非空且查找数据x小于根节点的值，则查找左子树，直到值相等，并返回节点
4.  若该树非空且查找数据x大于根节点的值，则查找右子树，直到值相等，并返回节点

插入节点：

1.  若二叉查找树为空，则将结点作为根节点插入
2.  若所插入节点关键字值等于根节点的值，则插入失败，并返回
3.  若所插入节点关键字值小于根节点的值，则把节点插入到左子树中
4.  若所插入节点关键字值大于根节点的值，则把节点插入到右子树中

![SouthEast 1][]

删除节点：

1.  若p结点为叶子结点，则删去该叶子结点，修改其双亲结点的指针即可。
2.  若p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点的左子树（当p是左子树）或右子树（当p是右子树）。
3.  若p结点的左子树和右子树均不空。找出节点p的后继节点y（一定在节点p的右子树中），并让y占据p的位置，且p原来右子树部分成为y新的右子树，原来p的左子树成为y新的左子树。

变形：

1.  若节点p没有左孩子（这里面包含了有右孩子或者没有右孩子）
2.  有左孩子且没有右孩子
3.  既有左孩子也有右孩子

## 完整程序 ##

函数定义：

#ifndef BINSEARTREE_H_INCLUDED
    #define BINSEARTREE_H_INCLUDED
    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #define LENGTH 11
    
    struct BinSearNode
    {
        int key;
        struct BinSearNode *left_child;
        struct BinSearNode *right_child;
        struct BinSearNode *parent;
    }Node;
    typedef struct BinSearNode *PNode;
    /*Search the node of the tree*/
    PNode Search_Tree(PNode root,int key)
    {
        PNode x=root;
        //the tree is not empty and the key is not equal
        while(NULL!=x && x->key!=key)
        {
            if(x->key<key)
                x=x->right_child;//along the right child of tree,until it is empty
            else
                x=x->left_child;//along the left child of tree,until it is empty
        }
        return x;//return the node
    }
    /*the minimum key of node in the tree*/
    PNode Minimum_Tree(PNode root)
    {
        PNode x=root;
        while(NULL!=x->left_child)
        {
            x=x->left_child;
        }
        return x;
    }
    /*the maxmum key of node in the tree*/
    PNode Maxmum_Tree(PNode root)
    {
        PNode x=root;
        while(NULL!=x->right_child)
        {
            x=x->right_child;
        }
        return x;
    }
    /*the successor node of the x*/
    PNode Successor_Tree(PNode x)
    {
        PNode y=NULL;
        //case 1:the right subtree of node x is not empty
        if(NULL!=x->right_child)
        {
            y=Minimum_Tree(x->right_child);
        }
        //case 2:the right subtree of node x is empty
        //and the node of x has a successor node y
        else
        {
            y=x->parent;
            while(NULL!=y && x==y->right_child)
            {
                x=y;
                y=y->parent;
            }
        }
        return y;
    }
    /*the predecessor node of the x*/
    PNode Predecessor_Tree(PNode x)
    {
        PNode y=NULL;
        //case 1:the left subtree of node x is not empty
        if(NULL!=x->left_child)
        {
            y=Maxmum_Tree(x->left_child);
        }
        //case 2:the left subtree of node x is empty
        //and the node of x has a predecessor node y
        else
        {
            y=x->parent;
            while(NULL!=y && x==y->left_child)
            {
                x=y;
                y=y->parent;
            }
        }
        return y;
    }
    /*insert a new node into the BST*/
    void Insert_Tree(PNode *root,int key)
    {
        PNode x=*root;
        PNode y=NULL;
        PNode z=(PNode)malloc(sizeof(Node));
        if(NULL==z)
        {
            printf("malloc the z is failed.");
            exit(1);
        }
        //initial the node of z
        z->key=key;
        z->left_child=z->right_child=z->parent=NULL;
        //Find the location node of y to insert the node of z
        while(NULL!=x)
        {
            y=x;
            if(z->key<x->key)
                x=x->left_child;
            else
                x=x->right_child;
        }
        //insert the node of z
        z->parent=y;
        if(NULL==y)
            *root=z;//tree was empty
        else
        {
            if(z->key<y->key)
                y->left_child=z;
            else
                y->right_child=z;
        }
    }
    void Transplant(PNode *root,PNode u,PNode v)
    {
        if(NULL==u->parent)
            *root=v;
        else
        {
            if(u==u->parent->left_child)
                u->parent->left_child=v;
            else
                u->parent->right_child=v;
        }
        if(NULL!=v)
            v->parent=u->parent;
    }
    /*delete a node in the binary search tree*/
    void Delete_Tree(PNode *root,int key)
    {
        //Find the node you want to delete
        PNode p=Search_Tree(*root,key);
        if(NULL==p->left_child)
            Transplant(root,p,p->right_child);
        else
        {
            if(NULL==p->right_child)
                Transplant(root,p,p->left_child);
            else
            {
                PNode y=Successor_Tree(*root);
                if(y->parent!=p)
                {
                    Transplant(root,y,y->right_child);
                    y->right_child=p->right_child;
                    y->right_child->parent=y;
                }
                Transplant(root,p,y);
                y->left_child=p->left_child;
                y->left_child->parent=y;
            }
        }
    }
    /*print the key of binary search tree*/
    void ioder_Tree(PNode root)
    {
        if(NULL!=root)
        {
            ioder_Tree(root->left_child);
            printf("  %d",root->key);
            ioder_Tree(root->right_child);
        }
    }
    #endif // BINSEARTREE_H_INCLUDED

测试程序:

#include <stdio.h>
    #include <stdlib.h>
    #include"BinSearTree.h"
    
    int main()
    {
        int i;
        int Arr[LENGTH]={16,6,20,2,7,19,22,1,4,11,8};
        PNode root=NULL;
        PNode p=NULL;
        for(i=0;i<LENGTH;i++)
        {
            Insert_Tree(&root,Arr[i]);
        }
        ioder_Tree(root);
        printf("\n");
        //printf("Hello world!\n");
        Delete_Tree(&root,11);
        ioder_Tree(root);
        printf("\n");
        p=Maxmum_Tree(root);
        printf("The Maxmum of node is:%d\n",p->key);
        p=Minimum_Tree(root);
        printf("The Minimum of node is:%d\n",p->key);
        return 0;
    }

[SouthEast]: /images/20220824/6c096a8d975d4178a7a137bf11fab663.png
[SouthEast 1]: /images/20220824/2f76e16aa5d341b3a08a6f10697907fb.png