精华内容
下载资源
问答
  • 上一篇写到了如何构建一棵树并打印出他的四种遍历,今天按着上一次的代码接着写已知先序遍历和中序遍历求后序遍历。 只要确定了中序遍历,加上另外一种遍历,我们就可以构造出一棵树 //已知前序中序求后序遍历 ...

    上一篇写到了如何构建一棵树并打印出他的四种遍历,今天按着上一次的代码接着写已知先序遍历和中序遍历,求后序遍历。

    只要确定了中序遍历,加上另外一种遍历,我们就可以构造出一棵树

    //已知前序中序求后序遍历
    		//先求出树的原型
    		public Node initTree(int[] preOrder,int pstart,int pend,int[] inOrder,int instart,int inend){
    			if(pstart > pend || instart > inend){
    				return null;
    			}
    			int rootData = preOrder[pstart];
    			Node head = new Node(rootData);
    			//根据中序找到根节点所在位置(左边为左子树,右边为右子树)
    			int rootIndex = findIndexInArray(inOrder,rootData,instart,inend);
    			int offSet = rootIndex-instart-1;
    			//构建左子树
    			Node left = initTree(preOrder,pstart+1,pstart+offSet+1,inOrder,instart,instart+offSet);
    			//构建右子树
    			Node right = initTree(preOrder,pstart+offSet+2,pend,inOrder,rootIndex+1,inend);
    			head.left = left;
    			head.right = right;
    			return head;
    		}
            //中序根节点位置
    		private int findIndexInArray(int[] inOrder, int rootData, int instart, int inend) {
    			for (int i = instart; i <= inend; i++) {
    				if(inOrder[i] == rootData){
    					return i;
    				}
    			}
    			return -1;
    		}

    测试类:

    public static void main(String[] args) {
    		int[] preOrder = {1,2,4,8,9,5,10,3,6,7};
    		int[] inOrder = {8,4,9,2,10,5,1,6,3,7};
    		ConstructTree tree = new ConstructTree();
    		Node root = tree.initTree(preOrder, 0, preOrder.length-1, inOrder, 0,inOrder.length-1);
    		System.out.println("二叉树后序遍历");
    		tree.postOrder(root);
    	}

    输出:

    二叉树后序遍历
    8 9 4 10 5 2 6 7 3 1 

     

    展开全文
  • 1.已知先序遍历中序遍历后序遍历中的任意一种方式,都无法建立起二叉树。 2.已知先序遍历和中序遍历,可以建立二叉树。 3.已知中序遍历和后序遍历,可以建立二叉树。 4.已知先序遍历和后序遍历,无法建立...

    1.已知先序遍历、中序遍历、后序遍历中的任意一种方式,都无法建立起二叉树。

    2.已知先序遍历和中序遍历,可以建立二叉树。

    3.已知中序遍历和后序遍历,可以建立二叉树。

    4.已知先序遍历和后序遍历,无法建立二叉树。

    下面来看洛谷p1030

    https://www.luogu.org/problemnew/show/P1030

    参考题解中的思路:

    首先定义两个字符串inorder,postorder存储中序和后序遍历结果,

    我们从后序遍历最后一个字符找到根结点,在中序遍历中由根结点分为左子树和右子树两个部分,

    根据左右子树结点的个数,在后序遍历中找到相应的左子树和右子树。

    所以我们可以重新得到左右子树的中序遍历和后序遍历,可以用递归解决此问题。

    #include<cstdio>
    #include<iostream>
    #include<string>
    using namespace std;
    void preorder(string inorder,string postorder){
    	if(!inorder.size())return;
    	char root=postorder[postorder.length()-1];
    	cout<<root;
    	int k=inorder.find(root);
    	preorder(inorder.substr(0,k),postorder.substr(0,k));//左子树 
    	preorder(inorder.substr(k+1),postorder.substr(k,postorder.length()-k-1));//右子树 
    	
    }
    int main(){
        string inorder,postorder;
        cin>>inorder>>postorder;
        preorder(inorder,postorder);
        return 0;
    }

    对于已知先序遍历和中序遍历,求后序遍历的问题,思路是一样的。

    下面附上用Python代码

    class Node:
        def __init__(self,data,left=None,right=None):
            self.data=data
            self.left=left
            self.right=right
    def build(preorder,inorder):
        if not inorder:
            return
        root = Node(preorder[0])
        index = inorder.find(preorder[0])
        root.left=build(preorder[1:index+1],inorder[0:index])
        root.right=build(preorder[index+1:],inorder[index+1:])
        return root
    
    def postorder(t):
        if t==None:
            return
        postorder(t.left)
        postorder(t.right)
        print(t.data,end='')
    preorder="ABDHIEJCFGKL"
    inorder="HDIBEJAFCKGL"
    if __name__=='__main__':
        tree=build(preorder,inorder)
        postorder(tree)

     

    展开全文
  • 对于一棵二叉树,已知先序遍历ACDEFHGB,中序遍历DECAHFBG,求后序遍历。 解题思路 首先条件给出了先序遍历和中序遍历,那么我们利用这两种遍历特性得到一下信息: 对于先序遍历,第一个节点是根节点 对于中序...

    已知先序遍历和中序遍历,输出后序遍历

    题目描述

    对于一棵二叉树,已知先序遍历ACDEFHGB,中序遍历DECAHFBG,求后序遍历。

    解题思路

    首先条件给出了先序遍历和中序遍历,那么我们利用这两种遍历特性得到一下信息:

    • 对于先序遍历,第一个节点是根节点
    • 对于中序遍历,根节点的左边是左子树节点,右边是右子树节点

    利用以上信息我们就可以利用递归构建出二叉树,然后通过后序遍历得到结果

    Python代码如下

    class TreeNode:
        def __init__(self,x):
            self.val = x
            self.left =None
            self.right =None
    class Solution:
        #返回构造的TreeNode根节点
        def reConstructBinaryTree(self,pre,tin):
            if len(pre) == 0:
                return None
            root = TreeNode(pre[0])
            TinIndex = tin.index(pre[0])
            root.left = self.reConstructBinaryTree(pre[1:TinIndex+1],tin[0:TinIndex])
            root.right = self.reConstructBinaryTree(pre[TinIndex+1:],tin[TinIndex+1:])
            return root
        def PostTraversal(self,root):
            if root != None:
                self.PostTraversal(root.left)
                self.PostTraversal(root.right)
                print(root.val)
    
    pre = ['A','C','D','E','F','H','G','B']
    tin = ['D','E','C','A','H','F','B','G',]
    S = Solution()
    root = S.reConstructBinaryTree(pre,tin)
    S.PostTraversal(root)
    
    

     

    展开全文
  • 已知前序遍历和中序遍历求后序遍历

    已知前序遍历和中序遍历求后序遍历


    1.知识必备

    ①二叉树的三种遍历
    ②递归的原理

    2.题目描述

    已知二叉树的前序遍历为(  ABCDFE  ),中序遍历(BADFCE ),求该二叉树的后序遍历。

    3.求解思想

    前序,中序遍历顺序图

    在前序遍历中,根节点将中序遍历分为两个部分,左子树和右子树。如果将元素个数进行简化,假设在中序遍历中被根节点分割的左右子树中都只有一个元素,那么可以很容易得到二叉树的形状,也就可以得到后序遍历。说明当这个问题简化成小问题时,可以很容易解决。

    4.算法步骤

    ①在前序遍历中取第一个点,即为根节点。
    ②在中序遍历中找到这个点所在的位置。下标从 0 开始,假设找到根节点在下标为 index 的位置 
    ③根节点将字符串分为左右两个子串(看上图的中序遍历),左子树 为  父串 的(0,index-1),右子树为父串的
    ( index+1 ,父串的结尾)。注:括号内容的含义,(起点下标,终点下标)   ;  知道了左右子树的起始位置和终止位置,那么左右子树的长度可以很容易得到(终点下标 - 起点下标 + 1),那么左子树在前序遍历中的位置也可以很容易得到 (1,index),右子树同理。
    ④将左右子树对应的前序遍历,中序遍历,在进行步骤①-③的操作,直到左右子树的长度为 0

    5.源代码

    下载地址:
    http://download.csdn.net/detail/qq_28648083/9801315



    展开全文
  • 已知后序遍历和中序遍历求二叉树

    千次阅读 2018-09-17 19:00:56
    输入某二叉树的后序遍历和中序遍历的结果,请输出前序遍历序列。假设输入的后序遍历和中序遍历的结果中都不含重复的数字。例如输入后序遍历序列{7,1,4,2,5,8,6,3,1}和中序遍历序列{4,7,2,1,5,3,8,6},重建二叉树并...
  • 题目:已知二叉树先序遍历+中序遍历 求后序遍历 对于一棵二叉树,给定其先序遍历的结果序列和中序遍历的结果序列,请写出其后序遍历的结果序列。 输入样例: GDAFEMHZ(先序遍历的结果序列) ADEFGHMZ(中序...
  •  输入一棵二叉树的先序遍历和中序遍历,输出它的后序遍历。 输入输入有多组数据(少于100组),以文件结尾结束。 每组数据仅一行,包括两个字符串,中间用空格隔开,分别表示二叉树的先序序列和中序序列(字符串...
  • 假设是1000个结点以内, 输入前序 4 1 3 2 6 5 7  中序 1 2 3 4 5 6 7  得到后续 2 3 1 5 7 6 4 ...已知前序遍历中序遍历求后序遍历: import java.io.BufferedInputStream; import java.uti...
  • 1.已知先序遍历中序遍历序列,能够创建出一棵唯一的二叉树,可以得出二叉树的后序遍历; 2.已知后序遍历中序遍历序列,能够创建出一棵唯一的二叉树,进而可以得出二叉树的先序序列; 3.综上,必须含有中序遍历...
  • 已经一个二叉树先序遍历ACDEFHGB,中序遍历DECAHFBG,求后序遍历? 解题参考资料: 先序遍历 (1)访问根节点(2)先序遍历左子树(3)先序遍历右子树 中序遍历 (1)中序遍历左子树(2)访问根节点(3)中序遍历右子树 后序遍历...
  • 二叉树的先序遍历中序遍历后序遍历 #include<stdio.h> #include<stdlib.h> typedef struct Node { char data; struct Node* lchild; struct Node* rchild; }BNode, *BiTree; void create_...
  • 2021/3/6 算法训练 绘制地图(已知数组先序和中序求后序序列) 在这里我们只需要改变cur_pos的初始值每次运行的操作即可 我们知道后序遍历序列是左子树->右子树->根;所以我们需要先建立右子树而后建立左...
  • 算法思想:已知先序遍历和中序遍历,如何求后序遍历?(1)确定树的根结点。树根是当前树中所有元素在先序遍历中最先出现的元素,即先序遍历的第一个结点就是二叉树的根。(2)解树的子树。找到根在中序遍历的位置,...
  • 已知后序遍历和中序遍历重建二叉树和已知前序遍历和中序遍历求后序遍历的时候已经说明思路,这里直接贴代码 # -*- coding:utf-8 -*- class Solution(object): def reConstructBinaryTree(self, post, mid): if ...
  • 程序1(通过根节点的位置判断树的左右子树是否为空)://已知二叉树的中序和先序遍历二叉树的后续遍历 #include #include #include typedef struct BiTree { char data; struct BiTree *left,*right; }...
  • //由先序遍历和中序遍历得到后序遍历 //算法思想 //首先由先序遍历的到根节点 //然后分成左子树右子树 //把先序遍历的第一个给后序遍历的最后一个 #include #include using namespace std; void ...
  • 已知二叉树先序遍历中序遍历后序遍历 (注:已知中序遍历序列剩下两种遍历序列中的一种都可以确定二叉树,即可得到另一种遍历序列, 但是已知前序遍历和后序遍历序列并不能唯一确定二叉树,例如:preorder:...
  • 已知后序遍历和中序遍历求前序遍历的过程差不多,但由于后序遍历是最后才访问根节点的  所以要从后开始搜索,例如上面的例子,后序遍历为 gbdehfca,中序遍历为 dgbaechf  后序遍历中的最后一个元素是根节点,...
  • 例如已知序列 中序遍历为:1234567 后序遍历为:2315764 由基本思想,先找到总树的根节点就为后序遍历的最后一个点。即4为Root 然后由找到的根节点 在中序遍历中找到左子树的中序遍历结果为123。 在后序遍历中找到左...
  • 题目描述: 二叉树的前序、中序后序遍历的定义: 前序遍历:对任一子树,先访问跟,然后遍历其左子树,最后... 给定一棵二叉树的前序遍历和中序遍历后序遍历(提示:给定前序遍历中序遍历能够唯一确定后...
  • 给出先序遍历和中序遍历后续遍历,要求: 函数头如下: bool getPostOrder(const char* perOrder, const char* inOrder, char* postOrder); 返回值是一个布尔 代表是否有这样的二叉树 用法: char* perorder ...
  • 题目:输入二叉树的前序和中序遍历结果,输出二叉树后序遍历结果。 输入格式: 第一行为二叉树的前序遍历结果 第二行为二叉树的中序遍历结果 输出格式: 二叉树后序遍历结果 Example: Inputs: 426315 623415 Outputs...
  • 菜鸡学习记录,贴代码: #include #include ...* 已知前序遍历和中序遍历的结果求后序遍历 * */ void changeOrderToLRD(char *pre,char *mid,int length) { if(0 == length) return; char
  • 由于先序遍历树的规则为:根左右,因此可以得到...由先序遍历和中序遍历求解二叉树的过程,步骤如下:①确定树的根节点。树根是当前树中所有元素在先序遍历中最先出现的元素,即先序遍历的第一个结点就是二叉树的根...
  • 给定这棵二叉树的前序遍历和中序遍历后序遍历。 下图是依据下文算法代码绘制的示意图。【输入格式】 输入包含多组测试数据。 每组数据占两行,每行包含一个大写字母构成的字符串,第一行表示二叉树的前序遍历...
  • 题目描述 二叉树的前序、中序后序遍历的定义: ...给定一棵二叉树的后序遍历和中序遍历其前序遍历(提示:给定后序遍历中序遍历能够唯一确定前序遍历)。 输入 两个字符串,其长度n均小于...
  • 先序遍历中第一个字母即为根节点,在中序遍历中找到根节点的位置 ②把中序遍历的字符串序列从根节点分成两部分,左侧一部分构建左子树,右侧一部分构建右子树 ③在②的基础上在先序遍历中也找到构建左右子树的...
  • 最近在刷北理复试机试题,遇到个经典问题:已知后序遍历和中序遍历前序遍历。 参考别人博客写的代码。 原文链接:https://blog.csdn.net/u014552756/article/details/55510814 算法思想: 后序遍历的最后...
  • package algorithm01; import java.util.Scanner;... * 给出先序遍历和中序遍历序列出二叉树的后续遍历序列 * @author wxisme * */ public class ToReverse { public static void main(String[] a...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 86,406
精华内容 34,562
关键字:

已知后序遍历和中序遍历求先序遍历