以二叉树链表作为二叉树的存储结构,编写算法计算返回二叉树的高度

用c编写
2025-05-14 21:15:54
推荐回答(2个)
回答(1):

楼主看样子是才学数据结构吧...我以前学过,忘很多了,看这么高的分,我就顺便复习一下吧;
首先理解一下什么是高度:高度其实也叫深度,我通俗点说就是 比如根节点 是第一层,根节点的左右孩子为第二层,然后根节点的左右孩子各自的孩子为第三层.....那么二叉树的高度就是这棵树最大的层数。这么说不知道楼主明白了没有,举例就是:如果只有一个根节点,那么高度就是1,如果有一个根节点再加上根节点的两个孩子,或者其中一个孩子,那么高度就是2;
那根据这样 如果用递归的思想,我想算法就比较好写了,就是统计一下根节点的左右孩子的高对呗,看哪个的高度更大那二叉树高度就是那个呗。下面我粘贴出网上的两个算法(我没去运行试过,错了别怪我)顺便解释一下:
#include
#include //头文件就不用说了吧
typedef struct Node{
char data;
struct Node* lchild;
struct Node* rchild;
}Node,*Tree; //二叉树的定义也不用多说吧那个data的数据类型char可以任意换是吧

int max(int m, int n)
{
if (m > n)
return m;
else
return n;
} //这个我想能够看明白 求两个数最大值,为什么要求最大值上面也说了

int TreeHeight(Node *root)
{
if (root == NULL)
return 0; //如果根节点都没有 那高度肯定就是0了 是吧
else
return 1 + max(TreeHeight(root->lchild), TreeHeight(root->rchild));
} //否则递归计算他的左右孩子的高度然后在加上根节点的层数1 对吧

int height(Node *t) //第二个算法(其实和第一个一样)
{
if(t==NULL)
return 0;
else
{
int m=height(t->lchild);
int n=height(t->rchild); //递归计算该节点的左右孩子的高度
return(m>n)?m+1:n+1; //只不过这里没有用到上面求最大值的那个函数,楼主应该学过C
} //吧,这就是个逗号表达式,判断?A:B 判断满足就返回A不满
} //足就返回B 那这句换还是一样就是求m和n的最大值然后加1返 回

大概就这么个意思,如果程序没通过,楼主可以试着按这个想法稍微改改。
分能给我么?

回答(2):

int Depth (BiTree T ){ // 返回二叉树的深度
if ( !T ) depthval = 0;
else {
depthLeft = Depth( T->lchild );
depthRight= Depth( T->rchild );
depthval = 1 + (depthLeft > depthRight ?
depthLeft : depthRight);
}
return depthval;
}