精华内容
下载资源
问答
  • 后序遍历非递归 Java

    2020-04-04 16:05:13
    思路:借助先序遍历交换子树。...观察发现:交换左右子树的二叉树先序遍历=二叉树逆后序遍历=后序遍历反着来 因此,我们的目标是,想办法吧二叉树变成交换左右子树的二叉树,然后push进一个stack里,最后只要pop出...

    思路:借助先序遍历交换子树。

    创建二叉树

    原二叉树
    交换左右子树的二叉树

     

     得出:

    先序遍历: 1,2,4,5,3,6

    逆后序遍历:1,3,6,2,5,4

    后序遍历:4,5,2,6,3,1

    观察发现:交换左右子树的二叉树先序遍历=二叉树逆后序遍历=后序遍历反着来

    因此,我们的目标是,想办法吧二叉树变成交换左右子树的二叉树,然后push进一个stack里,最后只要pop出来。

    代码实现如下:

       /**
         * 通过后序遍历遍历二叉树
         *
         * @param
         */
        public static void postOrderTraversalWithStack(TreeNode root) {
            Stack<TreeNode> src = new Stack<TreeNode>();
            Stack<TreeNode> re = new Stack<TreeNode>();
            //将节点push进src
            src.push(root);
            while (!src.isEmpty()) {
                TreeNode p = src.pop();
                re.push(p);
                if (p.leftchild != null) {
                    src.push(p.leftchild);
                }
                if (p.rightchild != null) {
                    src.push(p.rightchild);
                }
            }
            //输出最终后序遍历的结果
            while (!re.isEmpty()) {
                System.out.print(re.pop().data + " ");
            }
        }

     

    展开全文
  • 树的后序遍历(递归和非递归java实现)
                                   树的后序遍历(递归和非递归java实现)
    树的基本遍历是解决树相关问题的基础,所以要很熟悉,理解透彻!




    二叉树的结点定义:
    class BinaryTree{  
    public int value;  
    public BinaryTree leftNode;  
    public BinaryTree rightNode;  
    BinaryTree(int x) { value = x; }  
    }  




    后序遍历:左右根的原则遍历访问树的所有结点;
    void postOrder(BinaryTree root){
    	if(root !=null){	
    	postOrder(root.left);	
    	postOrder(root.right);
    	System.out.println(root.value);
    	}
    }


    后序遍历的非递归实现【java实现】

    package com.mytest.mymain;
    import java.util.Stack;
    class BTree{
    	public int value;  //public static int value;  那么最终输出都为8个8
    	public BTree left;  
    	public BTree right;  
    	BTree(int x) { value = x; }  
    }
    public class PreOrderwithStack {
    	public static void main(String[] args) {
    		BTree root=new BTree(1);
    		BTree Node2=new BTree(2);
    		BTree Node3=new BTree(3);
    		BTree Node4=new BTree(4);
    		BTree Node5=new BTree(5);
    		BTree Node6=new BTree(6);
    		BTree Node7=new BTree(7);
    		BTree Node8=new BTree(8);
    	
    		root.left=Node2;
    		root.right=Node3;
    		
    		Node2.left=Node4;
    		Node2.right=Node5;
    		
    		Node3.left=Node6;
    		Node3.right=Node7;
    		
    		Node4.left=Node8;
    		
    		preorderfun(root);
    		System.out.println();
    		inorderfun(root);
    		System.out.println();
    		postorderfun(root);
    	}
    	public static void postorderfun(BTree root){
    		Stack<BTree> stack =new Stack<BTree>();
    		BTree proot;//标记栈顶元素前一个被访问的元素
    		int flag;//root的左孩子未被访问;
    		if(root!=null){
    			do{
    				while(root!=null){//将root所有左孩子全部入栈
    					stack.push(root);
    					root=root.left;
    				  }
    				
    				//执行到此处,栈顶元素没有左孩子或者左子树已经被访问过;
    				proot=null;//标记栈顶元素前一个被访问的元素,或者此时为最左下边,该元素前一个被访问的元素肯定为空。
    				flag=1;//root的左孩子已经被访问;或者root为null
    				
    				while(!stack.isEmpty() && flag==1){
    					root=stack.peek();       //取到栈顶元素,但是不出栈;
    					if(root.right==proot){
    						root=stack.pop();
    						System.out.print(root.value+"  ");
    						proot=root;
    					}else{
    						root=root.right;
    						flag=0;//root左边孩子未被访问;
    					}
    				}
    			}while(!stack.isEmpty());
    		}
    		
    		
    	}
    
    
    






    展开全文
  • 今天刷后序遍历非递归实现时,因为以前看过借助一个栈和队列来实现,但始终模糊不清,不知道如何写,只好自己捋了一遍,然后查了下,发现和很多人写法有差异,故放出来,欢迎指正,如有知道用栈和队列方式实现的朋友...
        

    今天刷后序遍历非递归实现时,因为以前看过借助一个栈和队列来实现,但始终模糊不清,不知道如何写,只好自己捋了一遍,然后查了下,发现和很多人写法有差异,故放出来,欢迎指正,如有知道用栈和队列方式实现的朋友,也请赐教。

        public ArrayList<Integer> postorderTraversal(TreeNode root) {
            ArrayList<Integer> result = new ArrayList<>();
            if(root==null){
                return result;
            }
            TreeNode node = root;
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> markStack = new Stack<>();
            while(node!=null||!stack.isEmpty()){
                while(node!=null){
                    stack.push(node);
                    node = node.left;
                }
                
                while(!markStack.isEmpty()&&markStack.peek()==stack.peek()){
                      markStack.pop();;
                      result.add(stack.pop().val);
                }
                if(!stack.isEmpty()){
                    node = stack.peek();
                    markStack.push(node);
                    node = node.right;
                }
            }
            
            
            return result;
        }
    展开全文
  • Java方式实现的二叉树前中后序遍历的递归及非递归方式

    最近在研究数据结构算法,发现许多树类的算法都很灵活,所以研究了一下基础二叉树的递归以及非递归的三种遍历方式,在这里记录下来方便以后回忆。

    以该树为例:
    这里写图片描述

    二叉树的遍历为三种:前序遍历、中序遍历、后续遍历。
    前序遍历(先根遍历):即是在二叉树的遍历过程中,先访问根节点若左子树不空则访问左节点、若右子树不空则访问右节点,在访问左右子树时亦是先访问根节点再访问左节点、右节点,以此顺序。
    此树的先序遍历结果为:631254978

    中序遍历(中跟遍历):即是先访问左节点,再根节点,最后右节点。
    中序遍历结果为:123456789

    后序遍历(后跟遍历):先访问左节点,再右节点、最后根节点。
    后序遍历结果为:214538796

    1、递归方式
    建立数据模型()

    public class Node {//二叉树节点
        private int data;
        private Node leftNode;
        private Node rightNode;
    
        public Node(int data, Node leftNode, Node rightNode){
            this.data = data;
            this.leftNode = leftNode;
            this.rightNode = rightNode;
        }
    
        public int getData(){
            return data;
        }
    
        public void setData(int data){
            this.data = data;
        }
    
        public Node getLeftNode(){
            return leftNode;
        }
    
        public void setLeftNode(Node leftNode){
            this.leftNode = leftNode;
        }
    
        public Node getRightNode(){
            return rightNode;
        }
    
        public void setRightNode(Node rightNode){
            this.rightNode = rightNode;
        }
    }

    三种遍历:

    package Binary_tree;
    
    public class Traverse_tree {
    
        /*
         * 二叉树先序中序后序排序
         * 方式:递归。
         */
    
        //注意必须逆序简历,先建立子节点,再逆序往上建立,
        //因为非叶子节点会使用到下面的节点,而初始化是按顺序初始化得,不逆序建立会报错
        public static Node init(){
            Node J = new Node(8, null, null);
            Node H = new Node(4, null, null);
            Node G = new Node(2, null, null);
            Node F = new Node(7, null, J);
            Node E = new Node(5, H, null);
            Node D = new Node(1, null, G);
            Node C = new Node(9, F, null);
            Node B = new Node(3, D, E);
            Node A = new Node(6, B, C);
            return A;  //返回根节点
        }
    
        //打印节点数值
        public static void printNode(Node node){
            System.out.print(node.getData());
        }
    
            public void preOrder(Node root){    //前序遍历
            printNode(root);
            if(root.getLeftNode()!=null)
                preOrder(root.getLeftNode());
            if(root.getRightNode()!=null)
                preOrder(root.getRightNode());
        }
    
            public void inOrder(Node root){     //中序遍历
            if(root.getLeftNode()!=null)
                inOrder(root.getLeftNode());
            printNode(root);
            if(root.getRightNode()!=null)
                inOrder(root.getRightNode());
        }
    
        public void postOrder(Node root){       //后续遍历
            if(root.getLeftNode()!=null)
                postOrder(root.getLeftNode());
            if(root.getRightNode()!=null)
                postOrder(root.getRightNode());
            printNode(root);
        }
    
        public static void main(String[] args){
            Node node = Traverse_tree.init();
            Traverse_tree obj = new Traverse_tree();
    
            System.out.println("前序遍历");
            obj.preOrder(node);
            System.out.println();
    
            System.out.println("中序遍历");
            obj.inOrder(node);
            System.out.println();
    
            System.out.println("后续遍历");
            obj.postOrder(node);
    
        }
    
    }
    

    2、非递归的三种遍历方式:

    import java.util.Stack;
    
    public class Nontraverse_tree {
    
        Node node;
    
    
        public static Node_Nontraverse init(){
            Node I = new Node(8,null,null);
            Node H = new Node(4,null,null);
            Node G = new Node(2,null,null);
            Node D = new Node(1,null,G);
            Node E = new Node(5,H,null);
            Node F = new Node(7,null,I);
            Node B = new Node(3,D,E);
            Node C = new Node(9,F,null);
            Node A = new Node(6,B,C);
            return A;
        }
    
        public void preOrder(Node node){
            Node root = node;
            Stack<Node> stack = new Stack<Node>();
            while(root!=null||stack.size()>0){
                if(root!=null){
                    stack.push(root);
                    System.out.print(root.getData());
                    root = root.getLeftNode();
    
                }
                else{
                    root = stack.pop();
                    root = root.getRightNode();
                }
    
            }
        }
    
        public void inOrder(Node node){
            Node root = node;
            Stack<Node> stack = new Stack<Node>();
            while(root!=null||stack.size()>0){
                if(root!=null){
                    stack.push(root);
    
                    root = root.getLeftNode();
    
                }
                else{
                    root = stack.pop();
                    System.out.print(root.getData());
                    root = root.getRightNode();
                }
    
            }
        }
    
        public void postOrder(Node node){
            Node root = node;
            Stack<Node> stack = new Stack<Node>();
            Stack<Node> output = new Stack<Node>();
            while(root!=null||stack.size()>0){
                if(root!=null){
                    stack.push(root);
                    output.push(root);
                    root = root.getRightNode();
                }
                else{
                    root = stack.pop();
                    root = root.getLeftNode();
                }
            }
    
            while(output.size()>0){
                System.out.print(output.pop().getData());
            }
    
        }
    
        public static void main(String[] args){
            Nontraverse_tree obj = new Nontraverse_tree();
            Node root = Nontraverse_tree.init();
    
            System.out.println("二叉树的非递归前序遍历:");
            obj.preOrder(root);
            System.out.println();
    
            System.out.println("二叉树的非递归中序遍历:");
            obj.inOrder(root);
            System.out.println();
    
            System.out.println("二叉树的非递归后序遍历:");
            obj.postOrder(root);
        }
    
    }
    

    原帖地址为:

    http://blog.csdn.net/jssongwei/article/details/50790253

    展开全文
  • java版的二叉树的先序遍历、中序遍历以及后序遍历(递归以及非递归方式)
  • 后序遍历递归)代码图解功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个...
  • import java.util.ArrayList; import java.util.List; import java.util.Stack; ...public class PostOrder... //后序遍历非递归 public static void postOrderNoR(Node root) { Stack<Node> stack = n...
  • 二叉树后序遍历非递归实现(java)

    千次阅读 2018-09-29 23:42:48
    后序遍历:双栈法,和层次遍历(双队列)很相似,唯一区别在于层次遍历用的是队列,后序遍历用的是栈。 public static void posOrderUnRecur1(Node head){ System.out.print("PosOrder:"); if(head != null){ ...
  • 二叉树的先序、中序、后序遍历(递归 and 非递归)递归好写,非递归需要用栈就难写了。。package lianjia;import java.util.*; public class Main{ // 先序遍历(递归) public static void preOrder(TreeNode root...
  • 后序遍历递归定义: 先左子树,后右子树,再根节点。后序遍历的难点在于:需要判断上次访问的节点是位于左子树,还是右子树。若是位于左子树,则需跳过根节点,先进入右子树,再回头访问根节点;若是位于右子树,则...
  • 二叉树最大深度,前序遍历、中序遍历、后序遍历算法,包含递归与非递归 1 import java.util.*; 2 3 import javax.swing.plaf.synth.SynthSpinnerUI; 4 class TreeNode{ 5 int data; 6 TreeNode ...
  • 后序遍历 代码 package com.li.traversal; import java.util.Stack; public class LRD { public static void main(String[] args) { TreeNode[] nodes = new TreeNode[10]; for(int i=0;i<10;...
  • 二叉树的递归、非递归前中后序遍历和高度前中后序遍历递归非递归层次遍历树的高度递归非递归 前中后序遍历 递归 /** * 递归的前中后 */ public static void preOrder(TreeNode node){ System.out.println(node....
  • 二叉树的前序、中序、后序遍历非递归java 核心思路是把每一个结点看成父节点,叶子结点是左右孩子是null的父结点。 前序遍历 思路: 使用一个栈来存储结点,以便回到之前的父结点。 不断往左子树深入并不断先打印...
  • 对于二叉树的遍历一共存在两种类型:递归遍历和非递归遍历,针对每种类型有分为先序遍历,中序遍历和后序遍历。以下是六种遍历执行过程。 //先序遍历二叉树(递归形式) public List preOrder1(TreeNode root){ ...
  • //二叉树的先序,中序,后序遍历,包括递归方式和非递归方式 public class PreInPosTraversal { public static class Node { public int value; public Node left; public Node righ...
  • 到现在,树的深度遍历方式中就剩下树的后序...对于后序遍历,我们先给出一个递归的解法: package com.mengzhidu.teach.algorithm.tree.demo.traversal; import com.mengzhidu.teach.algorithm.tree.demo.TreeNode;...
  • 后序遍历: 对于节点cur可以分情况讨论 1. cur如果是叶子节点,直接输出 2. cur如果有孩子,且孩子没有被访问过,则按照右孩子,左孩子的顺序依次入栈 3. cur如果有孩子,而且孩子都已经访问过,则访问p节点 ...
  • 对于二叉树这种数据结构的...中序遍历非递归实现): 二叉树的中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。 代码实现: import java.util.Stack; public class Main { public static void main(String
  • 实现二叉树的先序、中序、后序遍历,包括递归方式和非递归方式 import java.util.Stack; public class Code_01_PreInPosTraversal { public static class Node { public int value; public Node left; public ...
  • 后序遍历非递归算法,是难一点儿。 前序遍历: 递归算法: public class LC144Try1 { public List&lt;Integer&gt; preorderTraversal(TreeNode root) { List&lt;Integer&gt; arr=new ...
  • 二叉树三种遍历的递归非递归实现
  • 二叉树的先序遍历递归实现: public List&lt;Integer&gt; preorderTraversal(TreeNode root) { //用栈来实现 List&lt;Integer&gt; list = new ArrayList&lt;Integer&gt;(); ...
  • 前序遍历 非递归   public void preordernorec(TreeNode root){ //System.out.println("先序遍历非递归):"); //用数组模拟栈,假设有节点个数不超过32个 TreeNode[] stack = new TreeNode[32]; for...
  • 递归实现: 当节点不为空时,每次遍历现将节点值添加进list,之后,左子树补空,遍历左子树;右指数不空,遍历右子树;最终返回list。需要注意的是根节点为空的情况,在遍历之前,根节点为空,直接返回(全局)list...
  • 递归的写法相对简单,但有时候非递归的实现,却需要想一想。今天,统一思考了一下,并用Java进行了实现,记录在这里,以便脑子宕机的时候看看。 一切的递归,都可以用自己写的栈来实现。 二叉树节点类: /** * ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 604
精华内容 241
关键字:

后序遍历非递归java

java 订阅