二叉排序树

r囧r小猫 2022-06-16 08:58 147阅读 0赞

二叉排序树（Binary Sort Tree）性质：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

#include <stdio.h>
    #include <stdlib.h>
    
    
    typedef struct BinSortTree{
        struct BinSortTree *lChild;
        struct BinSortTree *rChild;
        int num;
    }BinSortTree;               //节点
    
    
    void CreateBinSortTree(BinSortTree **Node,int Num);
    void InitNode(BinSortTree **Node);
    void PreOrderTraverse(BinSortTree *Node);
    void InOrderTraverse(BinSortTree *Node);
    void leaf_sum(BinSortTree *Node,int *Sum);
    int  BinaryTreeHeight(BinSortTree *Node);
    
    int main()
    {
        int a[10] = {49,29,9,18,28,5,7,55,80,100};  //for debuging
        BinSortTree *root = NULL;           //根节点
        InitNode(&root);                    //初始化根节点
        for(int i = 0; i < 10;++i)
        {
           CreateBinSortTree(&root,a[i]);       //创建二叉树
        }
    
        InOrderTraverse(root);              //中序遍历二叉树
        int leafNum = 0;                    //叶子节点
        leaf_sum(root,&leafNum);            //后序遍历二叉树找所有叶子节点
        printf("\nleaf Numbers : %d\n",leafNum);
    
        int Height = 0;
        Height = BinaryTreeHeight(root);
        printf("Height of Tree : %d",Height);
        return 0;
    }
    
    void InitNode(BinSortTree **Node)       //初始化一个节点
    {
        *Node = (BinSortTree *)calloc(1,sizeof(BinSortTree));
        if(!*Node)
        {
            printf("Error\n");
            return ;
        }
        (*Node)->lChild = NULL;
        (*Node)->num = -1;
        (*Node)->rChild = NULL;
    }
    
    void CreateBinSortTree(BinSortTree **Node,int Num)  //创建排序二叉树
    {
        BinSortTree *p_Temp = *Node;
        if((*Node)->num == -1)
        {
            (*Node)->num = Num;
            return ;
        }
        while(p_Temp)
        {
            if(p_Temp->num >= Num)  //插入的元素小于节点，插入在子树
            {
                if(!p_Temp->lChild) //遍历到要插入的左子树的最后一个空节点
                {
                   InitNode(&p_Temp->lChild);
                   p_Temp->lChild->num = Num;
                   return ;
                }
                else
                {
                    p_Temp = p_Temp->lChild;//不断遍历
                    continue;
                }
            }
            else    //插入的元素大于节点，插入右子树
            {
                if(!p_Temp->rChild)
                {
                    InitNode(&p_Temp->rChild);
                    p_Temp->rChild->num = Num;
                    return ;
                }
                else
                {
                    p_Temp = p_Temp->rChild;
                    continue;
                }
            }
        }
        return ;
    }
    
    void PreOrderTraverse(BinSortTree *Node)    //先序遍历二叉树
    {
        if(!Node)
        {
            return ;
        }
        printf("%d ",Node->num);
        PreOrderTraverse(Node->lChild); 
        PreOrderTraverse(Node->rChild);
        return;
    }
    
    void InOrderTraverse(BinSortTree *Node)     //中序遍历二叉树
    {
        if(!Node)
        {
            return ;
        }
    
        InOrderTraverse(Node->lChild);
        printf("%d ",Node->num);
        InOrderTraverse(Node->rChild);
    }
    
    void leaf_sum(BinSortTree *Node,int *Sum)   //遍历二叉树找到叶子节点
    {
        if(!Node)
        {
            return ;
        }
        if(!Node->lChild && !Node->rChild)      //先序遍历二叉树来查找叶子节点
        {
            (*Sum)++;
        }
        leaf_sum(Node->lChild,Sum);
        leaf_sum(Node->rChild,Sum);
        return ;
    }
    
    int BinaryTreeHeight(BinSortTree *Node) //遍历二叉树得到高度
    {
        if(!Node)
        {
            return -1;
        }
        static int lHeight = 0;
        static int rHeight = 0;
        lHeight = BinaryTreeHeight(Node->lChild);
        rHeight = BinaryTreeHeight(Node->rChild);
        return (lHeight) > (rHeight) ? (lHeight + 1) :(rHeight + 1);
    }

## 博主新地址：[http://www.firefoxbug.net][http_www.firefoxbug.net] ##

[http_www.firefoxbug.net]: http://www.firefoxbug.net/