满意答案
assonvoon
2013.11.06
采纳率：52% 等级：12
已帮助：9412人
原题:
以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法。所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。
标准答案:
①求树的高度
思想:对非空二叉树，其深度等于左子树的最大深度加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)
{
int
front=-1,rear=-1;/*
队列初始化*/
int flag=0,count=0,p;
/* p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值。*/if(T!=Null)
{
rear++;
q[rear]=T;
flag=1;
p=rear;
}
while(front
{
front++;
T=q[front];
if(T->lchild!=Null)
{
rear++;
q[rear]=T->lchild;
count++;
}
if(T->rchild!=Null)
{
rear++;
q[rear]=T->rchild;
count++;
}
if(front==p)
/* 当前层已遍历完毕*/
{
if(flag
flag=count;
count=0;
p=rear; /* p指向下一层最右边的结点*/
}
}
/* endwhile*/
return(flag);
}
00分享举报