题目：二叉树操作验证（c++改成c）

题目：二叉树操作验证

1.实验目的

(1)掌握二叉树的逻辑结构

(2)掌握二叉树的二叉链表存储结构；

(3)掌握基于二叉链表存储的二叉树的遍历操作的实现。

2.实验内容

(1) 建立一棵含有n个结点的二叉树，采用二叉链表存储；

(2) 前序（或中序、后序）遍历该二叉树。

3.实现提示

二叉链表的结点结构如图所示。

lchild

data

rchild

图 二叉树的结点结构

二叉链表的结点用C++中的结构类型描述为：

template <class T>

struct BiNode

｛

T data；

BiNode<T> * lchild，*rchild；

｝；

设计实验用二叉链表类BiTree，类中包含遍历操作。

template <class T>

class BiTree

｛

public：

BiTree(BiNode<T> *root)；//有参构造函数,初始化一棵二叉树，

//其前序序列由键盘输入

~BiTree（）； //析构函数，释放二叉链表中各结点的存储空间

void PreOrder(BiNode<T> *root)；//前序遍历二叉树

void InOrder(BiNode<T> *root)；//中序遍历二叉树

void PostOrder(BiNode< T＞ *root)； //后序遍历二叉树

private：

BiNode<T＞ *root； //指向根结点的头指针

void Creat(BiNode<T> *root)； //有参构造函数调用

void Release(BiNode<T>*root)； //析构函数调用

｝；

设计构造函数，建立一棵二叉树的二叉链表存储。

将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如＃，以标识其为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。扩展二叉树的一个遍历序列就能惟一确定一棵二叉树。假设扩展二叉树的前序遍历序列由键盘输人，root为指向根结点的指针，二叉链表的建立过程是：首先输人根结点，若输人的是一个＃字符，则表明该二叉树为空树，即root =NULL；否则输人的字符应该赋予root ->data，之后依次递归建

立它的左子树和右子树。建立二叉链表的递归算法如下：

二叉树的构造函数算法BiTree

template<class T>

BiTree :: BiTree (BiNode<T> *root)

{

root = creat( );

}

template <class T>

BiNode<T> * BiTree :: Creat( )

{

Cin>>ch;

if (ch = =’#’) return NULL; //建立一棵空树

else{

root = new BiNode<T>; //生成一个结点

root ->data = ch;

root ->lchild = Creat( ); //递归建立左子树

root ->rchile = Creat( ); //递归建立右子树

}

}

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>

struct BiTreeNode
{
char data;
struct BiTreeNode *rchild;
struct BiTreeNode *lchild;
};

void Create(struct BiTreeNode *&Tnode) //先序创建2叉链表
{
char ch;
cin>>ch;
if(ch=='#')
{
Tnode=NULL;
}
else
{
Tnode=new BiTreeNode;
Tnode->data=ch;
Create(Tnode->lchild);
Create(Tnode->rchild);
}
}

void PreOrder(struct BiTreeNode *&Tnode) //先序遍历2叉链表
{
struct BiTreeNode *p;
p=Tnode;
if(Tnode)
{
cout<<Tnode->data<<" ";
PreOrder(Tnode->lchild);
PreOrder(Tnode->rchild);
}
}
void InOrder(struct BiTreeNode*&Tnode)//中序遍历2叉表
{
struct BiTreeNode *p;
p=Tnode;
if(Tnode)
{
InOrder(Tnode->lchild);
cout<<Tnode->data<<" ";
InOrder(Tnode->rchild);
}
}
void PostOrder(struct BiTreeNode *&Tnode)//后序遍历2叉链表
{
struct BiTreeNode *p;
p=Tnode;
if(Tnode)
{

PostOrder(Tnode->lchild);
PostOrder(Tnode->rchild);
cout<<Tnode->data<<" ";
}
}

int main()
{
struct BiTreeNode *Tnode;
Create(Tnode);
PreOrder(Tnode);
cout<<endl;
InOrder(Tnode);
cout<<endl;
PostOrder(Tnode);
cout<<endl;
return 0;
}

输入 ab##cd###

输出 先序a b c d
中序b a d c
后序b d c a

是不是还得给你做完

(1) 建立一棵含有n个结点的二叉树，采用二叉链表存储；

(2) 前序（或中序、后序）遍历该二叉树。

这俩要求？