分治法求解二叉树深度
YOYO
posted @ 2009年4月29日 08:05
in 【算法】与【数据结构】
with tags
分治
, 3012 阅读
若一个树没有孩子，则它的深度为1；
若一个树只有左孩子，则它的深度就是左孩子的深度+1；
若一个树只有右孩子，则它的深度就是右孩子的深度+1；
若一个树有两个孩子，则它的深度就是两个孩子中较深的那颗深度+1。
由此可以递归得到该树的高度。
-
#include<iostream>
-
using namespace std;
-
-
/* 二叉树数据结构 */
-
typedef struct node{
-
int value;
-
struct node * lchild; // 左子树
-
struct node * rchild; // 右子树
-
}Node;
-
-
/* 创建二叉树函数：返回该结点的值 */
-
Node* create(){
-
int v;
-
cin>>v; // 输入结点的值
-
if(v==0)return NULL; // 输入为0时表示该结点为空
-
Node* p = new Node; // 为结点开辟空间
-
p->value = v;
-
p->lchild = create(); // 创建左子树
-
p->rchild = create(); // 创建右子树
-
return p;
-
}
-
-
/* 计算二叉树深度函数：返回该树的深度 */
-
int countDepth(Node* p){
-
if(p==NULL)return 0; // 如果结点为空，深度为0
-
int left = countDepth(p->lchild)+1; // 获得左子树的深度
-
int right = countDepth(p->rchild)+1; // 获得右子树的深度
-
return left>right?left:right; // 树的深度就是左右子树中较深的那颗深度+1
-
}
-
-
int main(){
-
Node* p = create(); // 创建树
-
cout<<countDepth(p)<<endl; // 输出树的深度
-
return 0;
-
}
评论 (0)
