计算二叉树的高度算法

1. 假设以二叉链表作为二叉树的存储结构，试编写一个求树的高度的算法

#include<iostream.h>
#include<malloc.h>

#define FALSE 0
#define TRUE 1
#define OK 1
#define maxsize 100
typedef int status;
typedef int elemtype;

typedef struct binode
{
elemtype data;
struct binode *lchild,*rchild;
}binode,*bitree;

status treecreated=FALSE;
int leafcount=0;

status createbitree(bitree *t);
status preordertraverse(bitree t);
int height(bitree t);
void swap(bitree *t);
void leafcounts(bitree t);

void main()
{
int choice=0;
status leave=FALSE,flag;
binode *bt;
cout<<"===========二叉树演示程序==============="<<endl;
do
{
cout<<"1：创建一个二叉树，按先序遍历结果输入，空用0表示 "<<endl;
cout<<"2：先序遍历二叉树，递归方式遍历二叉树 "<<endl;
cout<<"3：求叶子数"<<endl;
cout<<"4：计算二叉树的高度"<<endl;
cout<<"5: 树进行左右翻转"<<endl;
cout<<"0：退出"<<endl;
cout<<"-------请输入你的选择:"<<endl;
cin>>choice;
switch(choice)
{
case 1:
if(treecreated)
{
cout<<"sorry,the tree has been already created!"<<endl;
break;
};
cout<<"请输入代表树的数字："<<endl;
flag=createbitree(&bt);
if(flag==OK)
{
cout<<"你已经建立了一棵树了！"<<endl;
treecreated=TRUE;
}
break;

case 2:
if(!treecreated)
{
cout<<"sorry,you must create a tree for further steps!"<<endl;
break;
}
cout<<"先序遍历顺序:"<<endl;
preordertraverse(bt);
cout<<endl;
break;

case 3:
if(!treecreated)
{
cout<<"sorry,you must create a tree for further steps!"<<endl;
break;
}
leafcounts(bt);
cout<<"树的叶子数:"<<leafcount<<endl;
cout<<endl;
break;

case 4:
int h;
h=height(bt);
cout<<"树的高度:"<<h<<endl;
break;

case 5:
swap(&bt);
cout<<"树已经翻转！！！"<<endl;
break;

case 0:
leave=TRUE;
break;
}
}while(!leave);
cout<<" 谢谢 再见了！！！"<<endl;
}
//递归方法实现创建
status createbitree(bitree *t)
{
int ch=0;
cin>>ch;
if(ch==0) //输入如果是0表示是空
(*t)=NULL;
else
{
(*t)=(bitree)malloc(sizeof(binode)); //申请空间
(*t)->data=ch; //把数据传给他
createbitree(&(*t)->lchild); //左孩子重新进入创建函数
createbitree(&(*t)->rchild); //右孩子重新进入创建函数
}
return OK;
}

//递归方法实现先序遍历
status preordertraverse(bitree t)
{
if(t)
{
cout<<t->data<<" "; //先把头结点输出
preordertraverse(t->lchild); //然后是左结点
preordertraverse(t->rchild); //然后是右结点
return OK;
}
else
return OK;
}

int height(bitree t)
{
int hl,hr;
if(t==NULL)
return 0;
hl=height(t->lchild)+1; //最下面的左孩子加一
hr=height(t->rchild)+1; //最下面的右孩子加一
return (hl>hr?hl:hr); //比较谁大就取谁
}

void swap(bitree *t) //进行左右翻转
{
bitree p;
if(*t!=NULL)
{
p=(*t)->lchild; //p为中间变量
(*t)->lchild=(*t)->rchild;
(*t)->rchild=p;
swap(&(*t)->lchild);
swap(&(*t)->rchild);
}
}

void leafcounts(bitree t) //求叶子数
{
if(t) //如果不为空
{
if(t->lchild==NULL && t->rchild==NULL)//左右孩子都为空 表明是叶子
leafcount++;
leafcounts(t->lchild);
leafcounts(t->rchild);
}
}

2. 求二叉树高度的原理、算法是什么，越详细越好，C语言，谢谢

首先分析二叉树的深度（高度）和它的左、右子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加
1
。
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;
}

3. 什么是二叉树如何计算二叉树的高度

看左子树高还是右子树高，高的那个的高度加一就是整个二叉树的高度了。利用这个关系，搞个递归就出来了。

4. 二叉树的深度算法怎么算啊

二叉树的深度算法：
一、递归实现基本思想：
为了求得树的深度，可以先求左右子树的深度，取二者较大者加1即是树的深度，递归返回的条件是若节点为空，返回0
算法：
1
int
FindTreeDeep(BinTree
BT){
2
int
deep=0;
3
if(BT){
4
int
lchilddeep=FindTreeDeep(BT->lchild);
5
int
rchilddeep=FindTreeDeep(BT->rchild);
6
deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
7
}
8
return
deep;
9
}
二、非递归实现基本思想：
受后续遍历二叉树思想的启发，想到可以利用后续遍历的方法来求二叉树的深度，在每一次输出的地方替换成算栈S的大小，遍历结束后最大的栈S长度即是栈的深度。
算法的执行步骤如下：
（1）当树非空时，将指针p指向根节点，p为当前节点指针。
（2）将p压入栈S中，0压入栈tag中，并令p执行其左孩子。
（3）重复步骤（2），直到p为空。
（4）如果tag栈中的栈顶元素为1，跳至步骤（6）。从右子树返回
（5）如果tag栈中的栈顶元素为0，跳至步骤（7）。从左子树返回
（6）比较treedeep与栈的深度，取较大的赋给treedeep，对栈S和栈tag出栈操作，p指向NULL，并跳至步骤（8）。
（7）将p指向栈S栈顶元素的右孩子，弹出栈tag，并把1压入栈tag。（另外一种方法，直接修改栈tag栈顶的值为1也可以）
（8）循环（2）~（7），直到栈为空并且p为空
（9）返回treedeep，结束遍历
1
int
TreeDeep(BinTree
BT
){
2
int
treedeep=0;
3
stack
S;
4
stack
tag;
5
BinTree
p=BT;
6
while(p!=NULL||!isEmpty(S)){
7
while(p!=NULL){
8
push(S,p);
9
push(tag,0);
10
p=p->lchild;
11
}
12
if(Top(tag)==1){
13
deeptree=deeptree>S.length?deeptree:S.length;
14
pop(S);
15
pop(tag);
16
p=NULL;
17
}else{
18
p=Top(S);
19
p=p->rchild;
20
pop(tag);
21
push(tag,1);
22
}
23
}
24
return
deeptree;
25
}

5. 以二叉树链表作为二叉树的存储结构，怎么编写算法计算返回二叉树的高度

编写方法如下：

6. 二叉树的高度计算和查找结点双亲

求高度的算法：
int BTNodeHeight(BTNode *b)
{int lchildh,rchildh;
if(b==NULL)return 0;
else
{ lchild=BTNodeHeight(b->lchild);
rchild=BTNodeHeight(b->rchild);
return(lchildh>rchildh)?(lchildh+1):(rchildh+1);
}
}
查找节点：
BTNode *FindNode(BTNode *b ,char x)
{BTNode *p;
if(b==NULL)
return NULL;
else if(b->data==x)
return b;
else
{p=FindNode(b->lchild,x);
if(p!=NULL)
return p;
else
return FindNode(b->rchild,x);
}
}

7. 如何用非递归算法求二叉树的高度

if（T＝＝null）

return0；

intfront＝－1，

rear＝－1；

／／front出队指针

rear入队指针intlast＝0，

level＝0；

／／last每一层的最右指针

（front＝＝last时候一层遍历结束level＋＋）BiTreeQ［Maxsize］；

／／模拟队列Q［＋＋rear］＝T；

BiTreep；

while(front<rear){

p＝Q［＋＋front］；／／开始出队

因为front要赶到lash

实现level＋＋

if(p->lchild)

Q[++rear] = p->lchild;

if(p->rchild)

Q[++rear] = p->rchild;

if（front＝＝last）｛

level＋＋；

last＝rear；／／last指向下层节点｝

｝

(7)计算二叉树的高度算法扩展阅读

非递归算法思想：

（1）设置一个栈S存放所经过的根结点（指针）信息；初始化S；

（2）第一次访问到根结点并不访问，而是入栈；

（3）中序遍历它的左子树，左子树遍历结束后，第二次遇到根结点，就将根结点（指针）退栈，并且访问根结点；然后中序遍历它的右子树。

（4）当需要退栈时，如果栈为空则结束。

8. 以二叉链表为存储结构,写出求二叉树高度和宽度的算法

树的高度：对非空二叉树，其深度等于左子树的最大深度加1。

Int Depth(BinTree *T){int dep1,dep2;

if(T==Null) return(0);

else{dep1=Depth(T->lchild);

dep2=Depth(T->rchild);

if(dep1>dep2) return(dep1+1);

else return(dep2+1);}

树的宽度：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。

int Width(BinTree *T){intfront=-1,rear=-1;

/*队列初始化*／int flag=0,count=0,p;

/* pint CountNode (BTNode *t)

//节点总数{int num;if (t == NULL)num = 0;

elsenum = 1 + CountNode (t->lch) + CountNode (t->rch);

return (num);}void CountLeaf (BTNode *t)

//叶子节点总数{if (t != NULL){if (t->lch == NULL && t->rch == NULL)count ++;

// 全局变量CountLeaf (t->lch);CountLeaf (t->rch);}}。

(8)计算二叉树的高度算法扩展阅读

方法：

求二叉树的高度的算法基于对二叉树的三种遍历，可以用后序遍历的算法加上记录现在的高度和已知的最高的叶子的高度，当找到一个比已知高度还要高的叶子，刷新最高高度。

最后遍历下来就是树的高度，至于后序遍历的算法，是一本数据结构或者算法的书中都有介绍和参考代码

9. 二叉树求高度，用栈模拟递归.怎么实现

计算二叉树的高度可以采用几种不同的算法。 算法一：采用后序遍历二叉树，结点最大栈长即为二叉树的高度； 算法二：层次遍历二叉树，最大层次即为二叉树的高度； 算法三：采用递归算法，求二叉树的高度。

10. 求二叉树的高度

公式:V0=(V2)
+2(
V3)+3
(V4)....(k-1)(Vk)+1
所有的树都满足这个公式，其中v0...vk代表
度为0...K的节点个数。
所有计算度与节点个数的问题无论是几叉树的都必须用这个式子，我建议楼主哥哥记住!
叶子节点就是度为0的节点V0，其他的分支节点度都为m那么就只存在度为0和度为m的节点
代入上面公式:
V0=(m-1)Vm+1
又因为:
Vm+V0=n
//因为树总共n个节点
解这个方程组，就得
V0=((m-1)n+1)/m
用计算机计算
，你可以将它理解成一个层序遍历的过程，使用队列来遍历:
存储结构是
typedef
struct
Node
{
int
data;
struct
node
*FirstChild;
struct
node
*NextBrother;
}*Tree;
static
int
leafnum;
//全局函数用于计数叶子节点
void
BFSCount(Tree
t)
{
int
i=0;
SeqQueue
*Q;
TreeNode
*p;
InitQueue(Q);
if(t==NULL)
return;
EnterQueue(Q,t);
While(!Empty(Q))
{
DeleteQueue(Q,p);
//出队
然后判断这个节点
if(p->FirstChild==NULL)
leafnum++;
//如果这个节点一个孩子也没有，则是叶子，计数+1
else{
p=t->FirstChild;
//否则开始将它第一个孩子继续进入队
EnterQueue(Q,p);
while(i<=m)
//把第一个孩子的下一个兄弟依次入队
{
p=p->NextBrother;
EnterQueue(Q,p);
}
}
}
}