精华内容
下载资源
问答
  • 只知道中序和后序怎么知道二叉树呢?? 现在我们来了解一下基础的原理: 先知道概念噢!qwq~~~ 前序遍历:先访问当前节点,再访问当前节点的左子树,最后访问当前节点的右子树。对于二叉树,深度遍历与此同。规律:...

    数据结构的题目:

    只知道前序和中序怎么知道二叉树呢??
    只知道中序和后序怎么知道二叉树呢??

    现在我们来了解一下基础的原理:

    先知道概念噢!qwq~~~

    前序遍历:先访问当前节点,再访问当前节点的左子树,最后访问当前节点的右子树。对于二叉树,深度遍历与此同。规律:根在前;子树在根后且左子树比右子树靠前,且第一个就是根节点;

    中序遍历:先访问当前节点的左子树,然后访问当前节点,最后是当前节点的右子树,二叉树,中序遍历会得到数据升序效果。规律:根在中;左子树在跟左边,右子树在根右边,左边部分是根结点的左子树的中序遍历序列,右边部分是根结点的右子树的中序遍历序列 ;

    后序遍历:先访问当前节点的左子树,然后是当前节点的又子树,最后是当前节点。规律:根在后;子树在根前且左子树比右子树靠前,且最后一个节点是根节点。

    一、前序+中序

    1. 根据前序序列的第一个元素建立根结点;
    2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列;
    3. 在前序序列中确定左右子树的前序序列;
    4. 由左子树的前序序列和中序序列建立左子树;
    5. 由右子树的前序序列和中序序列建立右子树。
      如:已知一棵二叉树的先序遍历序列和中序遍历序列分别是abdgcefh、dgbaechf,求二叉树及后序遍历序列。
      先序:abdgcefh—>a bdg cefh

    中序:dgbaechf---->dgb a echf

    得出结论:a是树根,a有左子树和右子树,左子树有bdg结点,右子树有cefh结点。
    先序:bdg—>b dg

    中序:dgb —>dg b

    得出结论:b是左子树的根结点,b无右子树,有左子树。
    先序:dg---->d g

    中序:dg----->dg

    得出结论:d是b左子树的根节点,d无左子树,g是d的右子树

    然后对于a 的右子树类似可以推出

    最后还原:

                                                              a
                                      b                                                 c
    
               d                                                       e                                f
    
                     g                                                                      h
    

    后序遍历:gdbehfca

    二、后序+中序:

    已知一棵二叉树的后序序列和中序序列,构造该二叉树的过程如下:

    1. 根据后序序列的最后一个元素建立根结点;
    2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列;
    3. 在后序序列中确定左右子树的后序序列;
    4. 由左子树的后序序列和中序序列建立左子树;
    5. 由右子树的后序序列和中序序列建立右子树

    如还是上面题目:如:已知一棵二叉树的后序遍历序列和中序遍历序列分别是gdbehfca、dgbaechf,求二叉树

    后序:gdbehfca---->gdb ehfc a

    中序:dgbaechf----->dgb a echf
    得出结论:a是树根,a有左子树和右子树,左子树有bdg结点,右子树有cefh结点。
    后序:gdb---->gd b

    中序:dgb----->dg b

    得出结论:b是a左子树的根节点,无右子树,有左子树dg。

    后序:gd---->g d

    中序:dg----->d g

    得出结论:d是b的左子树根节点,g是d的右子树。

    然后对于a 的右子树类似可以推出。然后还原。
    在这里插入图片描述

    三、前序+后序

    前序和后序在本质上都是将父节点与子结点进行分离,但并没有指明左子树和右子树的能力,因此得到这两个序列只能明确父子关系,而不能确定一个二叉树。 故此法无。不能唯一确定一个二叉树。


    相信到这里大家都理解了叭~
    那我就直接上代码了噢

    import java.util.*;
    
    import tree.BinaryTreeDemo.BinaryTree;
    
     
    /**
     * 根据前序和中序还原二叉树
     *
     */
    
     class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
     
     
     /*
    public class tee2 {
        public static TreeNode1 reConstructBinaryTree(int [] pre,int [] in) {
            //1.由前序遍历确认根节点
            int node=pre[0];
            TreeNode1 tree=new TreeNode1(node);
    
            //2.由中序遍历确认左右子树节点
            ArrayList<Integer> leftTreeForIn=new ArrayList<>();
            ArrayList<Integer> rightTreeForIn=new ArrayList<>();
            int nodePosition=-1;
            for(int i=0;i<in.length;i++){
                if(in[i]==node){
                    nodePosition=i;  //确认根节点在中序遍历中的位置
                }
                //根据根节点将左右子树的节点分别放入两个list中
                if(nodePosition<0){
                    leftTreeForIn.add(in[i]); 
                }else if(nodePosition>=0 && nodePosition<i){
                    rightTreeForIn.add(in[i]);
                }
            }
    
            //3.为树添加左右子树
            if(leftTreeForIn.size()>0){ 
                TreeNode1 left;
                if(leftTreeForIn.size()==1){  //判断左子树是否有叶子节点,左子树只有1个节点则表示无叶子节点
                    left=new TreeNode1(leftTreeForIn.get(0));
                }else{ //有叶子节点则进行递归操作
                    int[] leftTreeForPre=new int[leftTreeForIn.size()];
                    for(int i=0;i<leftTreeForIn.size();i++){
                        leftTreeForPre[i]=pre[i+1];
                    }
                    left=reConstructBinaryTree(leftTreeForPre,Arrays.stream(leftTreeForIn.toArray(new Integer[]{})).mapToInt(Integer::valueOf).toArray());
                }
                tree.left=left;
            }
    
            if(rightTreeForIn.size()>0){
                TreeNode1 right;
                if(rightTreeForIn.size()==1){
                    right=new TreeNode1(rightTreeForIn.get(0));
                }else{
                    int[] rightTreeForPre=new int[rightTreeForIn.size()];
                    for(int i=0;i<rightTreeForIn.size();i++){
                        rightTreeForPre[i]=pre[i+1+leftTreeForIn.size()];
                    }
                    right=reConstructBinaryTree(rightTreeForPre,Arrays.stream(rightTreeForIn.toArray(new Integer[]{})).mapToInt(Integer::valueOf).toArray());
                }
                tree.right=right;
            }
           return tree;
    
        }
    
        public static void main(String[] args){
            int[] pre={1,2,4,7,3,5,6,8};
            int[] in={4,7,2,1,5,3,8,6};
    
            TreeNode1 tree=reConstructBinaryTree(pre,in);
            System.out.println(tree.left.left.right.val);
        }
    }
    */
    
    
    /**
    *根据中序和后序还原二叉树
    *
    *
    *
    *    3
       / \
      9  20
        /  \
       15   7
    
    */
    
    	 
    public class tee2 {
        public static void prevPrintTreeNode(TreeNode root){
        if(root == null){
        return;
    }
    System.out.print(root.val+" ");
    //运用了递归
    prevPrintTreeNode(root.left);
    prevPrintTreeNode(root.right);
    }
    
    public static void inPrintTreeNode(TreeNode root){
    if(root == null){
        return;
    }
    //运用了递归
    inPrintTreeNode(root.left);
    System.out.print(root.val+" ");
    inPrintTreeNode(root.right);
    }
        
    
        public  static TreeNode reConstructBinaryTree(int [] prev,int [] in) {
        //不管什么遍历方式,结果长度肯定是一样的,都是总结点数
            if(prev.length!= in.length || prev.length<1){
                return null;
            }
        //只有一个节点,那就是根节点
            if(prev.length == 1){
                return new TreeNode(prev[0]);
            }
        //在中序遍历结果中找根节点
            int index = -1;
            for(int i=0;i<in.length;i++){
                if(in[i]==prev[0]){
                    index=i;
                    break;
                }
            }
        //没找到,说明数据有问题
            if(index==-1){
                return null;
            }
        //找到根节点了
            TreeNode root = new TreeNode(prev[0]);
        //得到左子树的前序遍历结果
            int[] lChildPrev = new int[index];
            System.arraycopy(prev,1,lChildPrev,0,index);
        //得到左子树的中序遍历结果
            int[] lChildin = new int[index];
            System.arraycopy(in,0,lChildin,0,index);
        //通过递归,得到左子树结构
            root.left=reConstructBinaryTree(lChildPrev,lChildin);
            
        //得到右子树的前序遍历结果
            int[] rChildPrev = new int[in.length-1-index];
            System.arraycopy(prev,index+1,rChildPrev,0,in.length-1-index);
        //得到右子树的中序遍历结果
            int[] rChildin = new int[in.length-1-index];
            System.arraycopy(in,index+1,rChildin,0,in.length-1-index);
        //通过递归,得到右子树结构
            root.right=reConstructBinaryTree(rChildPrev,rChildin);
        //得到完整的二叉树结构
            return root;
        }
    
        public static void main(String[] args){
        int[] prev = {1,2,4,7,3,5,6,8};
        int[] in = {4,7,2,1,5,3,8,6};
        TreeNode root = reConstructBinaryTree(prev,in);
        prevPrintTreeNode(root);
        System.out.println();
        inPrintTreeNode(root);
        }
    }
    

    运行结果:
    1 2 4 7 3 5 6 8
    4 7 2 1 5 3 8 6

    宝宝们喜欢请点个关注噢爱你们~~

    展开全文
  • } //找出根节点在中序遍历中的位置 int treeIndex; for (treeIndex = inStart; treeIndex ; treeIndex ++) { if (inorder[treeIndex] == postorder[postEnd]) { break; } } int leftChildLength = treeIndex - in...
    package treeorder;
    
    public class InfixOrderPostOrderBuildTree {
        public static void main(String[] args) {
            InfixOrderPostOrderBuildTree t = new InfixOrderPostOrderBuildTree();
            int[] inorder = new int[] {2,1};
            int[] postorder = new int[] {1,2};
            TreeNode root = t.buildTree(inorder,postorder);
            System.out.println(root);
        }
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            if (inorder == null || inorder.length == 0 || postorder == null || postorder.length == 0) {
                return null;
            }
    
            TreeNode root = buildTree(inorder,0,inorder.length - 1, postorder, 0,
                    postorder.length - 1);
            return root;
        }
    
        public TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
            TreeNode tree = new TreeNode(postorder[postEnd]);//根节点
            if (inStart == inEnd || postStart == postEnd) {
                return tree;
            }
    
            //找出根节点在中序遍历中的位置
            int treeIndex;
            for (treeIndex = inStart; treeIndex <= inEnd; treeIndex ++) {
                if (inorder[treeIndex] == postorder[postEnd]) {
                    break;
                }
            }
    
            int leftChildLength = treeIndex - inStart;//找出当前树(或者子树)的根节点左孩子的长度
            int rightChildLength = inEnd - treeIndex;//找出当前树(或者子树)右孩子的长度
    
            if (leftChildLength > 0) {//递归构建左子树
                tree.left = buildTree(inorder,inStart,treeIndex - 1, postorder,
                        postEnd - rightChildLength - leftChildLength, postEnd - rightChildLength - 1);
            }
    
            if (rightChildLength > 0) {//递归构建右子树
                tree.right = buildTree(inorder,treeIndex + 1, inEnd, postorder,
                        postEnd - rightChildLength, postEnd - 1);
            }
    
            return tree;
        }
    }
    
    
    展开全文
  • 通过牛客网上的题目来复习一下二叉树的先序、中序和后序遍历,并用Java实现 实现二叉树的先序、中序和后序遍历 题目大意:给定一个二叉树的根结点,分别进行先序、中序和后序遍历,将遍历得到的序列分别放在三个一维...

    通过牛客网上的题目来复习一下二叉树的先序、中序和后序遍历,并用Java实现

    实现二叉树的先序、中序和后序遍历

    题目大意:给定一个二叉树的根结点,分别进行先序、中序和后序遍历,将遍历得到的序列分别放在三个一维数组中,然后返回三个一维数组组成的二维数组(可类比C语言的实现来理解):

    import java.util.*;
    
    /*
    * public class TreeNode {
    *   int val = 0;
    *   TreeNode left = null;
    *   TreeNode right = null;
    * }
    */
    
    public class Solution {
        /**
         *
         * @param root TreeNode类 the root of binary tree
         * @return int整型二维数组
         */
        public int[][] threeOrders (TreeNode root) {
            // write code here
            int[][] result = new int[3][];
            List<Integer> pre = new ArrayList<>();
            List<Integer> in = new ArrayList<>();
            List<Integer> post = new ArrayList<>();
            preOrder(root, pre);
            inOrder(root, in);
            postOrder(root, post);
            result[0] = new int[pre.size()];
            for (int i = 0; i < result[0].length; i++) {
                result[0][i] = pre.get(i);
            }
            result[1] = new int[in.size()];
            for (int i = 0; i < result[1].length; i++) {
                result[1][i] = in.get(i);
            }
            result[2] = new int[post.size()];
            for (int i = 0; i < result[2].length; i++) {
                result[2][i] = post.get(i);
            }
            return result;
        }
        
        public void preOrder(TreeNode root, List<Integer> pre) {
            if (root == null) {
                return ;
            }
            pre.add(root.val);
            preOrder(root.left, pre);
            preOrder(root.right, pre);
        }
        
        public void inOrder(TreeNode root, List<Integer> in) {
            if (root == null) {
                return ;
            }
            inOrder(root.left, in);
            in.add(root.val);
            inOrder(root.right, in);
        }
        
        public void postOrder(TreeNode root, List<Integer> post) {
            if (root == null) {
                return ;
            }
            postOrder(root.left, post);
            postOrder(root.right, post);
            post.add(root.val);
        }
    }
    

    ​对上面的写法的优化(在一个方法中同时实现了前、中、后三种遍历,其中的求结点个数可以记一下):

    import java.util.*;
    
    /*
    * public class TreeNode {
    *   int val = 0;
    *   TreeNode left = null;
    *   TreeNode right = null;
    * }
    */
    
    public class Solution {
        /**
         *
         * @param root TreeNode类 the root of binary tree
         * @return int整型二维数组
         */
        int pre = 0;
        int in = 0;
        int post = 0;
        
        public int[][] threeOrders (TreeNode root) {
            // write code here
            int count = nodeCount(root);
            int[][] result = new int[3][count];
            travel(root, result);
            return result;
        }
        // 求出二叉树中结点的总数
        public int nodeCount(TreeNode root) {
            if (root == null) {
                return 0;
            }
            return nodeCount(root.left) + nodeCount(root.right) + 1;
        }
        // 三种遍历同时实现
        public void travel(TreeNode root, int[][] result) {
            if (root == null) {
                return ;
            }
            result[0][pre++] = root.val;
            travel(root.left, result);
            result[1][in++] = root.val;
            travel(root.right, result);
            result[2][post++] = root.val;
        }
    }
    
    展开全文
  • 简单算法 实现二叉树先序,中序和后序遍历(java) 描述 分别按照二叉树先序,中序和后序打印所有的节点。 想法:无 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null;...

    简单算法 实现二叉树先序,中序和后序遍历(java)
    描述
    分别按照二叉树先序,中序和后序打印所有的节点。
    想法:无

    import java.util.*;
    
    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     * }
     */
    
    public class Solution {
        /**
         * 
         * @param root TreeNode类 the root of binary tree
         * @return int整型二维数组
         */
         public static ArrayList<Integer> pre= new ArrayList<Integer>();
         public static ArrayList<Integer> in= new ArrayList<Integer>();
         public static ArrayList<Integer> bak= new ArrayList<Integer>();
        
         public int[][] threeOrders (TreeNode root) {
            if(root == null) return new int [][]{{}};
             ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
             prel(root);
             inl(root);
             bakl(root);
             list.add(pre);
             list.add(in);
             list.add(bak);
             int[][] result = new int [list.size()][list.get(0).size()];
             for(int i = 0 ; i < list.size(); i ++){
                 for(int j = 0; j < list.get(0).size(); j++){
                     result [i][j] = list.get(i).get(j);
                 }
             }
             return result;
         }
        
        
        public static void prel(TreeNode root) {
            if(root == null) return ;
            pre.add(root.val);
            prel(root.left);
            prel(root.right);
        }
        
        public static void inl(TreeNode root) {
            if(root == null) return ;
            inl(root.left);
            in.add(root.val);
            inl(root.right);
        }
        
        public static void bakl(TreeNode root) {
            if(root == null) return ;
            bakl(root.left);
            bakl(root.right);
            bak.add(root.val);
        }
    }
    
    展开全文
  • 因为先序可以知道这颗树的根,后序也可以知道这颗树的根,那么再去看中序中序的根就找到了,中序根左边的子树是左子树,中序根右边的是右子树,也就是说通过先序先确定根,然后中序找到根与左右子树,然后对左子树...
  • 中序+后序构造二叉树 题目 思路 在拿到题目的时候,我们应该先分析中序和后序遍历的特点,由于中序:左中右,后序:左右中,我们可以知道以下两点 1. 后序的最后一个结点是根节点 2. 中序知道了根节点,那么左右...
  • [问题描述] 建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数。 [基本要求] 要求根据读取的元素建立二叉树,能输出各种遍历。 [实现提示] 可通过输入带空格的前序序列建立二叉链表。
  • //定义一棵二叉树 public class MyTreeNode { public int val; public MyTreeNode left; public MyTreeNode right; public MyTreeNode() {} public MyTreeNode(int val) { this.val = val; } public ...
  • 二叉树的遍历满足递归的思路,无论是先序的根左右,中序的左根右,还是后续的左右跟都是从根结点开始,对每个结点进行先序/中序/后序的遍历,每个结点都是如此,假如是先序根左右的遍历,我们先访问根结点,然后再是...
  • 分别是根据前序、中序和根据中序后序采用的二叉树如下图所示:注意:前序和后序是没有办法还原二叉树根据前序、中序还原二叉树如下图所示:基本思路:根据前序数组,我们能够确定根节点(因为前序数组的根节点一...
  • 输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。LeetCode面试题07 例如,给出: 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,...
  • 这里写目录标题一级目录二级目录三级目录 一级目录 二级目录 三级目录
  • 二叉树的遍历,全部用递归实现,很有规律! 二叉树的遍历,全部用递归实现,很有规律
  • package tree.test;...import java.util.LinkedList; import tree.domian.TreeNode; public class Test {  public static void main(String[] args) {  String hx = "KBFDCAE";  Strin
  • 涉及知识:二叉树的遍历分析:上一篇中介绍了如何通过二叉树的前序和中序遍历构造二叉树。我们知道前序的遍历顺序是:根,左,右;中序的遍历顺序是左,根,右;后序的遍历顺序是左,右,根;如果我们将后序遍历倒...
  • } } }public void theInOrderTraversal_Stack(Node root) { //中序遍历 Stack stack = new Stack(); Node node=root;while (node != null || stack.size() > 0) {if (node != null) { stack.push(node);//直接压栈 ...
  • 思路:中序遍历顺序为左子树-根-右子树, 后序遍历顺序为 左子树-右子树-根,故通过后序遍历可以确定树的根节点,再通过根节点在中序遍历中确定左子树右子树,递归实现以上过程完成树的构造。 图源:...
  • 题目链接:牛客NC45实现二叉树先序,中序和后序遍历 题目描述: 简单板子,直接用递归写方便点 public class Solution { /** * * @param root TreeNode类 the root of binary tree * @return int整型二维数组 ...
  • 二叉树的遍历二叉树的遍历分为前序、中序和后序。可以通过遍历父节点的顺序来区别。前序遍历的顺序是父节点–左子节点–右子节点;中序遍历的顺序是左子节点–父节点–右子节点;后序遍历的顺序是左子节点–右子节点...
  • 中序遍历:左根右 后序遍历:左右根 建树 public class BinaryTree { TreeNode root; public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() { } TreeNode(int val) { this.val = ...
  • 106. 从中序后序遍历序列构造二叉树 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回...
  • 二叉树前序、中序后序遍历(java代码实现)
  • 10.1.4 二叉树遍历的说明 使用前序,中序和后序对下面的二叉树进行遍历。...代码实现(Java实现二叉树的前序、中序和后序的遍历、查找、删除代码在最下方一块展示) 10.1.6 二叉树-查找指定节点 要求 请编写前
  • 后序遍历:先访问左右孩子,后访问父结点 分析 前序遍历(同时也是DFS) 先将根节点进栈,当栈不为空的时候 出栈,记下出栈的结点 当子树不为空,依次进栈右子树左子树 中序遍历 先将根节点进展,当栈不为空的时候...
  • 二叉树建立包括:根节点,左孩子,右孩子,data定义如下:BinTree root;BinTree lChild;BinTree rChild;Object data;List datas;建立二叉树的方法:public void CreateTree(Object[] objs){datas = new ArrayList();...
  • 中序遍历的结果和后序遍历的结果可以确定一颗二叉树 方法 后序序列可以知道根结点子树的子节点;中序序列可以知道根结点(子树的子节点)的左子树有哪些元素,右子树有哪些元素 推演 中序遍历序列和后序...
  • package fenshujs;...import java.util.Scanner; public class bishi { private static class Node { public char s; public Node left = null; public Node right = null; } public static Node Cre
  • 基于对数组链表的存储优缺点分析,这里按照需求引进了一种新的数据结构,树它可以在增删改查上都保持高效率创建如下图所示的二叉树,并分别使用三种顺序遍历: 代码实现:package Tree;public class ...
  • 根据前序和中序中序和后序生成二叉树 给定如下二叉树: 前序遍历结果:1234567 中序遍历结果:3241657 后序遍历结果:3426751 遍历代码实现:思路:将子节点以及其下节点看做一个树,相当于递归获取树的每个节点 ...
  • 已知一颗二叉树中序遍历序列和后序遍历序列,求二叉树的深度。 输入 输入数据有多组,输入T,代表有T组数据。每组数据包含两个长度小于50的字符串。第一个字符串表示二叉树中序遍历,第二个表示二叉树的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,168
精华内容 7,267
关键字:

中序和后序确定二叉树java

java 订阅