精华内容
下载资源
问答
  • @[TOC]树的遍历 前文 本人是通过leedcode学习数据结构的,边学边练,因此大部分题目也都来源于leedcode 今天贴上的是最简单的树遍历的java代码,其实代码部分都是相似的,先创建一个result(list)来存放结果,通过...

    前文

    本人是通过leedcode学习数据结构的,边学边练,因此大部分题目也都来源于leedcode

    今天贴上的是最简单的树遍历的java代码,其实代码部分都是相似的,先创建一个result(list)来存放结果,通过不同遍历方式去安排结点的遍历与数据存放的顺序.

    1. 前序遍历 :中——左——右
    /**
     2. Definition for a binary tree node.
     3. public class TreeNode {
     4.     int val;
     5.     TreeNode left;
     6.     TreeNode right;
     7.     TreeNode() {}
     8.     TreeNode(int val) { this.val = val; }
     9.     TreeNode(int val, TreeNode left, TreeNode right) {
     10.         this.val = val;
     11.         this.left = left;
     12.         this.right = right;
     13.     }
     14. }
     */
    class Solution {
        public List<Integer> result=new ArrayList<Integer>();
    
        public void preorder(TreeNode head){
            if(head==null) return;
            result.add(head.val);
            preorder(head.left);
            preorder(head.right);
        }
    
        public List<Integer> preorderTraversal(TreeNode root) {
           preorder(root);
           return result; 
           //所有执行结束后,回到根节点才会返回,因此需要preorderTraversal和preorder两个方法
        }
    }
    
    1. 中序遍历:左——中——右
      开头部分的代码与前序相同,后面就不再写上去了,贴主要的代码部分
    class Solution {
        public List<Integer> result=new ArrayList<>();
        public List<Integer> inorderTraversal(TreeNode root) {
            inorder(root);
            return result;
        }
        public void inorder(TreeNode head){
            if(head==null) return;       
            inorder(head.left);        
            result.add(head.val);       
            inorder(head.right);
            
        }
    }
    
    1. 后序遍历:左——右——中
    class Solution {
        public List<Integer> result=new ArrayList<>();
        public List<Integer> postorderTraversal(TreeNode root) {
            postorder(root);
            return result;
        }
        public void postorder(TreeNode head){
            if(head==null)return;
            postorder(head.left);
            postorder(head.right);
            result.add(head.val);
        }
    }
    

    总结

    不论是前序中序还是后序,思路都是一样的,都是
    1.创建一个result列表来保存数据
    2.构造返回根节点的方法
    3.构造前序/中序/后序搜索的方法,在该方法中先判断该结点是否存在,之后注意result.add的位置就可以了

    展开全文
  • 已知一个二叉树前序、中序遍历字符串求其后续遍历 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;//中序遍历字符串
    }
    
    

    运行结果

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

    展开全文
  • 如题,好像大学课后作业。写一个练练手。网上不少,大多都是C或C++。   一个二叉树前序遍历:GDAFEMHZ  中序遍历:ADEFGHMZ ...求其后续遍历。...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());
    			}
    
    		}
    	}
    
    }

     

     

    展开全文
  • 树的层次遍历Java代码实现)

    千次阅读 2017-11-13 14:43:29
    树的前中后序遍历的DFS思想不同,层次遍历用到的是BFS思想。一般DFS用递归去实现(也可以用栈实现),BFS需要用队列去实现。 层次遍历的步骤是: 1.对于不为空的结点,先把该结点加入到队列中 2.从队中拿出结点,...
     
    

    与树的前中后序遍历的DFS思想不同,层次遍历用到的是BFS思想。一般DFS用递归去实现(也可以用栈实现),BFS需要用队列去实现。

    层次遍历的步骤是:

    1.对于不为空的结点,先把该结点加入到队列中

    2.从队中拿出结点,如果该结点的左右结点不为空,就分别把左右结点加入到队列中

    3.重复以上操作直到队列为空

     

     1 public class Solution{
     2 class TreeNode {
     3     int val;
     4     TreeNode left;
     5     TreeNode right;
     6     TreeNode(int x) { val = x; }
     7 }
     8 public static void LaywerTraversal(TreeNode root){
     9         if(root==null) return;
    10         LinkedList<TreeNode> list = new LinkedList<TreeNode>();  
    11         list.add(root);
    12         TreeNode currentNode;
    13         while(!list.isEmpty()){
    14             currentNode=list.poll();
    15             System.out.println(currentNode.val);
    16             if(currentNode.left!=null){
    17                 list.add(currentNode.left);
    18             }
    19             if(currentNode.right!=null){
    20                 list.add(currentNode.right);
    21             }
    22         }
    23     }
    24 }

     

    展开全文
  • PTA【树的遍历Java

    2021-01-18 19:58:21
    在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。 输入样例: 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 输出样例: 4 1 6 3 5 7 2 代码实现: import java.io.*; impor
  • 树的层次遍历Java实现

    2020-02-04 19:43:36
    思想本身并不复杂,每一次打印一个节点时候,如果该节点有子节点,则把该节点子节点放到一个队列尾部。...代码如下: import java.util.ArrayList; /** public class TreeNode { int val = 0; ...
  • N叉树的层序遍历做题博客链接题目链接描述示例初始代码模板代码 做题博客链接 https://blog.csdn.net/qq_43349112/article/details/108542248 题目链接 ...描述 给定一个 N 叉树,返回其节点值的层序遍历。...
  • if (node == null) //很重要,必须加上 当遇到叶子节点用来停止向下遍历 return; System.out.print(node.getValue()+" "); preTraversal(node.getLeft()); preTraversal(node.getRight()); } 中序: pub...
  • ...import java.lang.reflect.Array; public class SortIt { /** * 交换 * @param array * @param i * @param j */ public void swapInt(int[] array, int i ,int j) { int temp
  • Java实现树的遍历

    2017-01-05 21:15:14
    树的遍历总结 整理了最近遇到的关于二叉树的遍历问题,记录如下: 递归: 递归方法比较简单,所以不再赘述。代码如下: 前序: public class Solution {  /**  * @param root: The root of binary tree.  ...
  • 题目:输入一个整数数组,判断该数组是不是某个二叉搜索树的后序遍历序列。假设数组的任意两个数字都不相同。 解题思路:这里是二叉搜索树,其左子树应该都小于根节点,右子树则都大于根节点。在后续遍历序列中,...
  • 二叉树的遍历JAVA实现

    2020-04-03 14:49:10
    二叉树的遍历JAVA实现 参考资料 二叉树的遍历有前序、中序、后序和层序,其主要区别是: 前序(根节点=>左子树=>右子) 中序(左子树=>根节点=>右子) 后序(左子树=>右子=>根节点) 这通过...
  • 主要介绍了Java中二叉树建立和各种遍历实例代码,涉及节点定义,后序遍历,层序遍历,深度优先和广度优先等相关内容,具有一定借鉴价值,需要朋友可以参考下
  • 首先遍历根结点,所以可以采用树的先序遍历遍历完一条路径后将其叶子节点删除重新回到其根结点中 代码: import java.util.ArrayList; /** public class TreeNode { int val = 0; TreeNode left = null; ...
  • java多叉树的遍历

    千次阅读 2019-01-23 08:54:26
    用过了二叉树后,正好业务上有一个需求,就是需要求出从根节点到每个叶子节点的路径集合,由于不是二叉树,而是如同一种多叉树的结构,下面来看具体代码, 1、节点对象,包含3个属性,当前节点Id,持有的父节点Id,...
  • 树算法系列 一 树的遍历与LeetCode相关树遍历算法

    多人点赞 热门讨论 2020-02-25 16:58:46
    注:以下所有代码皆使用Java进行编写 树的各种遍历: 首先我们需要了解一下数的各种遍历:分为先序,中序,后序,层序; 讲解:对于树的操作而言,由于在很多的情况下都是会回退到对上一级的访问,...
  • 二叉树的遍历java代码实现)

    千次阅读 2018-08-18 10:20:36
    二叉树的遍历分为以下三种: 先序遍历:遍历顺序规则为【根左右】 中序遍历:遍历顺序规则为【左根右】 后序遍历:遍历顺序规则为【左右根】 什么是【根左右】?就是先遍历根,再遍历左孩子,最后遍历右孩子 ...
  • 二叉树遍历——Java代码实现二叉树二叉树的遍历代码实现首先创建一个结点其次是进行遍历操作的BinaryTree类递归实现二叉树遍历方法详述(以中序遍历为例)主函数输出结果 二叉树 二叉树是树的一种,每个结点最多可...
  • 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 解题思路 (左神牛逼) 如果一个数组是二叉搜索树后序遍历的结果 那么这个...
  • Java递归算法实现目录树的遍历

    千次阅读 2017-01-03 16:17:42
    具体请看代码实现,挺简单的。... * 递归算法实现目录树的遍历 */ public class Recursion { public static void main(String[] args) { Recursion r = new Recursion(); String root = "E:
  • 树的层次遍历 (Java)

    千次阅读 2019-03-15 18:52:34
    一、问题 1 2 3 4 5 6 7 输出该层次遍历的结果 1 2 3 4 5 6 7 二、代码 Java @Data public class Node { private Int...
  • java多叉层次遍历

    千次阅读 2018-05-28 23:13:55
    java多叉树的层次遍历,我的树好像不太一样,看代码吧。代码中的LLQueue 就是一个单链表实现的队列。 思路与二叉树的层次遍历一样。遍历一层的时候,把下层的节点放到队列中。就是操作有点不同。 /** * 功能 : ...
  • 树的遍历算法(递归,迭代)(C++,java) 最近刷力扣,记录一下树的各种遍历算法,分别用C++和java实现,基于递归和迭代。 基于递归的二叉树遍历 所有树的遍历用递归来解决思路都是是十分清晰的,前序中序后序差距...
  • Node类:树的节点类 public class Node { private int no; private Node left; private Node right; public Node() { } public Node(int no) { this.no = no; } public int getNo() { return no;
  • 广度优先搜索是一种广泛运用在或图这类数据结构中,遍历或搜索算法。 该算法从一个根节点开始,首先访问节点本身。 然后遍历相邻节点,其次遍历二级邻节点、三级邻节点。 当我们在中进行广度优先搜索...
  • 3.递归遍历右子树,把右子树的遍历结果加入到List中。 4.返回 代码 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) ...
  • 层序遍历Java实现

    千次阅读 2019-10-05 10:28:11
    层序遍历Java实现 层序遍历是树的一种遍历方法 遍历过程 从根节点A开始,逐层从左到右遍历节点 遍历结果为A,B,C,D,E,F,G 代码实现 二叉树类创建 一个二叉树的节点,应具有节点值、左子树根节点引用和右子树根...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,478
精华内容 591
热门标签
关键字:

树的遍历java代码

java 订阅