树的高度:对非空二叉树,其深度等于左子树的最大深度加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 numif (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)}}。
扩展资料
方法:
求二叉树的高度的算法基于对二叉树的三种遍历,可以用后序遍历的算法加上记录现在的高度和已知的最高的叶子的高度,当找到一个比已知高度还要高的叶子,刷新最高高度。
最后遍历下来就是树的高度,至于后序遍历的算法,是一本数据结构或者算法的书中都有介绍和参考代码
分析:二叉树是递归定义的,其计算二叉树的高度可以采取递归方式intHeight(btrebt)//求二叉树bt的深度{inthl,hrif(bt==NULL)return(0)else{hl=Height(bt->lch)hr=Height(bt->rch)if(hl>hr)return(hl+1)elsereturn(hr+1)}}分析:求二叉树的最大宽度可采用层次遍历的方法,记下各层结点数,每层遍历完毕,若结点数大于原先最大宽度,则修改最大宽度。intWidth(BiTreebt)//求二叉树bt的最大宽度{if(bt==null)return(0)//空二叉树宽度为0else{BiTreeQ[]//Q是队列,元素为二叉树结点指针,容量足够大front=1rear=1last=1//front队头指针,rear队尾指针,last同层最右结点在队列中的位置temp=0maxw=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=rearif(temp>maxw)maxw=temp//last指向下层最右元素,更新当前最大宽度temp=0}//if}//whilereturn(maxw)}//结束width