#include<iostream>
using namespace std;
typedef struct Tree{
struct Tree *lchild,*rchild;
int data;
}TNode,*BiTree;
BiTree Search(BiTree T,int data,BiTree f,BiTree &p)
{// f初始值是NULL， 指向T的双亲
if(!T) p = f;
else if( T->data == data) p = T;
else if( T->data < data ) return Search(T->lchild,data,T,p);
else return Search(T->rchild,data,T,p);
}
void insert(BiTree &T,int data)
{
BiTree p,s;
if(!Search(T,data,NULL,p))
{
s = (BiTree)malloc(sizeof(TNode));
s->data = data; s->lchild = s->rchild = NULL;
if(!p) T = s;
else if(p->data > data) p->lchild = s;
else p->rchild = s;
}
}
void creatBiTree(BiTree &T)
{
int data;
do{
cin>>data;
insert(T,data);
}while(data!=0);
}
void printBiTree(BiTree &T)
{
if(T)
{
cout<<T->data<<endl;
printBiTree(T->lchild);
printBiTree(T->rchild);
}
}
int main()
{
BiTree t;
creatBiTree(t);
printBiTree(t);
system("pause");
return 0;
}

给你我的程序看看



#include <iostream.h>
#include <malloc.h>
#include <iomanip.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define length 50
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int CreateBiTree(BiTree &BT) //先序次序输入二叉树中节点的值，空格表示空树
{
char ch;
cin>>ch;
if (ch== '/') BT=NULL;
else
{
BT=(BiTNode *)malloc(sizeof(BiTNode)); //构造新结点
BT->data=ch;
CreateBiTree(BT->lchild); //构造左子树
CreateBiTree(BT->rchild); //构造右子树
}
return OK;
}
//先序遍历
void PreTraverse(BiTree BT)
{
if(BT!=NULL)
{
cout<<BT->data;
PreTraverse(BT->lchild);
PreTraverse(BT->rchild);
}
}
// 中序遍历
void InTraverse(BiTree BT){
if (BT!=NULL){
InTraverse(BT->lchild);
cout<<BT->data;
InTraverse(BT->rchild);
}
}
//后序遍历
void LastTraverse(BiTree BT){
if (BT!=NULL){
LastTraverse(BT->lchild);
LastTraverse(BT->rchild);
cout<<BT->data;
}
}
//层次遍历
void LevelTraverse(BiTree BT){
BiTree array[length],pos;
int front,end; //头尾指针
array[1]=BT;
front=end=1;
while (front<=end){ //出队
pos=array[front];
front++;
cout<<pos->data<<" ";
if(pos->lchild!=NULL)
{
end++;
array[end]=pos->lchild;
}
if(pos->rchild!=NULL)
{
end++;
array[end]=pos->rchild;
}
}
}

//计算节点数目
void Node(BiTree BT,int *count1){
if(BT){
(*count1)++;
Node(BT->lchild,count1);
Node(BT->rchild,count1);
}
}
//计算叶子节点数目
void Leaf(BiTree BT,int *count2)
{
if (BT)
{
Leaf(BT->lchild,count2);
if (BT->lchild==NULL && BT->rchild==NULL)
(*count2)++;
Leaf(BT->rchild,count2);
}
}
//计算二叉树的高度，其中h1和h2分别是以BT为根的左右子树的高度
int hight(BiTree BT)
{
int h1=0,h2=0;
if (BT==NULL)
return ERROR;
else
{
h1=hight(BT->lchild);
h2=hight(BT->rchild);
if(h1<h2)
{
int c=h1;
h1=h2;
h2=c;
}
h1++;
}
return h1;
}
//交换左右二叉数
void Change_Left_Right(BiTree BT)
{
if(BT)
{
Change_Left_Right(BT->lchild);
Change_Left_Right(BT->rchild);
BiTree k=BT->lchild;
BT->lchild=BT->rchild;
BT->rchild=k;
}
}
void main()
{
int x=0;
int count1=0,count2=0;
BiTree BT;
cout<<"please input the value of node"<<endl;
CreateBiTree(BT);
if(BT==NULL)
cout<<"The BiTree is Empty."<<endl;
else{
cout<<"先序遍历为"<<endl;
PreTraverse(BT);
cout<<endl;

cout<<"中序遍历为"<<endl;
InTraverse(BT);
cout<<endl;

cout<<"后序遍历为"<<endl;
LastTraverse(BT);
cout<<endl;

cout<<"层次遍历为:"<<endl;
LevelTraverse(BT);
cout<<endl;

//交换左右二叉数
Change_Left_Right(BT);
cout<<"交换左右二叉数后先序遍历为"<<endl;
cout<<BT->data;
PreTraverse(BT->lchild);
PreTraverse(BT->rchild);

Node(BT,&count1);
cout<<"节点个数为："<<count1<<endl;

Leaf(BT,&count2);
cout<<"叶子结点个数:"<<count2<<endl;

cout<<"二叉树高度:"<<hight(BT)<<endl;

}
}