求二叉树的高度

约定不等于承诺〃 2022-06-16 13:44 156阅读 0赞

/*求二叉树的高度*/
    #include<stdio.h>
    typedef struct btnode
    {
        char data;
        struct btnode *lchild,*rchild;      /*指向左右孩子的指针*/
    }BinTree;
    /*二叉树的创建*/
    BinTree * CreateTree(BinTree *T)
    {
        char ch;
        scanf("%c",&ch);
        if(ch=='#')
            return 0;
        else
        {
            T=(BinTree *)malloc(sizeof(BinTree));
            T->data=ch;
            T->lchild=CreateTree(T->lchild);    /*创建左子树*/
            T->rchild=CreateTree(T->rchild);    /*创建右子树*/
            return(T);
        }
    }
    /*先序遍历根指针为T的二叉树*/
    void Preorder(BinTree *T)
    {
        if(T)
        {
            printf("%c ",T->data);  /*访问根节点T*/
            Preorder(T->lchild);    /*先序遍历左子树*/
            Preorder(T->rchild);    /*先序遍历右子树*/
        }
    }
    /*中序遍历根指针为T的二叉树*/
    void inorder(BinTree *T)
    {
        if(T)
        {
            inorder(T->lchild);     /*中序遍历左子树*/
            printf("%c ",T->data);  /*访问根节点T*/
            inorder(T->rchild);     /*中序遍历右子树*/
        }
    }
    /*后序遍历根指针为T的二叉树*/
    void postorder(BinTree *T)
    {
        if(T)
        {
            postorder(T->lchild);   /*后序遍历左子树*/
            postorder(T->rchild);   /*后序遍历右子树*/
            printf("%c ",T->data);  /*访问根节点T*/
        }
    }
    /*求二叉树的高度*/
    int height(BinTree *T)
    {
        int lh,rh;
        if(T==NULL)
            return 0;               /*初始左右子树的高度为0*/
        else
        {
            lh=height(T->lchild);   /*左子树的高度*/
            rh=height(T->rchild);   /*右子树的高度*/
            return 1+(lh>rh?lh:rh);
        }
    }
    main()
    {
        BinTree *b;
        printf("请按先序的方式输入二叉树的结点元素:\n");
        b=CreateTree(b);
        printf("前序输出:\n");
        Preorder(b);
        printf("\n");
        printf("中序输出:\n");
        inorder(b);
        printf("\n");
        printf("后序输出:\n");
        postorder(b);
        printf("\n");
        printf("该二叉树的高度为:%d\n",height(b));
    }