已知二叉树的层序和中序遍历序列，或已知二叉树的先序序列、中序序列，是编写算法建立该二叉树（用递归或非递归的方法都可以）
任务：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；
#include <string> #include <iostream> #include <stdlib.h> #include <stdio.h> #include <string.h> #include <vector> #include <queue> #define MAXQSIZE 1000 using namespace std; //二叉链表表示二叉树 typedef struct BiNode { char data;//节点数据 struct BiNode * lchild;//左孩子 struct BiNode * rchild;//右孩子 }BiNode, * BiTree; string presequence,insequence,sequence; int len; //由前序序列和中序序列建立二叉树的过程 void CreateBiTree(BiTree & t,string presequence,string insequence)//t为要建立的二叉树,presequence和insequence分别为前序和中序序列 { if(presequence.length()==0) { t=NULL; return ; } char rootNode=presequence[0];//根 int index=insequence.find(rootNode);//根在中序序列中的位置 string lchild_insequence=insequence.substr(0,index);//左孩子的中序序列 string rchild_insequence=insequence.substr(index+1);//右孩子的中序序列 int lchild_length=lchild_insequence.length();//左孩子的长度 int rchild_length=rchild_insequence.length();//右孩子的长度 string lchild_presequence=presequence.substr(1,lchild_length);//左孩子的前序序列 string rchild_presequence=presequence.substr(1+lchild_length);//右孩子的前序序列 t=(BiTree)malloc(sizeof(BiNode)); if(t!=NULL) { t->data=rootNode; CreateBiTree(t->lchild,lchild_presequence,lchild_insequence);//递归创建左孩子 CreateBiTree(t->rchild,rchild_presequence,rchild_insequence);//递归创建右孩子 } } void CreateBiTree2(BiTree &root,char data,int index) { if(root==NULL) { root=(BiTree)malloc(sizeof(BiNode)); root->lchild=NULL; root->rchild=NULL; root->data=data;//cout<<"data="<<data<<endl; return; } int u; for(u=0;u<len;u++) { if(insequence[u]==root->data)break; } if(u<index)CreateBiTree2(root->rchild,data,index); else CreateBiTree2(root->lchild,data,index); } BiTree CreatBitree3(BiTree &root) { for(int i=0;i<len;i++) { int u; for(u=0;u<len;u++) if(insequence[u]==sequence[i])break; CreateBiTree2(root,sequence[i],u); } return root; } void PreOrderTraverse(BiTree & t) { if(t!=NULL) { cout<<t->data; PreOrderTraverse(t->lchild); PreOrderTraverse(t->rchild); } } //递归中序序遍历二叉树 void InOrderTraverse(BiTree & t) { if(t!=NULL) { InOrderTraverse(t->lchild); cout<<t->data; InOrderTraverse(t->rchild); } } void PostOrderTraverse(BiTree &T){///后序遍历二叉树的递归算法 if (T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout<<T->data; } } typedef struct{ BiTree base[MAXQSIZE]; int front,rear; }SqQueue; void InitQueue(SqQueue &q) { q.front=q.rear=0; } void LevelOrderTraverse(BiTree T) { BiTree p; SqQueue Q; InitQueue(Q); if (T){ Q.base[Q.rear]=T; Q.rear=(Q.rear+1)%MAXQSIZE; while (Q.front !=Q.rear) { p=Q.base[Q.front]; printf("%c",p->data); Q.front=(Q.front+1)%MAXQSIZE; if (p->lchild) { Q.base[Q.rear]=p->lchild; Q.rear=(Q.rear+1)%MAXQSIZE;} if (p->rchild) { Q.base[Q.rear]=p->rchild; Q.rear=(Q.rear+1)%MAXQSIZE;} } } } void init1(string &a,string &b) { cout<<"输入先序遍历序列\n"; cin>>a; cout<<"输入中序遍历序列\n"; cin>>b; } int init2(string &a,string &b) { cout<<"输入层序遍历序列\n"; cin>>a; cout<<"输入中序遍历序列\n"; cin>>b; int aa=a.length(); return aa; } void show(BiTree t) { cout<<"先序： "; PreOrderTraverse(t); cout<<"\n中序： "; InOrderTraverse(t); cout<<"\n后序： "; PostOrderTraverse(t); cout<<"\n层序： "; LevelOrderTraverse(t); cout<<endl; } int main() { BiTree t,q=NULL; init1(presequence,insequence); CreateBiTree(t,presequence,insequence); show(t); len=init2(sequence,insequence); q=CreatBitree3(q); show(q); return 0; }
测试数据：
abdgheicfjk gdhbeiacjfk abcdefghijk gdhbeiacjfk
