• 前序遍历 非递归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();
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实现）
• // 中序遍历 非递归算法 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...

...

java 订阅