Question

假设二叉树采用二叉链存储结构，设计一个算法Level o 求二叉树中制定结点的层数。

写出类型定义，算法加注释。

Answer 1

法1：
template<class T>
int tree<T>::tree_level(tree_node<T> *root)//利用递归：
{
if(root==NULL)
return 0;
else
{
int l_level=tree_level(root->rchild);//记录左子树的层数
int r_level=tree_level(root->rchild);//记录右子树的层数
return l_level>r_level?l_level+1:r_level+1;//选择左右层数较大的一个+1返回
}
}

法2：
template<class T>
void tree<T>::tree_level(tree_node<T> *root,int level,int& deth)//
{//用level记录当前的层数
if(root!=NULL)
{
if(level>deth)
{
deth=level;//deth和当前层数level比较，取较大值
}
tree_level(root->lchild,level+1,deth);//level+1看其左子树
tree_level(root->rchild,level+1,deth);//level+1看其右子树
}
}

Answer 2

// bzl.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "math.h"
typedef struct Bnode{
char data;
struct Bnode *lchild,*rchild;
}Bnode;
int i=0;
char *s="abc de g f ";
void preorder(Bnode *);
void visite(Bnode *);
void createTree(Bnode * &p){

if(s[i]!=' '){
p=new Bnode;
p->data=s[i];
i++;
createTree(p->lchild);
createTree(p->rchild);
}
else
{
p=NULL;i++;
}

}

int high(Bnode *T){
int r_lever,l_lever;
if(T==NULL)
return 0;
else{
r_lever=high(T->lchild)+1;
l_lever=high(T->rchild)+1;
if(a>b)
return r_lever;
else return l_lever;
}

}

int _tmain(int argc, _TCHAR* argv[])
{
int lever;
Bnode *p;
createTree(p);
lever=high(p);
printf("二叉树的深度为：%d",lever);

printf("\n");

return 0;
}