IBM Rational 系统开发最佳实践工具包	WebSphere MQ 最佳实践 TOP 15

求树高度算法

楼主zxx110（新）2006-03-11 12:59:06 在 C/C++ / C++ 语言提问

树结构结点声明：
struct NODE
{
NODE *left;
NODE *right;
Datatype data;
}
给定函数原型
int TreeHeight(NODE *root);//通过输入一个树的根结点，要求返回这棵数的高度；问题点数：50、回复次数：21Top

1 楼llf_hust（）回复于 2006-03-11 13:03:26 得分 10

int TreeHeight(NODE *root)
{
int i,j;
if( !root )
return 0;
else
{
i = TreeHeight(root->left);
j = TreeHeight(root->right);
if( i >= j )
return i+1;
else
return j+1;
}
}

Top

2 楼zxx110（新）回复于 2006-03-13 09:36:39 得分 0

似乎有点不对
当只有一个根结点时，此程序的结果为1；
但树的高度应该是为0啊；Top

3 楼healer_kx（甘草(楼主揭贴吧，我们这些上班灌水的也不容易)）回复于 2006-03-13 10:18:23 得分 0

那就return 1;呗、Top

4 楼zxx110（新）回复于 2006-03-13 12:21:29 得分 0

把哪个return 改了？？
如果是第一个明显root=NULL时不符合
如果是改后两个那所有非空树的高度都是1了；
改哪个都不对啊Top

5 楼zxx110（新）回复于 2006-03-13 12:44:37 得分 0

int TreeHeight(NODE *root)
{
static int count=0;
int tempData=0;
if (root==NULL&&root->left==NULL&&root->right==NULL)
return count;
else
{
if(root->left!=NULL)
{
count++;
tempData=TreeHeight(root->left);
}
if(root->right!=NULL)
{//如果左子树不为空，则此处高度不加1；
if(root->left==NULL） count++;
tempData=TreeHeight(root->right);
}
}

}

这样的写法不知错哪里了？？Top

6 楼ykzhujiang（朱朱）回复于 2006-03-13 15:50:51 得分 10

你这道题目本身就有些问题，二叉树有很多种，如果你的意思是求这棵树的最大深度的话，那么将这棵树遍历一次就可以求出了Top

7 楼ykzhujiang（朱朱）回复于 2006-03-13 16:34:27 得分 0

你的算法问题较多，我自己编了一个，你可以作为参考：
#include <iostream>
using namespace std;
typedef int Datatype;
struct NODE
{
NODE *left;
NODE *right;
Datatype data;
};

int TreeHeight(NODE *root)
{
static int count=0;
static int max_depth=0;
if(root==NULL)
return 0;
else
{
count++;
if(root->left!=NULL)
{
TreeHeight(root->left);
count--;
}
if(root->right!=NULL)
{
TreeHeight(root->right);
count--;
}
if(root->left==NULL&&root->right==NULL&&max_depth<count)
{
max_depth=count;
}
}
return max_depth;
}
int main()
{
struct NODE a,b,c,d,e,f,g;
a.left=&b;
a.right=&c;
b.left=NULL;
b.right=NULL;
c.left=&d;
c.right=NULL;
d.left=&e;
d.right=&f;
e.left=NULL;
e.right=NULL;
f.left=NULL;
f.right=&g;
g.left=NULL;
g.right=NULL;
cout<<TreeHeight(&a)<<endl;

return 0;
}Top

8 楼ykzhujiang（朱朱）回复于 2006-03-13 16:46:16 得分 0

只有一个节点的时候还是return 1比较好，否则会和root为空的情况重合
当然这个只不过是输出的形式问题
如果你习惯将根节点所在高度设为0的话，只要稍微改造一下就行，这样当root为空时返回-1
int TreeHeight(NODE *root)
{
static int count=-1;
static int max_depth=-1;
if(root==NULL)
return -1;
else
{
count++;
if(root->left!=NULL)
{
TreeHeight(root->left);
count--;
}
if(root->right!=NULL)
{
TreeHeight(root->right);
count--;
}
if(root->left==NULL&&root->right==NULL&&max_depth<count)
{
max_depth=count;
}
}
return max_depth;
}Top

9 楼dreamXren（追梦人）回复于 2006-03-13 18:11:55 得分 10

根据递归定义：二叉树的高度为：
　　　当为空树时，高度为0；
　　　当只有一个结点时，高度为1；
　　　其他情况：高度为max(根的左子树高度，根的右子树高度)+1

　int Height(NODE *root)
　　{
　　　int hl,hr;
　　　if(root)
　　　　{//非空树
　　　　　if(root->left==NUll)&&(root->right==NULL)//只含一个根结点
　　　　　　return 1;
　　　　　else
　　　　　　{
　　　　　　　hl=height(root->left);//根的左子树高度
　　　　　　　hr=height(root->right);//根的右子树高度
　　　　　　　if (hl>=hr)
　　　　　　　　return hl+1;
　　　　　　　else return h2+1;
　　　　　　}
　　　　}
　　　else return 0;
　　}
网上一找一堆。Top

10 楼chenzhichao2008（陈智超）回复于 2006-03-13 18:37:29 得分 10

if (root==NULL&&root->left==NULL&&root->right==NULL)
return count;

a
b c
d e
前序遍历遇到b是叶子结点，满足条件，返回1

else
{
if(root->left!=NULL)
{
count++;
tempData=TreeHeight(root->left);
}
if(root->right!=NULL)
{//如果左子树不为空，则此处高度不加1；
if(root->left==NULL） count++;
tempData=TreeHeight(root->right);
}
}

else 的返回值在哪里?
Top

11 楼chenzhichao2008（陈智超）回复于 2006-03-13 18:38:29 得分 0

tempData的作用呢？Top

12 楼du51（郁郁思扬）回复于 2006-03-13 18:53:08 得分 5

int Treedepth(NODE *root)
　{ 　if(!root)return(-1);
　　　if(root->lchild==NULL&&(root->rchild==NULL)return 0;
　　　else return(Treedepth(root->lchild)>Treedepth(root->rchild)?
　　　(1+Treedepth(root->lchild)):(1+Treedepth(root->rchild));
　 }Top

13 楼llf_hust（）回复于 2006-03-13 20:29:35 得分 0

int TreeHeight(NODE *root)
{
int i,j;
if( !root )
return 0;
else
{
i += TreeHeight(root->left);
j += TreeHeight(root->right);
if( i >= j )
return i+1;
else
return j+1;
}
}
Top

14 楼zxx110（新）回复于 2006-03-13 23:58:06 得分 0

感谢追梦人人的说明

回陈智超：
tempData 只是个数据域。它的取值与树的高度无关，所以作用无须声明；

各位高手，谁能指点我一下：
我的算法的意思是：用一个静态变量记数，先序遍历树，如果当前结点有左子树（包含有左右子树的情况）则记数器加一；如果只有右子树则记数器加一；遍历完后返回记数器的值；
因为我认为只有当结点有上叙两种情况之一时，树的高度才会增加；

to IIf_hust（）：我想你第二次写的算法更不行了；
i += TreeHeight(root->left)；
j += TreeHeight(root->right);
此时的i,j都是不可确定的，结果可能会出乎你的预料；Top

15 楼zxx110（新）回复于 2006-03-14 00:02:33 得分 0

希望有个比较纤细的说明
我的那个算法具体错哪了？？Top

16 楼zxx110（新）回复于 2006-03-14 00:03:33 得分 0

晕写错了
是个详细的说明
呵呵不好意思拉各位Top

17 楼Sword_liao（Sword_liao）回复于 2006-03-14 17:22:41 得分 5

1.递归法
int Height(TreeNode *root)
{
if (root==NULL)
return 0;

return (Height(root->lChild) > Height(root->rChild) ? Height(root->lChild)+1 :
Height(root->rChild)+1);
}

2. 用层次遍历，要用到队列，算法略
Top

18 楼dream2013（每个人都有魔鬼的一面( http://blog.sina.com.cn/u/1422260677 )）回复于 2006-03-14 20:54:06 得分 0

强Top

19 楼zxx110（新）回复于 2006-03-15 11:23:00 得分 0

仔细看了朱朱的代码，终于明白些了，知道我的算法主要问题在哪了。Thanks!
不过还想问下朱朱，有返回值的函数那样调用不会出什么问题吧？？Top

20 楼zxx110（新）回复于 2006-03-15 15:57:58 得分 0

还是希望朱朱有个回复
结帖了Top

21 楼ykzhujiang（朱朱）回复于 2006-03-15 16:28:29 得分 0

to zxx110(新)
这种调用方法不会有问题的，返回值被存放在临时变量里面，不会对产生影响的Top