精华内容
下载资源
问答
  • 已知一个二叉树的前序、中序遍历字符串求其后续遍历 Java代码实现 笔试遇到的问题,当时没写出来,上网找了一下思路,有一篇思路不错,结合自己的一些理解写个博客记录一下。 思路 一个二叉树 前序遍历:GDAFEMHZ ...

    笔试遇到的问题,当时没写出来,上网找了一下思路,有一篇思路不错,结合自己的一些理解写个博客记录一下。

    思路

    一个二叉树
    前序遍历:GDAFEMHZ
    中序遍历:ADEFGHMZ
    求其后序遍历。

    求解过程:
    1.通过前序遍历我们可知此树根节点为G(即前序遍历第一个字符)

    2.观测中序遍历可知此树左子树所有节点为:ADEF右子树所有节点为:HMZ(以根节点划分)

    3.得到左子树的前序遍历(DAFE)中序遍历(ADEF)顺序未变。

    4.得到右字数的前序遍历(MHZ)中序遍历(HMZ) 顺序未变。

    5.递归此过程,展开所有子树。

    实现代码

    public class Main {
    	public static String post = "";//用于记录后序遍历
    	public static void main(String[] args){
    		String pre = "GDAFEMHZ";
    		String in = "ADEFGHMZ";
    		
    		//创建树的根节点
    		Tree t = new Tree();
    		t.root = pre.substring(0, 1);//前序遍历的第一个字符
    		t.pre = pre;//该树的前序遍历
    		t.in = in;//该树的中序遍历
    		
    		build(t);//开始递归展开节点,获取它的孩子
    		
    		System.out.println(post);//输出后序遍历
    	}
    	/**
    	 * 采取后序遍历递归展开所有节点
    	 * @param tree
    	 */
    	public static void build(Tree tree){
    		open(tree);//将节点展开
    		if(tree.left != null){
    			build(tree.left);
    		}
    		if(tree.right != null){
    			build(tree.right);
    		}
    		//左右遍历完后到根节点
    		post = post + tree.root;
    	}
    	/**
    	 * 将节点展开
    	 * @param tree
    	 */
    	public static void open(Tree tree){
    		//该节点有孩子
    		if(tree.pre.length()>1){//前序长度大于一表示该节点后面还有节点
    			String s1 = tree.pre;
    			String s2 = tree.in;
    			String [] node = s2.split(tree.root);//中序遍历以根节点为分割符分割
    			if(node.length>=2){
    				//该节点有两个孩子
    				//创建新的子树赋值给左子树
    				tree.left = new Tree();
    				//新左子树的前序遍历
    				tree.left.pre = s1.substring(1, node[0].length()+1);
    				//新左子树的中序遍历
    				tree.left.in = node[0];
    				//分割完后的子树又相当于一颗新的树,其根节点为新的前序遍历的第一个字符
    				tree.left.root = tree.left.pre.substring(0, 1);
    				
    				//新的右子树思想和上面差不多
    				tree.right = new Tree();
    				tree.right.pre = s1.substring(node[0].length()+1, s1.length());
    				tree.right.in = node[1];
    				tree.right.root = tree.right.pre.substring(0, 1);
    			}else{
    				//该节点只有一个孩子
    				//当该节点只有一个孩子时,无论左孩子还是右孩子,后序遍历没有影响
    				tree.left = new Tree();
    				tree.left.pre = s1.substring(1, node[0].length()+1);
    				tree.left.in = node[0];
    				tree.left.root = tree.left.pre.substring(0, 1);
    			}
    		}//其他情况没有孩子,则该节点左右子树都是null
    	}
    }
    class Tree {
    	 String root;	  //根节点
    	 Tree left;       //左子树
    	 Tree right;      //右子树
    	 
    	 String pre;//前序遍历字符串
    	 String in;//中序遍历字符串
    }
    
    

    运行结果

    在这里插入图片描述
    不足之处多多包涵

    展开全文
  • 编程题找出二叉树中序遍历的下一个结点Java实现题目描述问题分析代码及讲解总结 题目描述 给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含...

    编程题找出二叉树中序遍历的下一个结点Java实现

    题目描述

    给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

    问题分析

    二叉树的结构如下所示,题目中的描述next意思是指向当前节点的父节点。我们要知道中序遍历的含义,先按中序遍历左子树,再输出当前结点,然后再中序遍历右子树。

    public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;
    
        TreeLinkNode(int val) {
            this.val = val;
        }
    }
    

    代码及讲解

    按照中序遍历的特点,如果当前结点没有右子树,且它是它父结点的左子结点(例如D),则当前结点的下一个遍历的结点就是它的父结点(B),如果它是它父结点的右子结点(G,I)则它应该向上寻找到一个结点是该结点父结点的左子结点(G对应null,I对应A),则下一个遍历的就是该结点的父节点。
    如果当前结点有右子树(如E,B),则按照中序遍历的规则,应该对当前节点的右子结点进行中序遍历,则下一个遍历的点为当前节点右子树中最下面的左子节点(H)。
    我这么说肯定看的很茫然,找了个图当例子讲一下。
    下图的中序遍历顺序为{D,B,H,E,I,A,F,C,G}。配合上面的讲述应该比较清楚了吧。
    在这里插入图片描述

    public class Solution {
        public TreeLinkNode GetNext(TreeLinkNode pNode)
        {
            if(pNode==null){
                return pNode;
            }
            if(pNode.right!=null){
                pNode=pNode.right;
                while(pNode.left!=null){
                    pNode=pNode.left;
                }
                return pNode;
            }
            while(pNode.next!=null){
                if(pNode.next.left==pNode)return pNode.next;
                if(pNode.next.right==pNode) pNode=pNode.next;
            }
            return null;
        }
    }
    

    总结

    我觉得本题要注意对问题的分析,我开始写是从是否是叶子结点来判断的,最后写的一塌糊涂,把自己也绕了进去,后来看了一些讨论和题解才解出来。其实二叉树中序遍历找下一个结点并不难,注意找到问题的切入点才是关键,老板们加油,我有个朋友说过种一棵树最好的时间是十年前然后就是。

    展开全文
  • 给定一个二叉树,返回它的中序遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2] 法一 递归法 理解: List.addAll() 成功 显示详情 执行用时 :2 ms, 在Binary Tree Inorder Traversal的Java...

    给定一个二叉树,返回它的中序 遍历。

    示例:

    输入: [1,null,2,3]
       1
        \
         2
        /
       3
    
    输出: [1,3,2]

    法一 递归法

    理解:   List.addAll()

    成功

    显示详情

    执行用时 : 2 ms, 在Binary Tree Inorder Traversal的Java提交中击败了49.67% 的用户

    内存消耗 : 34.2 MB, 在Binary Tree Inorder Traversal的Java提交中击败了59.14% 的用户

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<Integer>();
            if(root == null)
                return res;
            res.addAll(inorderTraversal(root.left) );
            res.add(root.val);
            res.addAll(inorderTraversal(root.right) );
            return res;
        }
    }

    法二,非递归,利用栈结构

    (当-while, 若-if )

    当前节点从根节点开始。

    当前节点不为空或栈不空

        当当前节点不为空时,当前节点入栈,判断其是否有左节点。若有当前节点置为左节点,继续当前这一步;若无,则进行下一步。

        若栈不为空,出栈,并将当前元素置为该出栈元素的右节点。

     

    成功

    显示详情

    执行用时 : 2 ms, 在Binary Tree Inorder Traversal的Java提交中击败了49.67% 的用户

    内存消耗 : 34 MB, 在Binary Tree Inorder Traversal的Java提交中击败了71.52% 的用户

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            //List<Integer> res = new ArrayList<Integer>();
            List<Integer> res = new ArrayList<>();
            if(root == null)
                return res;
            //Stack<TreeNode> tmp = new Stack<TreeNode>();
            Stack<TreeNode> tmp = new Stack<>();
            TreeNode cur = root;
            while(cur!=null || !tmp.empty() ){
                while(cur != null){
                    tmp.push(cur);
                    cur = cur.left;
                }
                if(!tmp.empty() ){
                    cur = tmp.pop();
                    res.add(cur.val);
                    cur = cur.right;
                }
            }
            return res;
        }
    }

     

    展开全文
  • //还有一种是需要自己去输入字符串的 public static void main(String[] args) { Scanner input=new Scanner(System.in); while(input.hasNext()){ String str=input.nextLine(); Node root=buildTree(str); ...
  • 如题,好像大学的课后作业。写一个练练手。网上不少,大多都是C或C++的。   一个二叉树前序遍历:GDAFEMHZ  中序遍历:ADEFGHMZ ...1.通过前序遍历我们可知...2.观测中序遍历可知此树左子树所有节点为:ADEF 右子...

    如题,好像大学的课后作业。写一个练练手。网上不少,大多都是C或C++的。

     

    一个二叉树前序遍历:GDAFEMHZ

                      中序遍历:ADEFGHMZ

    求其后续遍历。

     

    求解过程

    0.这三种遍历不知道是什么意思的请自行搜索。

    1.通过前序遍历我们可知此树根节点为G(即前序遍历第一个字符)

    2.观测中序遍历可知此树左子树所有节点为:ADEF  右子树所有节点为:HMZ(以根节点划分)

    3.得到左子树的前序遍历(DAFE)中序遍历(ADEF) 顺序未变。

    4.得到右字数的前序遍历(MHZ)中序遍历(HMZ) 顺序未变。

    5.递归此过程,展开所有子树。

     

    代码如下:

        定义二叉树的类

    public class Tree {
    	
    	 String root = "";//根节点
    	 Tree left;       //左子树
    	 Tree right;      //右子树
    	 
    	 String pre = "";//前序遍历字符串
    	 String in = "";//中序遍历字符串
    	 String back = "";//后序遍历字符串
    	
    	Tree(String s){
    		this.root = s;
    	}
    	
    	Tree(){}
    	
    }

     

        实现代码:

       

    public class testTree {
    	
    	
    	public static String post = "";
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		String pre = "GDAFEMHZ";
    		String in = "ADEFGHMZ";
    		Tree t = new Tree();
    		t.root = in;
    		t.pre = pre;
    		
    		build(t);
    		System.out.println(post);
    		
    		
    	}
    	
    	
    	/**
    	 * 采取后序遍历递归展开所有节点
    	 * @param tree
    	 */
    	public static void build(Tree tree){
    		
    
    		if(tree == null){
    			return;
    		}
    		open(tree);
    		if(tree.left != null){
    			open(tree.left);
    			build(tree.left);
    		}
    		if(tree.right != null){
    			open(tree.right);
    			build(tree.right);
    		}
    		post = post + tree.root;
    	}
    	
    	
    	/**
    	 * 将节点不是单字符的节点展开
    	 * @param tree
    	 */
    	
    	public static void open(Tree tree){
    		if(tree.root.length()>1){
    			String s2 = tree.root;
    			String s1 = tree.pre;
    			 
    			tree.root =s1.substring(0, 1);
    			String [] node = s2.split(tree.root);
    			if(node.length>=2){
    				tree.left = new Tree(node[0]);
    				tree.left.pre = s1.substring(1, node[0].length()+1);
    				tree.right = new Tree(node[1]);
    				tree.right.pre = s1.substring(s1.length()-node[1].length(), s1.length());
    			}
    
    		}
    	}
    
    }

     

     

    展开全文
  • package leetCoder; import java.util.ArrayList; import java.util.List; ... * @description : 二叉树的中序遍历 * @create : 2020/06/24 08:24 */ class TreeNode { int val; TreeNode lef
  • 对于二叉树的先序遍历和中序遍历,由于在先序遍历中第一个访问的总是根节点,因此可以根据先序遍历中的第一个元素,将中序遍历看成是**“左子树中序遍历+根节点+右子树中序遍历”**,根据左右子树中序遍历的节点个数...
  • 编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串:ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对...
  • 编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对...
  • /** * 假定二叉树节点的结构如下: * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x;... //本方法就是中序遍历方案,左根右。作者YYM ...
  • 每个节点都有一个小写字母,中序遍历,得到一个字符串,求所有能得到的字符串的字典序最小串。因为这棵树不一定是二叉树,所以中序遍历时,先中序遍历以节点序号最小的节点为根的子树,然后再遍历根节点,最后根据...
  • 根据给定的二叉树结构描述字符串,输出该二叉树按照中序遍历结果字符串中序遍历顺序为:左子树,根结点,右子树。 输入描述 由大小写字母、左右大括号、逗号组成的字符串: 1、字母代表一个节点值,左右括号内包含该...
  • 题目描述:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建...
  • 这题关键点在于理解二叉树的非递归遍历,能够看得出入栈顺序就是二叉树的先序遍历序列,出栈顺序就是二叉树的中序遍历序列。理解了这点这道题就转换成已知先序遍历+中序遍历,打印二叉树的后序遍历的问题了。 有两...
  • 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回...
  • 94. 二叉树的中序遍历

    千次阅读 2020-02-13 23:13:08
    94. 二叉树的中序遍历 题解: 1. 递归中序遍历 第一种解决方法是使用递归。这是经典的方法,直截了当。我们可以定义一个辅助函数来实现递归。 2. 迭代中序遍历 考查到当前节点时,并不直接输出该节点。 而是当考查...
  • 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树...
  • 中序遍历和后序遍历 输出先序遍历 public static void main(String[] args) { Scanner input=new Scanner(System.in); String mid=input.nextLine(); String next=input.nextLine(); System.out.p...
  • 两个字符串,分别表示二叉树的前序遍历和中序遍历结果,用空格分隔。保证数据合法 输出描述: 对应输出后序遍历序列 示例1 输入 ABDEC DBEAC 输出 DEBCA思路:先根据先序、中序序列建立二叉树...
  • 先序遍历的字符串的首字符肯定是树的根节点,而中序遍历字符串的左右子树肯定被根分割开。 # include <cstdio> using namespace std; /**************************/ struct Node{ char v; Node * left; ...
  • 两个字符串,其长度n均小于等于26。 第一行为前序遍历,第二行为中序遍历。 二叉树中的结点名称以大写字母表示:A,B,C…最多26个结点。 输出 输入样例可能有多组,对于每组测试样例, 输出一行,...
  • 题目描述 ...建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。 输入描述: 输入包括1行字符串,长度不超过100。 输出描述: 可能有多组测试数据,对于每组数据, 输出将输入字符串建立...
  • 编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再...
  • 文章目录一、题目描述1.1 题目1.2 ...二叉树的中序遍历 给定一个二叉树,返回它的中序 遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2] 进阶: 递归算法很简单,你可以通过迭代算法完成吗?...
  • 最近在学习数据结构这本书,遇到这个题目,就开始学习,网上看了很多代码都是用C写的,本人是搞java,于是...中序遍历:DBEAFC 输出结果:DEBFCA   附上源码如下:   /*  * author by xzb  * 2013.8.19  */ packag
  • * 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树: 3 / \ 9 20 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,914
精华内容 2,765
关键字:

中序遍历java输入字符串

java 订阅