求解二叉树的深度

发表于 | 分类于 | | 阅读次数:

思路

采用递归求解，对于树tree的深度，其值为：

Depth(tree) =
max(Depth(tree的左子树),Depth(tree的右子树)),tree != NULL
0,tree == NULL

231913132

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdlib.h> 
#include <stdio.h> 

typedef struct TNode 
{ 
    int value; 
    TNode* lchild; 
    TNode* rchild; 
}TNode,*BTree; 

//采用递归思想求解树的深度 
int CalDepth(BTree tree) 
{ 
    //若树为空，则树的深度为0 
    if (tree==NULL) return 0; 
    int left,right; 
    //仅考虑左子树，则树的深度等于左子树的深度加1 
    left = CalDepth(tree->lchild)+1; 
    //仅考虑右子树，则树的深度等于右子树的深度加1 
    right = CalDepth(tree->rchild)+1; 
    //树的深度取上述两个值中的较大值 
    return (left>right?left:right); 
} 

int main() 
{ 
    BTree tree = (BTree)malloc(sizeof(TNode)); 
    tree->lchild = (TNode*)malloc(sizeof(TNode)); 
    tree->lchild->lchild = NULL; 
    tree->lchild->rchild = NULL; 
    tree->rchild = (TNode*)malloc(sizeof(TNode)); 
    tree->rchild->lchild = (TNode*)malloc(sizeof(TNode)); 
    tree->rchild->rchild = NULL; 
    tree->rchild->lchild->lchild = NULL; 
    tree->rchild->lchild->rchild = NULL; 
    printf("the depth of the tree is:%d\n",CalDepth(tree)); 
    return 0; 
}

232126944