-
2016-07-30 23:18:22
在做数据结构面试题的时候我们会经常发现有关二叉树的题目总是这样的
栗子:
已知某二叉树先序为……中序为……求后序
已知某二叉树中序为……后序为……求先序
需要注意的是(我们只能够通过已知先序中序求后序或已知中序后序求先序,而不能够已知先序和后序求中序)
下面总结一下两种题的做法
首先回顾知识点
- 二叉树先序遍历 根结点—->左子树—->右子树
- 二叉树中序遍历 左子树—->根结点—->右子树
- 二叉树后序遍历 左子树—->右子树—->根结点
这个非常好记忆,就是看根结点的位置就可以了
第一种
已知一个二叉树的先序遍历结果为:ABCDEFGH,中序遍历结果为BDCEAFHG,求该二叉树的后序遍历。思路:拿到这样的题,我们要先根据两种遍历顺序把原始二叉树画出来,然后再根据后序遍历的规则解出后序遍历。
解析:首先看先序遍历的第一个结点为A,那么根据先序遍历规则先访问根结点,那么A肯定是根结点了。然后根据中序遍历规则先访问左子树中间访问根结点。那么我们可以得出BCDE是根结点A的左子树FHG是根结点A的右子树。那么左子树BCDE当中又怎么排序呢?这个时候我们再来看先序遍历,A结点之后先序先遍历B,说明B一定是根
更多相关内容 -
已知先序中序求后序,已知中序后序求先序,小白一看就会,二叉树重建
2021-04-09 13:44:03知道任何一棵二叉树的先序和中序遍历的序列或者中序和后序的遍历序列,都能构造出唯一的一棵二叉树 下面先看一道PTA上的题引入思考 因为知道了先序遍历的特点,从第一个开始,都先从根开始。 把先序的根在中序中...二叉树的重构
先序遍历:根 -> 左 -> 右
中序遍历:左 -> 根 -> 右
后序遍历:左 -> 右 -> 根
知道任何一棵二叉树的先序和中序遍历的序列或者中序和后序的遍历序列,都能构造出唯一的一棵二叉树
下面先看一道PTA上的题引入思考
因为知道了先序遍历的特点,从第一个开始,都先从根开始。
把先序的根在中序中找到,以此分两分,左边是左子树,右边是右子树。递归分治重新生成一棵二叉树。已知先序中序求后序
代码如下:
#include <iostream> #include <string.h> #include <stdio.h> #include <algorithm> using namespace std; char pre[50],in[50]; typedef struct node{ char data; node *l,*r; }btnode,*btree; int n,sum; btree rebuildtree(int root,int start,int end) { if(start>end) return NULL; int i; for(i=start;i<=end;i++) { if(in[i]==pre[root]) break; } btree t=new btnode; t->data=pre[root]; t->l=rebuildtree(root+1,start,i-1); t->r=rebuildtree(root+i-start+1,i+1,end); return t; } void h(btree root,int ans) { if(root==NULL) return; sum=max(sum,ans); h(root->l,ans+1); h(root->r,ans+1); return; } int main() { int i; btree r; cin>>n; for(i=1;i<=n;i++) { cin>>pre[i]; } for(i=1;i<=n;i++) { cin>>in[i]; } r=rebuildtree(1,1,n); h(r,1); cout<<sum<<endl; return 0; }
已知中序后序求先序(原理相同)
代码如下:
#include <iostream> using namespace std; typedef struct node{ char data; node *l,*r; }btnode,*btree; char in[10005],post[10005]; int n; btree rebuildtree(int root,int start,int end) { if(start>end) return NULL; int i; for(i=start;i<=end;i++) { if(in[i]==post[root]) break; } btree t=new btnode; t->data=post[root]; t->r=rebuildtree(root-1,i+1,end); t->l=rebuildtree(root-end+i-1,start,i-1); return t; } void print(btree root) { if(root==NULL) return; cout<<root->data<<" "; print(root->l); print(root->r); return; } int main() { int i; cin>>n; for(i=0;i<n;i++) { cin>>in[i]; } for(i=0;i<n;i++) { cin>>post[i]; } btree t=rebuildtree(n-1,0,n-1); print(t); return 0; }
-
二叉树已知先序中序求后序,已知后序中序求先序
2017-07-27 21:36:57已知先序中序求后序public class BinaryTree1 { private Node root; public void postOrder(){ postOrder(root); } //二叉树构造完毕之后进行后续遍历 private void postOrder(Node localroot) { if(localr已知先序中序求后序
public class BinaryTree1 { private Node root; public void postOrder(){ postOrder(root); } //二叉树构造完毕之后进行后续遍历 private void postOrder(Node localroot) { if(localroot!=null){ postOrder(localroot.left); postOrder(localroot.right); System.out.print(localroot.data+" "); } } public void InitTree(int[] preOrder,int[] inOrder){ this.root=InitTree(preOrder,0,preOrder.length-1,inOrder,0,inOrder.length-1); } /** * * @param preOrder 先序遍历的数组 * @param start1 递归每次遍历的数据段在先序遍历数组中的起始位置 * @param end1 递归每次遍历的数据段在先序遍历数组中的终止位置 * @param inOrder 中序遍历的数组 * @param start2 递归每次遍历的数据段在中序遍历数组中的起始位置 * @param end2 递归每次遍历的数据段在中序遍历数组中的终止位置 * @return 返回本次递归所构造完毕的树的根节点(从子结点向上依次返回) */ private Node InitTree(int[] preOrder, int start1, int end1, int[] inOrder, int start2, int end2) { if(start1>end1||start2>end2){ return null; } int rootData=preOrder[start1]; Node head=new Node(rootData); int rootindex=findIndexInArray(inOrder,rootData,start2,end2); /** * offset为以本次递归构造的节点为根节点的左子树的节点个数 */ int offset=rootindex-start2-1; Node left=InitTree(preOrder,start1+1,start1+offset+1,inOrder,start2,start2+offset); Node right=InitTree(preOrder,start1+offset+2,end1,inOrder,rootindex+1,end2); head.left=left; head.right=right; return head; } //检索出递归方法每次构造的节点在中序遍历数组中的索引 public int findIndexInArray(int[] a,int x,int begin,int end){ for (int i = begin; i <=end; i++) { if(a[i]==x){ return i; } } return -1; } public static void main(String[] args) { BinaryTree1 biTree=new BinaryTree1(); int[] preOrder={2,1,8,7,4,3,6,5,7,9}; int[] inorder={1,2,3,4,5,6,7,7,8,9}; biTree.InitTree(preOrder,inorder); System.out.println("后序遍历"); biTree.postOrder(); } }
解释:假设先序数组A B D E C F 中序数组D B E A F C
已知中序后序求先序
public class BinaryTree2 { private Node root; public void preOrder(){ preOrder(root); } private void preOrder(Node localroot) { if(localroot!=null){ System.out.print(localroot.data+" "); preOrder(localroot.left); preOrder(localroot.right); } } public void initTree(int[] inOrder,int[] postOrder){ this.root=initTree(inOrder,0,inOrder.length-1,postOrder,0,postOrder.length-1); } private Node initTree(int[] inOrder, int start1, int end1, int[] postOrder, int start2, int end2) { if(start1>end1||start2>end2){ return null; } int rootdata=postOrder[end2]; Node head=new Node(rootdata); int rootindex=findIndexInArray(inOrder,rootdata,start1,end1); int offset=rootindex-1-start1; Node left=initTree(inOrder,start1,start1+offset,postOrder,start2,start2+offset); Node right=initTree(inOrder,rootindex+1,end1,postOrder,start2+offset+1,end2-1); head.left=left; head.right=right; return head; } public int findIndexInArray(int[] a,int x,int begin,int end){ for (int i = begin; i <=end; i++) { if(a[i]==x){ return i; } } return -1; } public static void main(String[] args) { BinaryTree2 biTree=new BinaryTree2(); int[] inorder={1,2,3,4,5,6,7,7,8,9}; int[] postOrder={1,3,5,6,4,7,7,9,8,2 }; biTree.initTree(inorder,postOrder); System.out.println("先序遍历"); biTree.preOrder(); } }
解释同上。。。。。。
-
【算法】【树】已知先序中序序列求后序序列(详细解释)
2021-12-14 14:46:20题目描述 如题所示,已知先序中序序列建树与求后序序列 算法原理 利用递归和分制的思想,找到当前树先序序列的根节点,然后找到对应中序序列的位置,然后根据根节点在中序序列中的位置来判断左右子树分别的位置,...题目描述
如题所示,已知先序中序序列建树与求后序序列
算法原理
利用递归和分制的思想,找到当前树先序序列的根节点,然后找到对应中序序列的位置,然后根据根节点在中序序列中的位置来判断左右子树分别的位置,然后继续对左右子树进行递归,最后得出结果
post(0, 0, 序列总长度-1);
void post(int root, int start, int end)
首先是递归函数进入,其中三个形参分别代表的含义为
root 先序序列中当前递归层中根节点的下标
start 中序序列中子树的最左下标(子树开始的下标)
end 中序序列中子树的最右下标(子树结束的下标)
if(start > end) return ;
递归结束的标志,因为子树的元素范围在下标[start,end]之内,当start>end的时候,说明以当前节点为空节点
int i = start;
这里的i相当于只在中序遍历中有效,这里的i对于查找根节点root的先序序列完全没有意义,仅代表root在中序序列中的下标位置
例子:
假设一棵二叉树为上面的形式,那么他的先序序列和中序序列为
先序序列 1 2 3 4 5 6 7 8 9 10 11 中序序列 4 3 5 2 7 6 8 1 10 9 11 递归原理:
重点要解释一下这里的两条递归语句,分别代表递归当前根节点的左子树和当前根节点的右子树
对于左子树
post(root + 1, start, i - 1); //递归左子树
根节点 左子树 右子树 先序序列 1 2 3 4 5 6 7 8 9 10 11 root root+1 根节点 左子树的根节点 左子树 根节点 右子树 中序序列 4 3 5 2 7 6 8 1 10 9 11 i-1 i start end 如图可见,当遍历左子树的时候,
对于先序序列,左子树的根节点为先序序列上一层根节点root的下一个节点,也就是root+1
对于中序序列,因为是左子树,所以启始start值不变,end应该为在中序序列中找到的根节点i的前一个节点也就是i-1
对于右子树
post(root + 1 + i - start, i + 1, end);
根节点 左子树 右子树 先序序列 1 2 3 4 5 6 7 8 9 10 11 root root+1 root+(i-start) root+(i-start)+1 根节点 左子树的根节点 左子树的元素个数=i-start 左子树 根节点 右子树 中序序列 4 3 5 2 7 6 8 1 10 9 11 i-1 i i+1 start end 中序序列中的启始位置和结束位置都比较好确定,启始位置为i+1,结束位置为end
主要的难点就在于root的确认,我们能知道在先序序列中,是按照根节点——左子树——右子树排列的,左子树的根节点在先序序列中就为本层的根节点+1(root+1),比较好确定,但是右子树的跟节点就没有那么好确认了,但是我们细想就可以知道,原本的根节点加上左子树的节点个数,那不就到了右子树了嘛,但是这个想法也不准确
首先左子树的节点个数可以根据中序序列来判断,为i-start,但是根节点加上左子树的节点总数(root+(i-start))仅仅代表了左子树的最右侧节点,再加1才能代表右子树的第一个端点
有这幅图就可以比较清楚的看出
那么就引出了另一个问题了为什么根节点不能直接是i+1,而是要绕这么大一个圈子回来呢?
这就需要下一步递归来判断了
父节点的左子树 父节点 新的根节点 左子树 右子树 父节点的右子树子树 先序序列 1 2 3 4 5 6 7 8 9 10 11 root 父节点的左子树 左子树 新的根节点 右子树 父节点 父节点的右子树 中序序列 4 3 5 2 7 6 8 1 10 9 11 i-1 i i+1 start end 这样就比较容易能看出来了,正确的根节点应该是6
但是i+1仅仅表示7,明显与答案不符
实际上i仅仅在中序序列中有意义,放在先序序列中并没有什么意义
核心代码实现
参考柳婼已知前序(先序)与中序输出后序_柳婼 の blog-CSDN博客
#include <cstdio> using namespace std; int pre[] = {1,2,3,4,5,6,7,8}; int in[] = {4,3,5,2,7,6,8,1}; void post(int root, int start, int end) { //root 先序序列中当前递归层中根节点的下标 //start 中序序列中子树的最左下标(子树开始的下标) //end 中序序列中子树的最右下标(子树结束的下标) if(start > end) return ; /*递归结束的标志,因为子树的元素范围在下标[start,end]之内,当start>end的时候,说明以当前节点为空节点*/ int i = start; //这里的i对于查找根节点root的先序序列完全没有意义,仅代表root在中序序列中的下标位置 while(i < end && in[i] != pre[root]) i++; //寻找root在中序序列中的位置 post(root + 1, start, i - 1); //递归左子树 post(root + 1 + i - start, i + 1, end); //递归右子树 printf("%d ", pre[root]); //输出后序序列 } int main() { post(0, 0, 7); //这里的总长度是pre.size()-1,而不是pre.size() return 0; }
例题
-
java 二叉树(已知先序中序求后序)
2018-03-15 20:37:16package chazao.shu; import chazao.shu.Node; public class BiTree { private Node root; public BiTree(){ root = null;... //后序遍历方法递归实现 public void postOrder(Node localRoot){ ... -
根据先序 中序求后序
2016-05-23 11:24:20使用数组求解已知树的先序和中序求解后序的问题 -
树的遍历:已知先序中序求后序
2010-03-15 14:17:08C++源码,使用VC6.0打开编译后即可运行。 使用递归方法,极其经典,代码简短易懂。 -
18724 二叉树的遍历运算(已知先序中序求后序遍历)
2022-06-14 17:10:08SCAU 18724 二叉树已知先序中序求后序遍历 -
二叉树已知中序后序求先序
2018-06-01 16:40:13C语言,数据结构课程,知道中序和后序遍历,画二叉树和写出前序遍历。 -
数据结构——已知先序中序求后序,已知中序后序求先序
2018-10-20 20:01:00总结下二叉树的已知两种遍历方式求第三种遍历顺序的方法,已知先序和中序遍历或者后序与中序遍历后二叉树是唯一确定的,下面介绍怎么求出第三种遍历顺序。 先序遍历顺序为:根结点——左子结点——右子结点,中序... -
细解 二叉树:已知先序和中序求后序,已知中序和后序求先序
2019-01-10 20:27:18树的三种遍历方式的遍历顺序: 先序遍历:根、左子树、右子树(特点:第一个元素为根) 中序遍历:左子树、根、右子...1、已知先序和中序求后序 先序遍历的第一个字符为根,因此只需在中序遍历中找到它,就可以把根... -
已知先序和中序求后序.pdf
2021-08-10 14:09:40已知先序和中序求后序.pdf -
探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)
2020-09-05 06:48:32本篇文章是对用C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)的方法进行了详细的分析介绍,需要的朋友参考下 -
二叉树:已知先序,中序求后序遍历
2021-06-25 16:48:42} void PostOrderTraverse(BiTree* root)//后序遍历 { if (root != NULL) { PostOrderTraverse(root->Lchild); PostOrderTraverse(root->Rchild); cout << root->data; } } int main(void) { Elem_Type* preorder =... -
二叉树:已知先序和中序求后序,已知中序和后序求先序
2017-04-15 17:14:38树的三种遍历方式的遍历顺序: 先序遍历:根、左子树、右子树(特点:第一个元素为根) 中序遍历:左子树、根、右子树(特点:...1、已知先序和中序求后序 先序遍历的第一个字符为根,因此只需在中序遍历中找到它, -
04已知先序中序或后序还原二叉树(示例代码)
2021-05-23 04:52:14首先,我们看看前序、中序、后序遍历的特性:前序遍历:1.访问根节点2.前序遍历左子树3.前序遍历右子树(个人觉得这个命名略微有误导性,因为前序的“前”容易让人误会成树的最前边(视觉上的左边)。记住前序遍历就是... -
已知先序中序求后序 C实现(分治法)
2017-08-06 16:36:05先 中转后序的 两种实现 对比 -
已知先序和中序求后序
2020-03-22 16:42:44) return root def PostTraversal(self,root): #后序遍历 if root != None: self.PostTraversal(root.left) self.PostTraversal(root.right) print(root.val) pre=[1,2,4,7,3,5,6,8] tin=[4,7,2,1,5,3,8,6] S=... -
二叉树的遍历(前序、中序、后序、已知前中序求后序、已知中后序求前序)
2021-03-08 20:45:17二叉树的遍历(前序、中序、后序、已知前中序求后序、已知中后序求前序) 之前的一篇随笔(二叉树、前序遍历、中序遍历、后序遍历)只对二叉树的遍历进行了笼统的描述,这篇随笔重点对前、中、后序的遍历顺序... -
利用递归方法已知先序,中序求后序
2018-03-27 23:03:35已知某个二叉树的先序和中序、或者中序和后序遍历的次序。可以唯一确定该二叉树。Input两行 第一行:先序遍历的序列 第二行:中序遍历的序列Output输出该二叉树后序遍历的序列。Sample InputABCD BADCSample ... -
二叉树_已知先序中序求后序
2016-05-28 21:09:59二叉树_已知先序中序求后序 #include #include using namespace std ; class Node { public : int data; Node *lchild, *rchild; Node( int _data) { data = _data; lchild = NULL; rchild =... -
已知先序中序求后序算法
2019-10-02 01:41:58// tree.cpp : Defines the entry point for the console application. // #include <stdio.h> #include "string.h" typedef struct node { char data; struct node *lchild,*rchild;...} Bi... -
已知前序中序求后序
2018-07-16 22:20:55题目描述: 输入某二叉树的前序遍历和中序遍历的结果, 请重建出该二叉树。...例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并输出它的后序遍历序列。 思路... -
已知前序中序求后序(python+递归)
2021-03-13 17:40:45传入前序遍历序列和中序遍历序列,后划分为左子树的前序中序遍历序列和右子树前序中序遍历序列,符合递归的思想,而后序遍历的遍历为:左->右->根,所以先递归左子树序列,后递归右子树序列,再输出根节点 ... -
二叉树已知先序和中序求后序方法(结构体构造函数小知识点)
2020-03-12 23:38:39题目描述 二叉树的前序、中序、后序遍历的定义: 前序遍历:对... 给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。 输入描述: 两个字符串,其长度n均小于... -
数据结构习题——由先序和中序建立二叉树/已知先序求后序序列
2020-05-23 23:48:04设一颗二叉树各结点的值互不相同,其先序遍历序列和中序遍历序列分别存在两个一维数组A[1…n]和B[1…n]中,试编写算法建立该二叉树的二叉链表 根据先序序列确定树的根结点 根据根结点在中序序列中划分出二叉树的左... -
先序中序转后序/后序中序转先序
2020-04-19 22:29:50pat里面一个用栈遍历树的题目,本质其实就是已知先序中序转为后序 这俩图相当于分析了,下面直接背吧↓ //一直先序中序转后序 void post(int root,int start,int end) { if(start>end) return ; int i=... -
已知先序中序遍历求后序
2020-10-13 22:53:03#include<bits/stdc++.h>...tree creat1(char a[],char b[],int l1, int h1,int l2,int h2){//l1,h1代表先序第一个和最后一个的下标,l2,h2代表中序的第一个和最后一个的下标 if(l2>h2) return NU -
【数据结构】【二叉树】先序中序后序遍历解题报告
2020-07-18 10:07:59给定一个二叉树,给出二叉树的先序、中序、后序的遍历结构 解题思路: 1.第一个知识点二叉树的先序遍历、中序遍历、后序遍历 先序遍历结构:根 --> 左 -> 右 遍历结果:1->2->3 中序遍历结构:左–>... -
已知先序、中序求后序;已知中序、后序求先序(C++)
2016-07-20 22:11:01先序中序后序的相互求解问题 一、问题描述 我们知道,二叉树有三种深度优先遍历方法:先序中序以及后序,那么,如何已知其中两种遍历序列,求解第三种遍历序列呢。 其实也没大家想得那么美好哈,已知先序、中序...