实用数据结构总结之二叉树遍历

二叉树简单总结：
二叉树节点结构：
struct Node{
Node *lchild;//指向其左儿子节点的指针，当其不存在左儿子时为NULL
Node *rchild;//指向其右儿子节点的指针，当其不存在右儿子时为NULL
/*
节点附加信息
.....
*/
}
对于该结构，先序遍历，中序遍历，后序遍历分别为：
先序遍历：

void preOrder(Node *Tree)
{
/*
对当前节点Tree的遍历操作
*/
if(Tree->lchild !=NULL)//递归遍历左子树
preOrder(Tree->lchild);
if(Tree->rchild != NULL)//递归遍历右子树
preOrder(Tree->rchild);
return;
}

void inOrder(Node *Tree)
{
if(Tree->lchild !=NULL)//递归遍历左子树
preOrder(Tree->lchild);
/*
对当前节点Tree的遍历操作
*/
if(Tree->rchild != NULL)//递归遍历右子树
preOrder(Tree->rchild);
return;
}

void postOrder(Node *Tree)
{
if(Tree->lchild !=NULL)//递归遍历左子树
preOrder(Tree->lchild);
if(Tree->rchild != NULL)//递归遍历右子树
preOrder(Tree->rchild);
/*
对当前节点Tree的遍历操作
*/
return;
}
例题：通过先序遍历和中序遍历确定后序遍历
输入：
两个字符串，其长度n均小于等于26
第一行为先序遍历，第一行为中序遍历
输出：
输入样例为多组，对于每组测试用例，输出一行，为后序遍历字符串

#include <iostream>#include <cstring>using namespace std;struct Node//二叉树结点结构体{Node *lchild;//左儿子指针Node *rchild;//右儿子指针char c;//结点字符信息}Tree[50];//静态内存分配数组int loc;//静态数组中已经分配的结点个数Node *create()//申请一个结点空间，返回指向其的指针{Tree[loc].lchild = Tree[loc].rchild = NULL;//初始化左右儿子为空return &Tree[loc++];//返回指针，loc自增}char str1[30],str2[30];//先序和中序字符串void postOrder(Node *T)//后序遍历{if (T->lchild!=NULL)postOrder(T->lchild);if (T->rchild!=NULL)postOrder(T->rchild);   cout<<T->c;}Node *buildtree(int s1,int e1,int s2,int e2){//由字符串的先序遍历和中序遍历还原树，并返回其根节点，其中//其中先序遍历结果由str1[s1]到str1[e1],中序遍历结果由str2[s2]//到str2[e2]Node* ret = create();//为该树根结点申请空间ret->c = str1[s1];//先序遍历第一个字符int rootindex;for (int i=s2;i<=e2;i++){if (str2[i] == str1[s1]){rootindex = i;break;}}if (rootindex !=s2)//若左子树不为空{ret->lchild = buildtree(s1+1,s1+(rootindex -s2),s2,rootindex-1);}if (rootindex !=e2){ret->rchild = buildtree(s1+(rootindex - s2)+1,e1,rootindex+1,e2);}return  ret;}int main(){while(cin>>str1>>str2){loc = 0;int L1 = strlen(str1);int L2 = strlen(str2);Node * T = buildtree(0,L1-1,0,L2-1);postOrder(T);cout<<endl;}  //  system("pause");return 0;}