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

函数接口定义：

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;
}
/* 你的代码将被嵌在这里 */

输出样例（对于图中给出的树）：

4

代码如下：

#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;
}BinTree CreatBinTree()
{//层序生成二叉树BinTree BT;ElementType T;int front = 0;int tail = 0;BinTree Queue[1001] = { '\0' };//父节点数列，'\0'是字符串结束标志BinTree Date;scanf("%c", &T);if (T == '0')//空树{return NULL;}else{BT = (BinTree)malloc(sizeof(struct TNode));if (BT == NULL){return NULL;}BT->Data = T;//根节点赋值BT->Left = BT->Right = NULL;//初始化左右子树Queue[tail++] = BT;//给父节点数列加树}while (Queue[front]!=NULL)//根节点入队列{Date = Queue[front++];scanf("%c", &T);if (T == '0'){Date->Left = NULL;}else{Date->Left = (BinTree)malloc(sizeof(struct TNode));if (Date->Left == NULL)//先完成左树的操作，然后完成右树的操作{return NULL;}Date->Left->Data = T;Date->Left->Left = Date->Left->Right = NULL;Queue[tail++] = Date->Left;}scanf("%c", &T);if (T == '0'){Date->Right = NULL;}else{Date->Right = (BinTree)malloc(sizeof(struct TNode));if (Date->Left == NULL)//先完成左树的操作，然后完成右树的操作{return NULL;}Date->Right->Data = T;Date->Right->Left = Date->Right->Right = NULL;Queue[tail++] = Date->Right;}}return BT;
}int GetHeight(BinTree BT)//递归方法
{int LH, RH;//对左右子树的高度进行记录if (!BT){return 0;}else{LH = GetHeight(BT->Left);RH = GetHeight(BT->Right);return LH > RH ? ++LH : ++RH;//返回左右子树中值最大的，因为不会统计父节点，所以要再加上当前父节点}
}