首页 > 代码库 > 二叉树先序遍历中序遍历求后序遍历
二叉树先序遍历中序遍历求后序遍历
先序遍历:根 左 右
中序遍历:左 根 右
后序遍历:左 右 根
我们可以先从先序遍历中找到根节点,由于知道了根节点那么可以依靠中序遍历找到左子树,右子树。这样再去先序遍历中找到左子树的根节点,然后再依靠中序遍历找到左子树的左子树(右子树同理)。这样层层递归就能还原二叉树。之后求出后序遍历。
感谢原博主http://www.cnblogs.com/rain-lei/p/3576796.html 一开始递归不会写,看了博主的发现其实很简单。注意还原二叉树时return root。
#include<stdio.h> int n; typedef struct btnode{ int data; struct btnode *left; struct btnode *right; }treenode; //定义二叉树节点 int preorder[1001]; //先序遍历 int inorder[1001]; //中序遍历 treenode *gettree(int prel,int prer,int inl,int inr){ //根据先序中序还原二叉树 if(prel>prer) return NULL; treenode *root; root=new treenode; root->data=http://www.mamicode.com/preorder[prel]; if(prel==prer){ root->left=NULL; root->right=NULL; return root; } int temp; //记录根节点在中序遍历中的位置 for(int i=1;i<=inr;i++) if(inorder[i]==preorder[prel]){ temp=i; break; } root->left=gettree(prel+1,prel+(temp-inl),inl,temp-1); //还原左子树 root->right=gettree(prel+(temp-inl)+1,prer,temp+1,inr);//还原右子树 return root; } void postorder(treenode *t){ //后序遍历二叉树 if(t!=NULL){ postorder(t->left); postorder(t->right); printf("%d\n",t->data); } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&preorder[i]); for(int i=1;i<=n;i++) scanf("%d",&inorder[i]); treenode *tree=gettree(1,n,1,n); postorder(tree); }
二叉树先序遍历中序遍历求后序遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。