二叉排序树

二叉排序树(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);
}

标签:C/C++, DataStructure