本文实例讲述了Java实现的二叉树常用操作。分享给大家供大家参考，具体如下：
|
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
123
124
125
126
127
128
129
130
131
|
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
//二叉树的建树，前中后 递归非递归遍历 层序遍历
//Node节点
class Node {
int element;
Node left;
Node right;
public Node() {
}
public Node(int element) {
this.element = element;
}
}
// BinaryTree
public class Tree {
// creat tree from array
public static Node creatTree(int[] data, int i) {
if (i >= data.length || data[i] == -1)
return null;
Node temp = new Node(data[i]);
temp.left = creatTree(data, i * 2 + 1);
temp.right = creatTree(data, i * 2 + 2);
return temp;
}
// pre前序遍历递归
public static void pre(Node temp) {
if (temp == null)
return;
System.out.print(temp.element + " ");
pre(temp.left);
pre(temp.right);
}
// mid中序遍历递归
public static void mid(Node temp) {
if (temp == null)
return;
mid(temp.left);
System.out.print(temp.element + " ");
mid(temp.right);
}
// last后序遍历递归
public static void last(Node temp) {
if (temp == null)
return;
last(temp.left);
last(temp.right);
System.out.print(temp.element + " ");
}
// pre1前序遍历非递归
public static void pre1(Node temp) {
Stack<Node> stack = new Stack<>();
while (temp != null || !stack.isEmpty()) {
while (temp != null) {
stack.push(temp);
System.out.print(temp.element + " ");
temp = temp.left;
}
if (!stack.isEmpty()) {
temp = stack.pop().right;
}
}
}
// mid1中序遍历非递归
public static void mid1(Node temp) {
Stack<Node> stack = new Stack<>();
while (temp != null || !stack.isEmpty()) {
while (temp != null) {
stack.push(temp);
temp = temp.left;
}
if (!stack.isEmpty()) {
temp = stack.pop();
System.out.print(temp.element + " ");
temp = temp.right;
}
}
}
// last1后序遍历非递归
public static void last1(Node temp) {
Stack<Node> stack = new Stack<>();
Stack<Node> stack2 = new Stack<>();
while (temp != null || !stack.isEmpty()) {
while (temp != null) {
stack.push(temp);
stack2.push(temp);
temp = temp.right;
}
if (!stack.isEmpty()) {
temp = stack.pop().left;
}
}
while (!stack2.isEmpty())
System.out.print(stack2.pop().element + " ");
}
// ceng层序遍历
public static void ceng(Node temp) {
if (temp == null)
return;
Queue<Node> queue = new ArrayDeque<>();
queue.offer(temp);
while (!queue.isEmpty()) {
temp = queue.poll();
System.out.print(temp.element + " ");
if (temp.left != null)
queue.offer(temp.left);
if (temp.right != null)
queue.offer(temp.right);
}
}
// Demo
public static void main(String[] args) {
int[] array = { 1, 2, 3, 4, 5, 6, 7, -1, -1, 10, -1, -1, 13 };
Node tree = creatTree(array, 0);
System.out.println("服务器之家测试结果：");
pre(tree);
System.out.println();
pre1(tree);
System.out.println();
mid(tree);
System.out.println();
mid1(tree);
System.out.println();
last(tree);
System.out.println();
last1(tree);
System.out.println();
ceng(tree);
}
}
|
运行结果：
希望本文所述对大家java程序设计有所帮助。
原文链接：http://blog.csdn.net/idealemail/article/details/51382114