求解二叉树的深度

6-06 2,891 views

思路：
采用递归求解，对于树tree的深度，其值为：
Depth(tree) =
max(Depth(tree的左子树),Depth(tree的右子树)),tree != NULL
0,tree == NULL

代码：

#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; 
}

#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;

}

版权属于: 我爱我家

原文地址: http://magicwt.com/2012/06/06/%e6%b1%82%e8%a7%a3%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e6%b7%b1%e5%ba%a6/

转载时必须以链接形式注明原始出处及本声明。