星期三

二叉树的链式结构

二叉树的数据结构：

typedef struct Node
{
char data;
struct Node *lchild,*rchild;
}*Bitree,BiNode;

分别为根，左孩子，右孩子

二叉树的创建，先序遍历的方式

如输入  “AB#CD###E#F##”

void creatBitree(Bitree &T)
{
char ch;
cin>>ch;
if(ch=='#')
T=NULL;
else
{
T=new BiNode;
T->data=ch;
creatBitree(T->lchild);
creatBitree(T->rchild);
}
}

二叉树的中序遍历：

void InOrderTraverse(Bitree T)
{
if(T)
{
InOrderTraverse(T->lchild);
cout<<T->data;   //访问该节点
InOrderTraverse(T->rchild);
}
}

二叉树的后序遍历 ：

void PostOrderTraverse(Bitree T)
{
if(T)
{
InOrderTraverse(T->lchild);
InOrderTraverse(T->rchild);

cout<<T->data;
}
}