当前位置: 首页 > 编程语言 > 算法 > 正文

如何求二叉树深度

时间:2015-10-30

题目描述:

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

输入:

第一行输入有n,n表示结点数,结点号从1到n。根结点为1。 n <= 10。

接下来有n行,每行有两个个整型a和b,表示第i个节点的左右孩子孩子。a为左孩子,b为右孩子。当a为-1时,没有左孩子。当b为-1时,没有右孩子。

输出:

输出一个整型,表示树的深度。

样例输入:

3

2 3

-1 -1

-1 -1

样例输出:

2

之前在Cracking the Coding interview中有一道根据给定有序数组,创建一个高度最小的二叉树的题目,最后要写个求高度的函数,与这道题一样。这是这次用数组存储二叉树,在九度OJ上AC。

思路很简单,递归实现,代码如下:

#include<stdio.h>  
#include<stdlib.h>  
      
      
typedef struct BTNode  
{  
    int data;  
    int rchild;  
    int lchild;  
}BTNode;  
      
int max(int a,int b)  
{  
    return a>b ? a:b;  
}  
      
/* 
求二叉树的深度 
本栏目更多精彩内容:http://www.bianceng.cn/Programming/sjjg/
*/
int TreeDepth(BTNode *pTree,int index)  
{  
    if(pTree == NULL)  
        return 0;  
      
    if(index == -1)  
        return 0;  
    else
        return max(TreeDepth(pTree,pTree[index].lchild),TreeDepth(pTree,pTree[index].rchild)) + 1;  
}  
      
      
int main()  
{  
    int n;  
    while(scanf("%d",&n) != EOF)  
    {  
        BTNode *pTree = NULL;  
        if(n>0)  
        {  
            pTree = (BTNode *)malloc(n*sizeof(BTNode));  
            if(pTree == NULL)  
                exit(EXIT_FAILURE);  
            int i;  
            //输入n个节点的data  
            for(i=0;i<n;i++)  
            {  
                int data1,data2;  
                scanf("%d %d",&data1,&data2);  
                if(data1 != -1)  
                    pTree[i].lchild = data1-1;  
                else
                    pTree[i].lchild = -1;  
                if(data2 != -1)  
                    pTree[i].rchild = data2-1;  
                else
                    pTree[i].rchild = -1;  
            }  
        }  
        printf("%d",TreeDepth(pTree,0));  
    }  
    return 0;  
}