题目描述

求二叉树的先序、中序及后序遍历序列。结点数<=100。

输入

按先序遍历的顺序建立一个二叉树，为了保证树的唯一性，并在程序中的递归出口是左右子树为空，故输入时，当某结点的左子树或右子树为空值时也要作为先序遍历的有效输入。例如一个树只有3个结点，根结点值为1，其左孩子结点值为2，其右孩子结点值为3，则输入的先序遍历序列依次为1　2　0　0  3　0　0（为空时输入0值）*/

输出

在三行上，依次输出二叉树的先序、中序及后序遍历序列。序列中各数用空格隔开。

样例输入 Copy

1 2 0 0 3 0 0

样例输出 Copy

1 2 3
2 1 3
2 3 1

主要思路：

本题运用的主要思想是递归，然后树的存储方式有两种，一种是运用一维数组顺序存储，另一种也是本节用的是链式存储，最后还是说下递归，掌握它很重要(本体中无论是构造还是遍历输出树都用到了这种方法，很方便的说）

#include<iostream>
#include<cstdlib>
#include<cstdio>
 
using namespace std;
 
typedef struct BiTNode{
    int data;               //定义节点值
    struct BiTNode *lchild;//定义左子树
    struct BiTNode *rchild;//定义右子树
}BiTNode,*BiTree;
 
void create(BiTree &T)
{
    int ch;
    cin>>ch;
    if(!ch)//如果输入不是整数
    T=NULL;
    else {
        T=new BiTNode;//分配这个节点的空间
        T->data=ch;    
        create(T->lchild);//遍历建立左子树
        create(T->rchild);//遍历建立右子树
    }
}
 
void pre(BiTree &T);//前序
  
void mid(BiTree &T);//中序
  
void last(BiTree &T);//后序
 
int main()
{
    BiTree T;
    create(T);
    pre(T);
    cout<<endl;
    mid(T);
    cout<<endl;
    last(T);
    cout<<endl;
    return 0;
}
 
void last(BiTree &T)
{
    if(T){
        last(T->lchild);
        last(T->rchild);
        cout<<T->data<<" "; 
    }
}
 
void mid(BiTree &T)
{
    if(T){
        mid(T->lchild);
        cout<<T->data<<" ";
        mid(T->rchild);
    }
} 
 
void pre(BiTree &T)
{
    if(T){
        cout<<T->data<<" ";
        pre(T->lchild);
        pre(T->rchild);
    }
}