参考答案

正确答案：二叉树高度可递归计算如下：若二叉树为空则高度为0否则二叉树的高度等于左右子树高度的大者加1。这里二叉树为空的标记不是null而是0。设根结点层号为1则每个结点的层号等于其双亲层号加1。二叉树的存储结构定义如下：typedefstruct node{int L[]；／／编号为i的结点的左儿子int R[]；／／编号为i的结点的右儿子int D[]；／／编号为i的结点的层号int i；／／存储结点的顺序号(下标)}tnode；(1)int Height(tnode tint i)／／求二叉树高度调用时i=1{int lhrh；if(i==0)return(0)；else{1h=Height(tt．L[i])；rh=Height(tt．R[i])；if(1h>rh)return(1h+1)；else return(rh+1)；}}／／结束Height求最大宽度可采用层次遍历的方法记下各层结点数每层遍历完毕若结点数大于原先最大宽度则修改最大宽度。(2)int Width(BiTree bt)／／求二叉树bt的最大宽度{if(bt==null)return(0)；／／空二叉树宽度为0else{BiTree Q[]；／／Q是队列元素为二叉树结点指针容量足够大front=1；rear=1；last=1；／／front队头指针rear队尾指针last同层最右结点在队列中的位置temp=0；maxw=0；／／temp记局部宽度maxw记最大宽度Q[rear]=bt；／／根结点人队列while(front<=last){P=Q[front++]；temp++；／／同层元素数加1if(p->lchild!=null)Q[++rear]=p一>lchild；／／左子女人队if(p->rchild!=null)Q[++rear]=p一>rchild；／／右子女人队if(front>last)／／一层结束{last=rear；if(temp>maxw)maxw=temp；／／last指向下层最右元素更新当前最大宽度temp=0；}／／if}／／whilereturn(maxw)；}／／结束width
二叉树高度可递归计算如下：若二叉树为空,则高度为0,否则,二叉树的高度等于左右子树高度的大者加1。这里二叉树为空的标记不是null而是0。设根结点层号为1,则每个结点的层号等于其双亲层号加1。二叉树的存储结构定义如下：typedefstructnode{intL[]；／／编号为i的结点的左儿子intR[]；／／编号为i的结点的右儿子intD[]；／／编号为i的结点的层号inti；／／存储结点的顺序号(下标)}tnode；(1)intHeight(tnodet,inti)／／求二叉树高度,调用时i=1{intlh,rh；if(i==0)return(0)；else{1h=Height(t,t．L[i])；rh=Height(t,t．R[i])；if(1h>rh)return(1h+1)；elsereturn(rh+1)；}}／／结束Height求最大宽度可采用层次遍历的方法,记下各层结点数,每层遍历完毕,若结点数大于原先最大宽度,则修改最大宽度。(2)intWidth(BiTreebt)／／求二叉树bt的最大宽度{if(bt==null)return(0)；／／空二叉树宽度为0else{BiTreeQ[]；／／Q是队列,元素为二叉树结点指针,容量足够大front=1；rear=1；last=1；／／front队头指针,rear队尾指针,last同层最右结点在队列中的位置temp=0；maxw=0；／／temp记局部宽度,maxw记最大宽度Q[rear]=bt；／／根结点人队列while(front<=last){P=Q[front++]；temp++；／／同层元素数加1if(p->lchild!=null)Q[++rear]=p一>lchild；／／左子女人队if(p->rchild!=null)Q[++rear]=p一>rchild；／／右子女人队if(front>last)／／一层结束{last=rear；if(temp>maxw)maxw=temp；／／last指向下层最右元素,更新当前最大宽度temp=0；}／／if}／／whilereturn(maxw)；}／／结束width