PTA练习题：求二叉树高度

怼烎@ 2023-02-11 04:42 26阅读 0赞

本题要求给定二叉树的高度。

函数接口定义：

int GetHeight( BinTree BT );  
其中BinTree结构定义如下：

typedef struct TNode \*Position;  
typedef Position BinTree;  
struct TNode\{  
ElementType Data;  
BinTree Left;  
BinTree Right;  
\};  
要求函数返回给定二叉树BT的高度值。

裁判测试程序样例：

\#include <stdio.h>  
\#include <stdlib.h>

typedef char ElementType;  
typedef struct TNode \*Position;  
typedef Position BinTree;  
struct TNode\{  
ElementType Data;  
BinTree Left;  
BinTree Right;  
\};

BinTree CreatBinTree(); /\* 实现细节忽略 \*/  
int GetHeight( BinTree BT );

int main()  
\{  
BinTree BT = CreatBinTree();  
printf("%d\\n", GetHeight(BT));  
return 0;  
\}  
/\* 你的代码将被嵌在这里 \*/  
输出样例（对于图中给出的树）：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg_size_16_color_FFFFFF_t_70]

#include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    
    BinTree CreatBinTree();
    int GetHeight( BinTree BT );
    void print(BinTree T);
    
    int main()
    {
        BinTree BT = CreatBinTree();
        print(BT);
       printf("%d\n", GetHeight(BT));
        return 0;
    }
    // 先序建立二叉树 
    BinTree CreatBinTree()
    {
    	BinTree T = NULL;
    	char c;
    	scanf("%c",&c);
    	if(c != '#')
    	{
    		T = (BinTree)malloc(sizeof(struct TNode));
    		T->Data = c;
    		T->Left = CreatBinTree();
    		T->Right = CreatBinTree();
    	}
    	return T; 
    }
    // 先序遍历 
    void print(BinTree T)
    {
    	if(T != NULL)
    	{
    		printf("%c",T->Data);
    		print(T->Left);
    		print(T->Right);
    	}
    }
    // 求高度 
    int GetHeight( BinTree BT )
    {
    	if(BT == NULL)
    	{
    		return 0;
    	}
    	return GetHeight(BT->Left)+1>GetHeight(BT->Right)+1? GetHeight(BT->Left)+1:GetHeight(BT->Right)+1;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020052119482823.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg==,size_16,color_FFFFFF,t_70