二叉树 数据结构

建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序，中序，后序），打印输出结果。
要求：从键盘接受输入先序序列，一二叉链表作为存储结构，建立二叉树，并对其进行遍历（先序，中序，后序）并判断是否为满二叉树。打印遍历结果。要求用递归方法实现

---

#include<iostream>
#include<cmath>//提供pow()函数
using namespace std;

#define OK 1
#define ERROR 0

typedef int Status;
typedef struct BiTNode
{
int data;
struct BiTNode *lChild,*rChild;
}BiTNode,*BiTree;

//先序输出二叉树
void PreOrderTraverse(BiTree T)
{
if(T)
{
cout<<T->data<<' ';
PreOrderTraverse(T->lChild);
PreOrderTraverse(T->rChild);
}
}

//中序输出二叉树
void InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lChild);
cout<<T->data<<' ';
InOrderTraverse(T->rChild);
}
}

//后序输出二叉树
void PostOrderTraverse(BiTree T)
{
if(T)
{
PostOrderTraverse(T->lChild);
PostOrderTraverse(T->rChild);
cout<<T->data<<' ';
}
}

//创建二叉树
Status CreateBiTree(BiTree& T)
{
int num;
cin>>num;
if(num==0)
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
T->data=num;
CreateBiTree(T->lChild);
CreateBiTree(T->rChild);
}
return OK;
}

//计算二叉树的深度
int BiTreeDepth(BiTree T)
{
int depth1,depth2;
if(!T)
return 0;
else{
depth1=BiTreeDepth(T->lChild);
depth2=BiTreeDepth(T->rChild);
if(depth1>depth2)
return depth1+1;
else
return depth2+1;
}
}

static int n=0;
int CountNode(BiTree T)
{
if(T)
{
n++;
CountNode(T->lChild);
CountNode(T->rChild);
}
return n;
}

//计算深度为depth的满二叉树的结点数
inline int Count(int depth)
{
return pow(2,depth)-1;/腊汪/满二叉树的结点计算法
}

int main()
{
int depth,num;
BiTree T;
cout<<"默认为先序输入二叉树数据(以0为空格字符)。"<<endl;
cout<<"例如者芦:只有一个结点的二叉树,输入形式为:1 0 0"<<endl<<endl;;
cout<<"现在,请您输入"<<endl;
if(CreateBiTree(T))
{
cout<<"先序结果为:"<<endl;
PreOrderTraverse(T);
cout<<endl<<endl;
cout<<"中序结果为:"<<endl;
InOrderTraverse(T);
cout<<endl<<endl;
cout<<"后序结果为:"轮嫌仔<<endl;
PostOrderTraverse(T);
cout<<endl<<endl;
depth=BiTreeDepth(T);
num=CountNode(T);
if(num==Count(depth))//
cout<<"二叉树为满二叉树。"<<endl;
else
cout<<"二叉树不是满二叉树。"<<endl;
}
return 0;
}

我已经调试过了，可以通过。你调试的时候，记得输入二叉树要先序输入，以0为空格字符

---