Wetry文川

# 数据结构与算法分析 二叉树的遍历

### 树的遍历（先中后）

#### 递归版本

``````package cn.ustb.树的遍历;
//递归遍历
public class MyBinaryTree {
static class Node{
Node left;
Node right;
private int val;
public Node(int val) {
super();
this.val = val;
}
}

/*
* 递归版本
*/
//前序
public static void preOrder(Node node){
if(node == null)
return;
System.out.print(node.val);
preOrder(node.left);
preOrder(node.right);
}
//中序
public static void inOrder(Node node){
if(node == null)
return;
inOrder(node.left);
System.out.print(node.val);
inOrder(node.right);
}
//后序
public static void postOrder(Node node){
if(node == null)
return;
postOrder(node.left);
postOrder(node.right);
System.out.print(node.val);
}

public static void main(String[] args) {
/*
*       4
*     /   \
*    2     7
*   / \   / \
*  1   3 6   9
*
*/
Node n1 = new Node(4);
Node n2 = new Node(2);
Node n3 = new Node(7);
Node n4 = new Node(1);
Node n5 = new Node(3);
Node n6 = new Node(6);
Node n7 = new Node(9);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
n3.right = n7;

preOrder(n1);//4213769
System.out.println();
inOrder(n1);//1234679
System.out.println();
postOrder(n1);//1326974
}
}
``````

#### 非递归版本

##### MyStack的数组实现

``````package cn.ustb.树的遍历;

import java.util.Arrays;

public class MyStack<T> {

private T[] nodes;
volatile int size = 0;
private static final int PRIMARY_CAPACITY = 10;

public MyStack() {
super();
this.nodes = (T[]) new Object[PRIMARY_CAPACITY];
this.size = 0;
}

public void push(T t){
ensureCapacity();
nodes[size++] = t;
}

public T pop(){
if(empty())
throw new RuntimeException("空！");
T temp = nodes[--size];
nodes[size] = null;
return temp;
}
public T peek(){
if(empty())
throw new RuntimeException("空！");
return nodes[size-1];
}

private void ensureCapacity(){
if(size == nodes.length){
nodes = Arrays.copyOf(nodes, size<<2);
}
}

public int size(){
return size;
}
public boolean empty(){
return size()==0;
}
}
``````
##### 非递归
``````package cn.ustb.树的遍历;

public class MyBinaryTree2 {
static class Node{
Node left;
Node right;
private int val;
public Node(int val) {
super();
this.val = val;
}
}

/*
* 非递归版本，利用栈数据结构
*/
//前序遍历
public static void preOrder(Node node){
if(node == null)return;
MyStack<Node> stack = new MyStack<>();
while(node!=null||!stack.empty()){
while(node!=null){
System.out.print(node.val);//push之前先遍历
stack.push(node);
node = node.left;
}
if(!stack.empty()){
node = stack.pop();
node = node.right;
}
}
}

//中序遍历
public static void inOrder(Node node){
if(node == null)return;

MyStack<Node> stack = new MyStack<>();
while(node!=null||!stack.empty()){
while(node !=null){
stack.push(node);
node = node.left;
}
if(!stack.empty()){
node = stack.pop();
System.out.print(node.val);
node = node.right;
}
}
}
//后序遍历
public static void postOrder(Node node){
if(node == null)return;
MyStack<Node> stack = new MyStack<>();
MyStack<Node> outputStack = new MyStack<>();//存储遍历顺序
while(node!=null||!stack.empty()){
while(node !=null){
stack.push(node);
outputStack.push(node);
node = node.right;
}
if(!stack.empty()){
node = stack.pop();
node = node.left;
}
}
while(!outputStack.empty())
System.out.print(outputStack.pop().val);
}
//后序遍历方法2：
public static void postOrder(Node node,String method2){
if(node == null)return;
MyStack<Node> stack = new MyStack<>();
MyStack<Integer> stateStack = new MyStack<>();//存储对应位置node的输出状态
while(node!=null||!stack.empty()){
while(node !=null){
stack.push(node);
stateStack.push(0);//0代表默认不输出
node = node.left;
}
while(!stack.empty()&&stateStack.peek()==1){//可以输出
stateStack.pop();
System.out.print(stack.pop().val);
}
if(!stack.empty()){//不可以输出 :node == null&&state == 0
stateStack.pop();
stateStack.push(1);
node = stack.peek();
node = node.right;
}
}
}

public static void main(String[] args) {
/*
*       4
*     /   \
*    2     7
*   / \   / \
*  1   3 6   9
*
*/
Node n1 = new Node(4);
Node n2 = new Node(2);
Node n3 = new Node(7);
Node n4 = new Node(1);
Node n5 = new Node(3);
Node n6 = new Node(6);
Node n7 = new Node(9);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
n3.right = n7;

preOrder(n1);//4213769
System.out.println();
inOrder(n1);//1234679
System.out.println();
postOrder(n1);//1326974
System.out.println();
postOrder(n1,"");//1326974
}
}
``````

### 树的遍历（深度优先，广度优先）

#### 深度优先+广度优先

``````package cn.ustb.树的遍历;

public class MyBinaryTree3 {
static class Node{
Node left;
Node right;
private int val;
public Node(int val) {
super();
this.val = val;
}
}

/*
* 深度优先
* 借助 栈  的数据结构实现
*/
public static void deptFirstOrder(Node node){
if(node == null)return ;

MyStack<Node> stack = new MyStack<>();
stack.push(node);
while(!stack.empty()){
node = stack.pop();
System.out.print(node.val);
if(node.right!=null)
stack.push(node.right);
if(node.left!=null)
stack.push(node.left);
}
}

/*
* 广度优先
* 借助  队列  的数据结构实现
*/
if(node == null)return;
MyQueue<Node> queue = new MyQueue<>();//或者自己实现queue
queue.offer(node);
while(!queue.isEmpty()){
node = queue.poll();
System.out.print(node.val);
if(node.left!=null)
queue.offer(node.left);
if(node.right!=null)
queue.offer(node.right);
}
}

public static void main(String[] args) {
/*
*        4
*      /   \
*     2     7
*    / \   / \
*   1   3 6   9
*  /
* 0
*/
Node n1 = new Node(4);
Node n2 = new Node(2);
Node n3 = new Node(7);
Node n4 = new Node(1);
Node n5 = new Node(3);
Node n6 = new Node(6);
Node n7 = new Node(9);
Node n8 = new Node(0);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
n3.right = n7;
n4.left = n8;

deptFirstOrder(n1);//42103769
System.out.println();
System.out.println();

}
}
``````
##### MyQueue的数组实现

``````package cn.ustb.树的遍历;

import java.util.Arrays;

public class MyQueue<T> {
private T[] nodes;

private int start;
private int end;

private static final int PRIMARY_CAPACITY = 10;

public MyQueue() {
super();
nodes = (T[]) new Object[PRIMARY_CAPACITY];
start = end = 0;
}
public void offer(T t){
ensureCapacity();
nodes[end++] = t;
}
public T poll(){
if(isEmpty())
throw new RuntimeException("empty!");
T temp = nodes[start];
nodes[start++] = null;
return temp;
}
public T peek(){
if(isEmpty())
throw new RuntimeException("empty!");
return nodes[start];
}

private void ensureCapacity(){
if(end == nodes.length){
nodes = Arrays.copyOf(nodes, end<<2);//4倍扩容
}
}

public int size(){
return end-start;
}
public boolean isEmpty(){
return size()==0;
}
}
``````

### Wetry文川

09/09
0
0

wustor
2017/11/06
0
0

04/25
66
0
Java学习资料-Java常用算法-二叉树算法

2015/01/28
714
0

JAVA高级架构v
01/09
0
0

Mr_zebra
1分钟前
0
0

AndLong
8分钟前
0
0

internetafei
12分钟前
0
0
Cassandra repair 工具使用

15分钟前
0
0
element-vue使用富文本编辑器【前端】

21分钟前
0
0