关于二叉树的深度算法题目及解答

求二叉树的深度算法

算法的思想：

　　采用二叉树的后序遍历非递归算法。由于后序遍历非递归算法使用一个栈实现，每次都会在一条路径上走到最底层才向上访问，再向右访问。因此，记录下栈在遍历中的最大值，即为二叉树的最大深度。

#include 
#include 
using namespace std;
struct BinTree
{
    int data;
    BinTree *lc;
    BinTree *rc;
}BTNode,*BinTree;
int max(int a,int b)
{
    return (a>b)?a:b;
}
int BinTreeDepth(BinTree T)
{
    stack s;
    BinTree p = T,r = NULL;
    int depth=0;
    while(p||!s.empty())
    {
        if(p)
        {    //从根节点向左边走
            s.push(p);
            int size = s.size();//获取栈的大小
            depth = max(depth,size);//替换最大值
            p = p->lc;
        }
        else
        {    //左边走不通向右走
            p = s.top();
            if(p->rc&&p->rc!=r)//如果右子树存在，且未被访问过
            {
                p = p->rc;
                s.push(p);
                int size = s.size();//获取栈的大小
                depth = max(depth,size);//替换最大值
                p = p->lc;
            }else
            {
                p=s.top();
                s.pop();
                cout<data<

求二叉树深度的算法

题目：二叉树用二叉链表表示，编写求二叉树深度的算法。

答案是：
int height(Bitree T)
{
  if (T==NULL) return 0;
  u=height(T->lchild);
  v=height(T->rchild);
   if (u>n) return (u+1)
  return (v+1)
}

关于递归，你可以看成是一句一句往下运行嘛。需要保存状态的时候，系统就会自动用栈帮你保存。就依你说得那个为例：
n为全局变量，初值为0；

第一次调用height(T)，假设T！=NULL
由于T!=NULL：跳过if (T==NULL) return 0; 

关键到了u=height(T->lchild); 调用本身的函数：此时的T->lchild保存在栈中，既然是调用就得从函数开头执行：
看下这时候T2（其实就是T->lchild），if (T==NULL) return 0；
这里假设T不是NULL，就继续运行在遇到u=height(T->lchild); 在调这个函数本身――
这里就假设它为T->lchild==NULL吧。这下可好，这个函数执行return 0；

慢着：第二次函数调用u=height(T->lchild)中的函数值已经计算出来啦。这时u=0；

你还记得第二次调用运行到了v=height(T->rchild); 这句话吧？好，这个过程就和u=height(T->lchild)完全一样。
这里也假设得到的v=0

则第二次调用到了if (u>n) return (u+1) 
return (v+1)
得到一个返回值，不如就假设u〉n，于是返回值1；
好，这一波完毕；

你还记得第一次调用的height吧，这时把返回值给u,u=1；
然后执行到第一次调用中的v=height(T->rchild); 了。分析同上。

这个过程的确比较复杂。慢慢琢磨吧。呵呵。

 基本思路就是如果当前节点还有子节点，则继续访问，递归的找寻子节点直到叶子节点为止。 

procedure tree(a:node,depth:integer); 
begin 
if resultnil then tree(a.leftchild,depth+1); 
if a.rightchild<>nil then tree(a.rightchild,depth+1); 
end;
注:result是全局变量,是结果 

实际上最好不用什么全局变量 
int depth(node *bt) 
{ if (bt==NULL) 
return 0; 
ldepth=depth(bt->left)+1; 
rdepth=depth(bt->right)+1; 
return max(ldepth,rdepth); 
}

全局变量是bug 
int Height(BiTree T){ 
int m,n; 
if(!T) return(0); 
else 
m=Height(T->lchild); 
n=Height(T->rchild); 
return((m>n?m:n)+1); 
}

求树深度的递归算法 
// struct bnode{struct bnode *lc,*rc); 
int depth(struct bnode *r) 
{ 
return r==NULL?0:1+max(depth(r->lc),depth(r->rc)); 
}

问：设计算法求二叉树的深度

设一棵二叉树以二叉链表存储，试设计算法求此二叉树的深度

回答：

#include 
#include 
typedef struct node
{
 char data;
 struct node *left,*right;
}Node,*PNode;
PNode createBtree(PNode root)//创建二叉树，控制台下输入，基于先序遍历输入
{
   char data;
   scanf("%c",&data);
   if (data==' ')
   {
    root=NULL;
    return root;
   }
   root = (PNode)malloc(sizeof(Node));
   root->data = data;
   root->left = createBtree(root->left);
   root->right = createBtree(root->right);
   return root;
}
int depth(PNode root)//这就是你要的函数。
{
 int ld,rd;
 if (root==NULL)
 {
  return 0;
 }
 ld = 1+depth(root->left);
 rd = 1+depth(root->right);
 return ld>rd?ld:rd;
}
int main()
{
    PNode root=NULL;
 root = createBtree(root);
 printf("%d",depth(root));
 return 0;
}

为了测试，写了二叉树的建立程序；
如下输入可以看到结果
虚节点用空格输入的。例如你输入
先序遍历
234空格空格5空格6空格空格7空格空格回车就可以看到结果。
另外，本算法是从1开始算深度的，就是根节点是深度下。
                    


                    

                        

                            
相关文章
                        
                        

                                                                                                

                                        《尼尔：机械纪元》武器黑之倨傲属性及特殊能力介绍
                                        11-15
                                    
                                                                    

                                        《尼尔：机械纪元》机械生命体的枪获得方法介绍
                                        11-15
                                    
                                                                    

                                        《尼尔：机械纪元》武器机械生命体的枪属性及特殊能力介绍
                                        11-15
                                    
                                                                    

                                        《尼尔：机械纪元》天使之圣翼获得方法介绍
                                        11-15
                                    
                                                                    

                                        《尼尔：机械纪元》武器天使之圣翼属性及特殊能力介绍
                                        11-15
                                    
                                                                    

                                        《尼尔：机械纪元》武器恶魔之秽牙属性及特殊能力介绍
                                        11-15