这个树结构怎么写啊
二叉树的前序、中序、后序遍历的定义：前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。
拷贝下面的代码，完成相应的函数。
//给定前序遍历和中序遍历，求其后序遍历
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
typedef char TElemType;
//二叉树的二叉链表存储表示
typedef struct BiTNode {
TElemType data; //结点数据域
struct BiTNode *lchild, *rchild; //左右孩子指针
} BiTNode, *BiTree;
//根据先序序列pre和中序序列in建树t
void BuildTree(BiTree& t, char pre[], int pre_low, char in[], int in_low, int len)
{
/****在此下面完成代码************/
/*********************************/
}
// 后序遍历采用递归算法或非递归算法
void PostOrderTraverse(BiTree t)
{
/****在此下面完成代码************/
/*********************************/
}
void DestroyBitree(BiTree& t)
{
/****在此下面完成代码************/
/*********************************/
}
int main()
{
char pre, in;
BiTree t = NULL;
while(cin >> pre) {
cin >> in;
BuildTree(t, pre, 0, in, 0, strlen(in));
PostOrderTraverse(t);
DestroyBitree(t);
cout << endl;
}
}
页:
[1]