TNode *stack[MAX_STACK_SIZE] ,*p=T;
int top=0, num=0;
if (T!=NULL)
{ stack[++top]=p ;
while (top>0)
{ p=stack[top--] ;
if (p->Lchild==NULL&&p->Rchild==NULL) num++ ;
if (p->Rchild!=NULL )
stack[++top]=p->Rchild;
if (p->Lchild!=NULL )
stack[++top]=p->Lchild;
}
}
return(num) ;
}
求二叉树的深度 3 求二叉树的深度
利用层次遍历算法可以直接求得二叉树的深度。
算法实现： ＃define MAX_NODE 50
int BiTreedepth( BTNode *T)
{ BTNode * Queue[MAX_NODE] ,*p=T;
int front=0 , rear=0, depth=0, level ;
/* level总是指向访问层的最后一个结点在队列的位置 */
if (T!=NULL)
{ Queue[++rear]=p; /* 根结点入队 */
level=rear ; /* 根是第1层的最后一个节点 */
while (frontLchild!=NULL)
Queue[++rear]=p; /* 左结点入队 */
if (p->Rchild!=NULL)
Queue[++rear]=p; /* 左结点入队 */
if (front==level)
/* 正访问的是当前层的最后一个结点 */
{ depth++ ; level=rear ; }
}
}
}
求深度的递归算法 /* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
int BiTreeDepth(BiTree T)
{
int i,j;
if(!T) return 0;
if(T->lchild)
i=BiTreeDepth(T->lchild);
else i=0;
if(T->rchild)
j=BiTreeDepth(T->rchild);
else j=0;
return i>j?i+1:j+1;
}
|