根据后序和中序遍历输出先序遍历C++

知识点:

先序:中左右

中序:左中右

后序:左右中

#include 
using namespace std;typedef struct BiNode{//创建一个结点int data;BiNode *lchild;BiNode *rchild;
}BiNode,*BiTree;//递归创建二叉树,三个形参
//第一个是储存后序遍历的数组
//第二个是中序遍历的数
//第三个是组数的长度BiTree Createtree(int *postOrder,int *inOrder,int n)
{BiTree T;if(n<=0)return NULL;T=new BiNode;int mid=0;for(int i=0;idata=postOrder[n-1];//后序最后一个结点是树根T->lchild=Createtree(postOrder,inOrder,mid);//递归创建左子树T->rchild=Createtree(postOrder+mid,inOrder+mid+1,n-mid-1);//递归创建右子树return T;
}int flag=0;
void prePrint(BiTree T) //先序遍历的递归方法
{if(!T)return;if(!flag){cout<data;//访问第一个不加空格flag=1;}elsecout<<" "<data;prePrint(T->lchild);prePrint(T->rchild);}int main() {int n;BiTree T;cin>>n;int postOrder[n];//放后序遍历int inOrder[n];//放中序遍历for(int i=0;i>postOrder[i];}for(int i=0;i>inOrder[i];}T=Createtree(postOrder,inOrder,n);//创建二叉树cout<<"Preorder: ";prePrint(T);//先序遍历二叉树的递归函数return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！