精华内容
下载资源
问答
  • 前序遍历 非递归public void preordernorec(TreeNode root){//System.out.println("先序遍历(非递归):");//用数组模拟栈,假设有节点个数不超过32个TreeNode[] stack = new TreeNode[32];for(int i =0;i<32;i++)...

    前序遍历 非递归

    public void preordernorec(TreeNode root){

    //System.out.println("先序遍历(非递归):");

    //用数组模拟栈,假设有节点个数不超过32个

    TreeNode[] stack = new TreeNode[32];

    for(int i =0;i<32;i++){

    stack[i] = null;

    }

    int index =0;

    TreeNode pnode = root;

    while(pnode!=null||index>0){

    while(pnode!=null){

    System.out.print(pnode.getKey()+",");

    stack[index++] = pnode;

    pnode = pnode.getLeftchlid();

    }

    pnode = stack[--index];

    pnode = pnode.getRightchild();

    }

    //System.out.println("");

    }

    前序遍历 递归

    public void preorder(TreeNode root){

    if(root!=null){

    System.out.print(root.getKey()+",");

    preorder(root.getLeftchlid());

    preorder(root.getRightchild());

    }

    }

    中序遍历 非递归

    public void inordernorec(TreeNode root){

    TreeNode[] stack = new TreeNode[32];

    int index=0;

    for(int i =0;i<32;i++){

    stack[i] = null;

    }

    TreeNode pnode = root;

    while(pnode!=null||index>0){

    while(pnode!=null){

    stack[index++] = pnode;

    pnode = pnode.getLeftchlid();

    }

    pnode = stack[--index];

    System.out.print(pnode.getKey()+",");

    pnode = pnode.getRightchild();

    }

    //System.out.println("");

    }

    中序遍历 递归

    public void inorder(TreeNode root){

    if(root!=null){

    inorder(root.getLeftchlid());

    System.out.print(root.getKey()+",");

    inorder(root.getRightchild());

    }

    }

    后序遍历 非递归

    public void postordernorec(TreeNode root){

    TreeNode[] stack = new TreeNode[32];

    int index=0;

    for(int i =0;i<32;i++){

    stack[i] = null;

    }

    TreeNode pnode = root;

    TreeNode LastVisit = null;

    while(pnode!=null||index>0){

    while(pnode!=null){

    stack[index++] = pnode;

    pnode = pnode.getLeftchlid();

    }

    pnode=stack[index-1];

    if(pnode.getRightchild()==null||pnode.getRightchild()==LastVisit){

    System.out.print(pnode.getKey()+",");

    LastVisit = pnode;

    index--;

    pnode = null;

    }

    else

    {

    pnode = pnode.getRightchild();

    }

    }

    }

    后序遍历 递归

    public void postorder(TreeNode root){

    if(root!=null){

    postorder(root.getLeftchlid());

    postorder(root.getRightchild());

    System.out.print(root.getKey()+",");

    }

    }

    展开全文
  • 二叉树最大深度,前序遍历、中序遍历、后序遍历算法,包含递归与非递归 1 import java.util.*; 2 3 import javax.swing.plaf.synth.SynthSpinnerUI; 4 class TreeNode{ 5 int data; 6 TreeNode ...

    二叉树最大深度,前序遍历、中序遍历、后序遍历算法,包含递归与非递归

      1 import java.util.*;
      2 
      3 import javax.swing.plaf.synth.SynthSpinnerUI;
      4 class TreeNode{
      5     int data;
      6     TreeNode lefchild=null;
      7     TreeNode rightchild=null;
      8     TreeNode(int data,TreeNode leftchild,TreeNode rightchild){
      9         this.data=data;
     10         this.lefchild=leftchild;
     11         this.rightchild=rightchild;
     12     }
     13 }
     14 public class BinaryTree {
     15 
     16     public static void main(String[] args) {
     17         // TODO Auto-generated method stub
     18         TreeNode J=new TreeNode(8,null,null);
     19         TreeNode H=new TreeNode(4,null,null);
     20         TreeNode G=new TreeNode(2,null,null);
     21         TreeNode F=new TreeNode(7,null,J);
     22         TreeNode E=new TreeNode(5,H,null);
     23         TreeNode D=new TreeNode(1,null,G);
     24         TreeNode C=new TreeNode(9,F,null);
     25         TreeNode B=new TreeNode(3,D,E);
     26         TreeNode A=new TreeNode(6,B,C);
     27         BinaryTree p=new BinaryTree();
     28         int maxdepth=p.getMaxDepth(A);
     29         System.out.println("最大深度:"+maxdepth);
     30         
     31         System.out.print("递归中序遍历:");
     32         p.inorder(A);
     33         System.out.println();
     34         System.out.print("非递归中序遍历:");
     35         p.inOrder(A);
     36         System.out.println();
     37         
     38         System.out.print("递归前序遍历:");
     39         p.preorder(A);
     40         System.out.println();
     41         System.out.print("非递归前序遍历:");
     42         p.preOrder(A);
     43         System.out.println();
     44         
     45         System.out.print("递归后序遍历:");
     46         p.postorder(A);
     47         System.out.println();
     48         System.out.print("非递归后序遍历:");
     49         p.postOrder(A);
     50         System.out.println();
     51     }
     52     /*获取最大深度*/
     53     public int getMaxDepth(TreeNode root){
     54         if(root==null){
     55             return 0;
     56         }else{
     57             int leftDepth=getMaxDepth(root.lefchild);
     58             int rightDepth=getMaxDepth(root.rightchild);
     59             return 1+Math.max(leftDepth, rightDepth);        }
     60     }
     61     /*递归中序遍历*/
     62     public void inorder(TreeNode root){
     63         if(root==null){
     64             return;
     65         }else{
     66             inorder(root.lefchild);
     67             System.out.print(root.data+" ");
     68             inorder(root.rightchild);
     69         }
     70     }
     71     /*递归前序遍历*/
     72     public void preorder(TreeNode root){
     73         if(root==null){
     74             return;
     75         }else{
     76             System.out.print(root.data+" ");
     77             preorder(root.lefchild);
     78             preorder(root.rightchild);
     79         }
     80     }
     81     /*递归后序遍历*/
     82     public void postorder(TreeNode root){
     83         if(root==null){
     84             return;
     85         }else{
     86             postorder(root.lefchild);
     87             postorder(root.rightchild);
     88             System.out.print(root.data+" ");
     89         }
     90     }
     91     /*非递归中序遍历*/
     92     public void inOrder(TreeNode root){
     93         Stack<TreeNode> stack=new Stack<TreeNode>();
     94         while(root!=null||!stack.isEmpty()){
     95             while(root!=null){
     96                 stack.push(root);
     97                 root=root.lefchild;
     98             }
     99             if(!stack.isEmpty()){
    100                 root=stack.pop();
    101                 System.out.print(root.data+" ");
    102                 root=root.rightchild;
    103             }
    104         }
    105     }
    106     /*非递归前序遍历*/
    107     public void preOrder(TreeNode root){
    108         Stack<TreeNode> stack=new Stack<TreeNode>();
    109         while(root!=null||!stack.isEmpty()){
    110             while(root!=null){
    111                 System.out.print(root.data+" ");
    112                 stack.push(root);
    113                 root=root.lefchild;
    114             }
    115             if(!stack.isEmpty()){
    116                 root=stack.pop();
    117                 root=root.rightchild;
    118             }
    119         }
    120     }
    121     /*非递归后序遍历*/
    122     public void postOrder(TreeNode root){
    123         Stack<TreeNode> stack=new Stack<TreeNode>();
    124         TreeNode prev=null;
    125         while(root!=null||!stack.isEmpty()){
    126             while(root!=null){
    127                 stack.push(root);
    128                 root=root.lefchild;
    129             }
    130             if(!stack.isEmpty()){
    131                 TreeNode temp=stack.peek().rightchild;
    132                 if(temp==null||temp==prev){
    133                     root=stack.pop();
    134                     prev=root;
    135                     System.out.print(root.data+" ");
    136                     root=null;
    137                 }else{
    138                     root=temp;
    139                 }
    140             }
    141         }
    142     }
    143 }

     

    转载于:https://www.cnblogs.com/lulushow/p/6813967.html

    展开全文
  • 前序遍历 非递归   public void preordernorec(TreeNode root){ //System.out.println("先序遍历非递归):"); //用数组模拟栈,假设有节点个数不超过32个 TreeNode[] stack = new TreeNode[32]; for...

    前序遍历 非递归

     

    	public void preordernorec(TreeNode root){
    		//System.out.println("先序遍历(非递归):");
    		//用数组模拟栈,假设有节点个数不超过32个
    		TreeNode[] stack = new TreeNode[32];
    		for(int i =0;i<32;i++){
    			stack[i] = null;
    		}
    		int index =0;
    		TreeNode pnode = root;
    		while(pnode!=null||index>0){
    			while(pnode!=null){
    				System.out.print(pnode.getKey()+",");
    				stack[index++] = pnode;				
    				pnode = pnode.getLeftchlid();
    			}
    			pnode = stack[--index];
    			pnode = pnode.getRightchild();
    		}
    		//System.out.println("");
    	}


     

    前序遍历 递归

    public void preorder(TreeNode root){
    		
    		if(root!=null){
    			System.out.print(root.getKey()+",");
    			preorder(root.getLeftchlid());
    			preorder(root.getRightchild());
    		}
    	}


     

    中序遍历 非递归

    	public void inordernorec(TreeNode root){
    		TreeNode[] stack = new TreeNode[32];
    		int index=0;
    		for(int i =0;i<32;i++){
    			stack[i] = null;
    		}
    		TreeNode pnode = root;
    		while(pnode!=null||index>0){
    			while(pnode!=null){
    				stack[index++] = pnode;
    				pnode = pnode.getLeftchlid();
    			}
    			pnode = stack[--index];
    			System.out.print(pnode.getKey()+",");
    			pnode = pnode.getRightchild();
    		}
    		
    		//System.out.println("");
    	}


     

    中序遍历 递归

     

    public void inorder(TreeNode root){
    		
    		if(root!=null){
    			
    			inorder(root.getLeftchlid());
    			System.out.print(root.getKey()+",");
    			inorder(root.getRightchild());
    		}
    	}


     

    后序遍历 非递归

     

    public void postordernorec(TreeNode root){
    	TreeNode[] stack = new TreeNode[32];
    	int index=0;
    	for(int i =0;i<32;i++){
    		stack[i] = null;
    	}
    	TreeNode pnode = root;
    	TreeNode LastVisit = null;
    	while(pnode!=null||index>0){
    		while(pnode!=null){
    			stack[index++] = pnode;
    			pnode = pnode.getLeftchlid();
    		} 
    		pnode=stack[index-1];
    		if(pnode.getRightchild()==null||pnode.getRightchild()==LastVisit){
    			System.out.print(pnode.getKey()+",");
    			LastVisit = pnode;
    			index--;
    			pnode = null;
    		}
    		else
    		{
    			pnode = pnode.getRightchild();
    		}
    	}
    }


     

    后序遍历 递归

    public void postorder(TreeNode root){
    	if(root!=null){
    		postorder(root.getLeftchlid());
    		postorder(root.getRightchild());
    		System.out.print(root.getKey()+",");
    	}
    }


     

     

    展开全文
  • 中序遍历比前序遍历绕一点。思路就是先将最左边的节点依次入栈,当左子节点为空时,pop出根节点,再对根节点的右子树进行同样的方法入栈。 package 二叉树的中序遍历_94; import java.util.ArrayList; import java...

    中序遍历比前序遍历绕一点。思路就是先将最左边的节点依次入栈,当左子节点为空时,pop出根节点,再对根节点的右子树进行同样的方法入栈。

    package 二叉树的中序遍历_94;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    import 二叉树的中序遍历_94.TreeNode;
    // 迭代法
    public class Solution2 {
    
    	public static void main(String[] args) {
    		// TODO 自动生成的方法存根
    		TreeNode root = new TreeNode(1);
    		root.right = new TreeNode(2);
    		root.right.left = new TreeNode(3);
    		System.out.println(inorderTraversal(null));
    	}
    
    	static List<Integer> inorderTraversal(TreeNode root) {
    		// TODO 自动生成的方法存根
    		if (root == null) {
                return new ArrayList<Integer>();
            }
            List<Integer> list = new ArrayList<Integer>();
    
            Stack<TreeNode> s = new Stack<TreeNode>();
            TreeNode currentNode;
            while(!s.isEmpty() || root != null) {
            	while(root != null) {
            		s.push(root);
            		root = root.left;
            	}
            	currentNode = s.pop();
            	list.add(currentNode.val);
            	root = currentNode.right;
            }
            return list;
         
    	}
    
    }
    

     

    展开全文
  • 在上一篇中我们介绍了树的前序遍历,这一节我们介绍树的中序遍历。所谓树的中序遍历,就是先遍历左子树,然后遍历根节点,然后遍历右子树。 我们先来看一下递归的实现方式(这里直接传入了空节点): package ...
  • 非递归中序遍历:关键是最左节点的寻找 public static void inOrder(Node root) { java.util.Stack stack = new java.util.Stack(); Node current = root; if(root != null) { stack.push...
  • 二叉树的中序遍历Java 二叉树中序非递归遍历) 很久没写算法,一个水题竟然写了好久 class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } /** * 二叉树...
  • import java.util.*; public class InorderTree { public InorderTree(){} public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list= new ArrayList<>(); i...
  • 遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。 若二叉树为空则结束返回,否则: (1)访问根结点; (2)前序遍历左子树; (3)前序遍历右子树 ; 需要注意的是:遍历...
  • 递归算法代码记录: public List<Integer> preorderTraversal(TreeNode root) { if(root==null){ return new ArrayList(); } List<Integer> resultList=new ArrayList(); re
  • 后序遍历非递归算法,是难一点儿。 前序遍历: 递归算法: public class LC144Try1 { public List&lt;Integer&gt; preorderTraversal(TreeNode root) { List&lt;Integer&gt; arr=new ...
  • 思路其实和之前做过的#数据结构与算法学习笔记#PTA11:先序遍历+中序遍历转后序遍历/二叉树非递归遍历/二叉树栈遍历(JAVA)是一样的。 题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设...
  • 这题关键点在于理解二叉树的非递归遍历,能够看得出入栈顺序就是二叉树的先序遍历序列,出栈顺序就是二叉树的中序遍历序列。理解了这点这道题就转换成已知先序遍历+中序遍历,打印二叉树的后序遍历的问题了。 有两...
  • 二叉树先序遍历、中序遍历、后序遍历的递归以及非递归算法Java实现)
  • java 中序非递归遍历

    2020-09-29 15:01:56
    // 中序遍历 非递归算法 public static void InOrder2(TreeNode root) { if(root==null) return; Stack<TreeNode> stk = new Stack<TreeNode>(); TreeNode p = root;//辅助节点 stk.add(p...
  • 二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。...在三种遍历中,前序和中序遍历非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点。节点分布如下:import j...
  • 这个问题的实现就是迭代器问题,无论是Java还是C++,利用迭代器遍历树节点(Java中是TreeMap类,C++中是map类)都使用了中序遍历,且无法使用递归和栈,算法效率近似为O(1),不可能每个节点只访问一次。  纯C实现的...
  • 中序遍历的次序依次是左、根、右。后序遍历的次序依次是:左、右、根),多叉树和二叉树类似。另外,在操作“树”这种数据结构的时候。首先能想到的该用递归递归大概是天然的为树而生的。参考Java代码...
  • 今天主要聊聊二叉树的非递归遍历,主要借助于“栈”后进先出的特性来保存节点的顺序,先序遍历和中序遍历相对来说比较简单,重点理解后序遍历。1. 先看看节点类型://二叉树的节点类型private class Node{int data; ...
  • //进入到下一个左子树中 } } } } 3、中序遍历 3.1 递归操作 //中序遍历递归操作 public voidinOrder(TreeNode root) {if(root==null)return; inOrder(root.lchild); System.out.print(root.data+" "); inOrder...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 170
精华内容 68
关键字:

中序遍历非递归算法java

java 订阅