算法初级——二叉树的遍历

实现二叉树的先序、中序、后序遍历,包括递归方式和非递归方式
/*
* 二叉树的遍历,二叉树每个节点在遍历的过程中访问三次,第一次访问打印为先序遍历,第二次访问打印为中序打印,第三次访问打印为后序打印。
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
import java.util.Stack;

public class 二叉树的遍历 {
    public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int data) {
            this.value = data;
        }  
    }
    //递归先序:中左右
    public static void prerec(Node head) {
        if(head == null) {
            return;
        }
        System.out.print(head.value+" ");
        prerec(head.left);
        prerec(head.right);
    }
    //递归中序:左中右
    public static void inrec(Node head) {
        if(head == null) {
            return;
        }
        inrec(head.left);
        System.out.print(head.value+" ");
        inrec(head.right);
    }
    //递归后序:左右中
    public static void posrec(Node head) {
        if(head == null) {
            return;
        }
        posrec(head.left);
        posrec(head.right);
        System.out.print(head.value+" ");
    }
    //非递归先序:中左右 构建一个栈,头结点压入栈,然后弹出栈,打印头结点,如果头结点有右孩子,压入栈内,如果头结点有左孩子,
    //压入栈内,然后执行while循环。
    public static void preunrec(Node head) {
        if(head != null) {
            Stack<Node> stack = new Stack<Node>();
            stack.add(head);
            while(!stack.isEmpty()) {
                head = stack.pop();
                System.out.print(head.value + " ");
                if(head.right != null) {
                    stack.push(head.right);
                }
                if(head.left != null) {
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }
    //非递归中序:左中右 当前节点为空,从栈中拿一个,打印,当前节点右孩子;当前节点不为空,当前节点压入栈,当前节点左孩子
    public static void inunrec(Node head) {
        if(head != null) {
            Stack<Node> stack = new Stack<Node>();
            while(!stack.isEmpty() || head != null) {
                if(head != null) {
                    stack.push(head);
                    head = head.left;
                }else {
                    head = stack.pop();
                    System.out.print(head.value + " ");
                    head = head.right;
                }
            }
        }
        System.out.println();
    }
    //非递归后序:左右中 根据先序遍历的思想,借用两个辅助栈,
    public static void posunrec1(Node head) {
        if(head != null) {
            Stack<Node> stack = new Stack<Node>();
            Stack<Node> stack2 = new Stack<Node>();
            stack.add(head);
            while(!stack.isEmpty()) {
                head = stack.pop();
                stack2.push(head);
                if(head.left != null) {
                    stack.push(head.left);
                }
                if(head.right != null) {
                    stack.push(head.right);
                }
            }
            while (!stack2.isEmpty()) {
                System.out.print(stack2.pop().value + " ");
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = new Node(5);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.left.left.left = new Node(1);
        head.right.left = new Node(7);
        head.right.left.left = new Node(6);
        head.right.right = new Node(10);
        head.right.right.left = new Node(9);
        head.right.right.right = new Node(11);
        prerec(head);
        System.out.println();
        preunrec(head);
        System.out.println();
        inrec(head);
        System.out.println();
        inunrec(head);
        System.out.println();
        posrec(head);
        System.out.println();
        posunrec1(head);
    }
}
0 条评论
发表一条评论