Question

二叉树的建立及基本操作

实验要求：
用C语言编程实现二叉树的基本操作，并完成下述函数功能：
(1) CreateBiTree( )：根据先序遍历序列生成一棵二叉树
(2) CountLeaf( )：统计该二叉树中叶子结点的个数
(3) InOrderTraverse( )：中序遍历二叉树
(4) PostOrderTraverse( )：后序遍历二叉树
在主函数main( )中调用各个子函数完成二叉树的基本操作。
[实现提示]
采用特殊符号，如*号表示空树的情况。
通过输入扩展的先序序列建立一棵二叉树。
[测试数据]
由学生自己确定，注意边界数据。
程序检查时，由老师提供用于建树的初始输入序列。

Answer 1

#include <stdio.h>
typedef struct node
{
char data;
struct node * lchild;
struct node * rchild;
}BTNode;

BTNode * PreCreate() //先序建立
{
char ch = getchar();
if (ch = '*')
return NULL;
else
{
BTNode *p = (BTNode *)malloc(sizeof(BTNode));
p->data = ch;
p->lchild = PreCreate();
p->rchild = PreCreate();
return p;
}

}

int leafNode(BTNode *t) //求叶子节点
{
if (t == NULL)
return 0;
else
{
int lleafCount = leafNode(t->lchild);
int rleafCount = leafNode(t->rchild);
if (!lleafCount && !rleafCount)
return 1;
else
return lleafCount + rleafCount;
}

}

void InOrderTraverse(BTNode *t)
{
InOrderTraverse(t->lchild);
printf("%c ", t->data);
InOrderTraverse(t->rchild);
}

void PostOrderTraverse(BTNode *t)
{
PostOrderTraverse(t->lchild);
PostOrderTraverse(t->rchild);
printf("%c ", t->data);

}

Answer 2

#include<iostream.h>
struct T
{
int a;
T *lch,*rch;
};

class B
{
public:
void creatBinaryTree(T *&p); //生成二叉树
void preorder(T *p); //先序遍历
void inorder(T *P); //中序遍历
void postorder(T *p); //后序遍历
int Q(T *p); //求深度
int P(T *p); //求叶子节点数
int max(int m,int n);

};
void B::creatBinaryTree(T *&p){
int m;
cout<<"Input a data : ";
cin>>m;
if(m!=0){
p=new T;
p->a=m;

creatBinaryTree(p->lch);
creatBinaryTree(p->rch);
}else p=NULL;
}
void B::preorder(T *p){
if(p!=NULL){
cout<<p->a<<' ';
preorder(p->lch);
preorder(p->rch);
}
}
void B::inorder(T *p){
if(p!=NULL){
inorder(p->lch);
cout<<p->a<<' ';
inorder(p->rch);
}
}
void B::postorder(T *p){
if(p!=NULL){
postorder(p->lch);
postorder(p->rch);
cout<<p->a<<' ';
}
}
int B::Q(T *p){
if(p==NULL) return 0;
else return max(Q(p->lch),Q(p->rch))+1;
}
int B::P(T *p){
if(p!=NULL){
if(p->lch==NULL&&p->rch==NULL) return P(p->lch)+P(p->rch)+1;
else return P(p->lch)+P(p->rch)+0;
}else return 0;
}
int B::max(int m,int n){
if(m>n) return m;
else return n;
}

void main()
{
B b;
T *p=NULL;
b.creatBinaryTree(p);
b.preorder(p);
cout<<endl;
b.inorder(p);
cout<<endl;
b.postorder(p);
cout<<endl;
cout<<b.Q(p)<<endl;
cout<<b.P(p)<<endl;
}

更完整的应该是字符串输入，你可以自己完善