deep=leftdeep=rightdeep?leftdeep+1:rightdeep+1;
成都创新互联主要从事网站设计、网站制作、网页设计、企业做网站、公司建网站等业务。立足成都服务柳林,十年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18980820575
放在
leftdeep=TreeDeep(T-lchild);
rightdeep=TreeDeep(T-rchild);
后面
就是一直访问左孩子到树的底部后再一层层返回去,返回一层深度加一,一旦遇到右孩子不为空时,再访问右孩子的左孩子到树的底部后再一层层返回去,返回一层深度加一,每一个结点都进行右孩子与左孩子深度的比较,取大返回
首先分析二叉树的深度(高度)和它的左、右子树深度之间的关系。从二叉树深度的定义可知,二叉树的深度应为其左、右子树深度的最大值加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;
}
int BiTreeDepthHierarchy(BiThrTree T) //非递归类层次遍历求二叉树深度
{
int depth=0,hp,tp,lc; //hp为已访问的结点数,tp历史入队的结点总数,lc为每层最后一个结点标记
LinkQueue Q;
BiThrNode *p;
if(T)
{
p=T;
hp=0;tp=1;lc=1;
InitQueue(Q);
EnQueue(Q,p);
while(!QueueEmpty(Q))
{
DeQueue(Q,p);
hp++; //hp为已访问的结点数
if(p-lchild)
{
EnQueue(Q,p-lchild);
tp++; //tp记录历史入队的结点总数
}
if(p-rchild)
{
EnQueue(Q,p-rchild);
tp++;
}
if(hp==lc) //当hp=lc时,表明本层结点均已访问完
{
depth++;
lc=tp; //lc=tp,更新下层的末结点标记
}
}
}
return depth;
}
思想:对非空二叉树,其深度等于左子树的最大深度加1。
Int Depth(BinTree *T)
{
int dep1,dep2;
if(T==Null) return(0);
else
{
dep1=Depth(T-lchild);
dep2=Depth(T-rchild);
if(dep1dep2) return(dep1+1);
else return(dep2+1);
}
typedef int Status;
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int GetDepth(BiTree T){
if(!T) return 0;
else{
int depthLeft = GetDepth( T-lchild );
int depthRight= GetDepth( T-rchild );
return (depthLeftdepthRight?depthLeft:depthRight)+1;
}
}