Question

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

所谓宽度是指在二叉树的各层上具有节点数最多的那一层上的节点总数！
我想得到直接的答案，算法

Answer 1

树的高度：对非空二叉树，其深度等于左子树的最大深度加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);}}。

扩展资料

方法：

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

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

Answer 2

原题：
以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法。所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。

标准答案：
①求树的高度
思想：对非空二叉树，其深度等于左子树的最大深度加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<p)
{
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<count)
flag=count;
count=0;
p=rear; /* p指向下一层最右边的结点*/
}
}
/* endwhile*/
return(flag);
}

Answer 3

递归，用一个一维数组维护各层的节点数信息。层序遍历 类似BFS 借助一个队列。