Question

假设以二叉链表作为二叉树的存储结构，试编写一个求树的高度的算法

假设以二叉链表作为二叉树的存储结构，试编写一个找出给定值的结点的算法

Answer 1

#include<iostream.h>
#include<malloc.h>

#define FALSE 0
#define TRUE 1
#define OK 1
#define maxsize 100
typedef int status;
typedef int elemtype;

typedef struct binode
{
elemtype data;
struct binode *lchild,*rchild;
}binode,*bitree;

status treecreated=FALSE;
int leafcount=0;

status createbitree(bitree *t);
status preordertraverse(bitree t);
int height(bitree t);
void swap(bitree *t);
void leafcounts(bitree t);

void main()
{
int choice=0;
status leave=FALSE,flag;
binode *bt;
cout<<"===========二叉树演示程序==============="<<endl;
do
{
cout<<"1：创建一个二叉树，按先序遍历结果输入，空用0表示 "<<endl;
cout<<"2：先序遍历二叉树，递归方式遍历二叉树 "<<endl;
cout<<"3：求叶子数"<<endl;
cout<<"4：计算二叉树的高度"<<endl;
cout<<"5: 树进行左右翻转"<<endl;
cout<<"0：退出"<<endl;
cout<<"-------请输入你的选择:"<<endl;
cin>>choice;
switch(choice)
{
case 1:
if(treecreated)
{
cout<<"sorry,the tree has been already created!"<<endl;
break;
};
cout<<"请输入代表树的数字："<<endl;
flag=createbitree(&bt);
if(flag==OK)
{
cout<<"你已经建立了一棵树了！"<<endl;
treecreated=TRUE;
}
break;

case 2:
if(!treecreated)
{
cout<<"sorry,you must create a tree for further steps!"<<endl;
break;
}
cout<<"先序遍历顺序:"<<endl;
preordertraverse(bt);
cout<<endl;
break;

case 3:
if(!treecreated)
{
cout<<"sorry,you must create a tree for further steps!"<<endl;
break;
}
leafcounts(bt);
cout<<"树的叶子数:"<<leafcount<<endl;
cout<<endl;
break;

case 4:
int h;
h=height(bt);
cout<<"树的高度:"<<h<<endl;
break;

case 5:
swap(&bt);
cout<<"树已经翻转！！！"<<endl;
break;

case 0:
leave=TRUE;
break;
}
}while(!leave);
cout<<" 谢谢 再见了！！！"<<endl;
}
//递归方法实现创建
status createbitree(bitree *t)
{
int ch=0;
cin>>ch;
if(ch==0) //输入如果是0表示是空
(*t)=NULL;
else
{
(*t)=(bitree)malloc(sizeof(binode)); //申请空间
(*t)->data=ch; //把数据传给他
createbitree(&(*t)->lchild); //左孩子重新进入创建函数
createbitree(&(*t)->rchild); //右孩子重新进入创建函数
}
return OK;
}

//递归方法实现先序遍历
status preordertraverse(bitree t)
{
if(t)
{
cout<<t->data<<" "; //先把头结点输出
preordertraverse(t->lchild); //然后是左结点
preordertraverse(t->rchild); //然后是右结点
return OK;
}
else
return OK;
}

int height(bitree t)
{
int hl,hr;
if(t==NULL)
return 0;
hl=height(t->lchild)+1; //最下面的左孩子加一
hr=height(t->rchild)+1; //最下面的右孩子加一
return (hl>hr?hl:hr); //比较谁大就取谁
}

void swap(bitree *t) //进行左右翻转
{
bitree p;
if(*t!=NULL)
{
p=(*t)->lchild; //p为中间变量
(*t)->lchild=(*t)->rchild;
(*t)->rchild=p;
swap(&(*t)->lchild);
swap(&(*t)->rchild);
}
}

void leafcounts(bitree t) //求叶子数
{
if(t) //如果不为空
{
if(t->lchild==NULL && t->rchild==NULL)//左右孩子都为空 表明是叶子
leafcount++;
leafcounts(t->lchild);
leafcounts(t->rchild);
}
}

Answer 2

int length(BiTree T)
{
int h1,h2;
if(T==NULL) return 0;
if(T->lchild==NULL && T->rchild==NULL) return 1;
h1=length(T->lchild);
h2=length(T->rchild);
return h1>=h2?h1:h2;
}

BiTree Find(BiTree T,ElemType x) //该函数返回给定值的结点的指针
{
BiTree t;
if(T==NULL) return NULL;
if(T->data==x) return T;
if(t=Find(T->lchild)) return t;
if(t=Find(T->rchild)) return t;
return NULL;
}

Answer 3

#include<iostream>
using namespace std;
template <class T>
struct BiNode
{T data;BiNode<T>*lchild,*rchild;};
template <class T>
class BiTree
{
public:
BiTree(){root=Creat(root);}
void PreOrder(){PreOrder(root);}
int Deepth(){ return Deepth(root);}
int Empty();
private:
BiNode<T>*root;
BiNode<T>*Creat(BiNode<T>*bt);
int Deepth(BiNode<T>*bt);
};
template<class T>
BiNode<T>*BiTree<T>::Creat(BiNode<T>*bt)
{ char ch;
cin>>ch;
if(ch=='#')bt=NULL;
else{
bt=new BiNode<T>;bt->data=ch;
bt->lchild=Creat(bt->lchild);
bt->rchild=Creat(bt->rchild);
}
return bt;
}
template<class T>
int BiTree<T>::Empty()
{
if(root==NULL)return 1;
else return 0;
}
template<class T>
int BiTree<T>::Deepth(BiNode<T>*bt)//求深度的算法
{ int nl,nr;
if(bt==NULL) return 0;
else
{
nl=Deepth(bt->lchild);
nl++;
nr=Deepth(bt->rchild);
nr++;
if(nl>nr)return nl;
else return nr;
}
}
int main()
{ int t;
while(1)
{
BiTree<char> Bt;
cout<<Bt.Deepth()<<endl;
t=Bt.Empty();
if(t==1)break;
}
return 0;
}

Answer 4

int BTNodeDepth (BTNode *t)
{
int lchildh, rchildh;
if (t == NULL)
return 0;
else
{
lchildh = BTNodeDepth (t->lch);
rchildh = BTNodeDepth (t->rch);
return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1);
}
}