一、树
树与线性表、栈、队列等线性结构不同，树是一种非线性结构。
一棵树只有一个根节点，如果一棵树有了多个根节点，那它已经不再是一棵树了，而是多棵树的集合，也被称为森林。
二、树的父节点表示法
树中除根节点之外每个节点都有一个父节点，为了记录树中节点与节点之间的父子关系，可以为每个节点增加一个parent域，用以记录该节点的父节点。
|
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
132
133
134
135
136
137
|
package com.ietree.basic.datastructure.tree;
import java.util.ArrayList;
import java.util.List;
/**
* Created by ietree
* 2017/4/30
*/
public class TreeParent<E> {
public static class Node<T> {
T data;
// 保存其父节点的位置
int parent;
public Node() {
}
public Node(T data) {
this.data = data;
}
public Node(T data, int parent) {
this.data = data;
this.parent = parent;
}
public String toString() {
return "TreeParent$Node[data=" + data + ", parent=" + parent + "]";
}
}
private final int DEFAULT_TREE_SIZE = 100;
private int treeSize = 0;
// 使用一个Node[]数组来记录该树里的所有节点
private Node<E>[] nodes;
// 记录树的节点数
private int nodeNums;
// 以指定节点创建树
public TreeParent(E data) {
treeSize = DEFAULT_TREE_SIZE;
nodes = new Node[treeSize];
nodes[0] = new Node<E>(data, -1);
nodeNums++;
}
// 以指定根节点、指定treeSize创建树
public TreeParent(E data, int treeSize) {
this.treeSize = treeSize;
nodes = new Node[treeSize];
nodes[0] = new Node<E>(data, -1);
nodeNums++;
}
// 为指定节点添加子节点
public void addNode(E data, Node parent) {
for (int i = 0; i < treeSize; i++) {
// 找到数组中第一个为null的元素，该元素保存新节点
if (nodes[i] == null) {
// 创建新节点，并用指定的数组元素保存它
nodes[i] = new Node(data, pos(parent));
nodeNums++;
return;
}
}
throw new RuntimeException("该树已满，无法添加新节点");
}
// 判断树是否为空
public boolean empty() {
// 根结点是否为null
return nodes[0] == null;
}
// 返回根节点
public Node<E> root() {
// 返回根节点
return nodes[0];
}
// 返回指定节点（非根结点）的父节点
public Node<E> parent(Node node) {
// 每个节点的parent记录了其父节点的位置
return nodes[node.parent];
}
// 返回指定节点（非叶子节点）的所有子节点
public List<Node<E>> children(Node parent) {
List<Node<E>> list = new ArrayList<Node<E>>();
for (int i = 0; i < treeSize; i++) {
// 如果当前节点的父节点的位置等于parent节点的位置
if (nodes[i] != null && nodes[i].parent == pos(parent)) {
list.add(nodes[i]);
}
}
return list;
}
// 返回该树的深度
public int deep() {
// 用于记录节点的最大深度
int max = 0;
for (int i = 0; i < treeSize && nodes[i] != null; i++) {
// 初始化本节点的深度
int def = 1;
// m 记录当前节点的父节点的位置
int m = nodes[i].parent;
// 如果其父节点存在
while (m != -1 && nodes[m] != null) {
// 向上继续搜索父节点
m = nodes[m].parent;
def++;
}
if (max < def) {
max = def;
}
}
return max;
}
// 返回包含指定值的节点
public int pos(Node node) {
for (int i = 0; i < treeSize; i++) {
// 找到指定节点
if (nodes[i] == node) {
return i;
}
}
return -1;
}
}
|
测试类：
|
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
|
package com.ietree.basic.datastructure.tree;
import java.util.List;
/**
* Created by ietree
* 2017/4/30
*/
public class treeParentTest {
public static void main(String[] args) {
TreeParent<String> tp = new TreeParent<String>("root");
TreeParent.Node root = tp.root();
System.out.println(root);
tp.addNode("节点1", root);
System.out.println("此树的深度：" + tp.deep());
tp.addNode("节点2", root);
// 获取根节点的所有子节点
List<TreeParent.Node<String>> nodes = tp.children(root);
System.out.println("根节点的第一个子节点：" + nodes.get(0));
// 为根节点的第一个子节点新增一个子节点
tp.addNode("节点3", nodes.get(0));
System.out.println("此树的深度：" + tp.deep());
}
}
|
程序输出：
TreeParent$Node[data=root, parent=-1]
此树的深度：2
根节点的第一个子节点：TreeParent$Node[data=节点1, parent=0]
此树的深度：3
三、子节点链表示法
让父节点记住它的所有子节点。
|
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
package com.ietree.basic.datastructure.tree;
import java.util.ArrayList;
import java.util.List;
/**
* Created by ietree
* 2017/4/30
*/
public class TreeChild<E> {
private static class SonNode {
// 记录当前节点的位置
private int pos;
private SonNode next;
public SonNode(int pos, SonNode next) {
this.pos = pos;
this.next = next;
}
}
public static class Node<T> {
T data;
// 记录第一个子节点
SonNode first;
public Node(T data) {
this.data = data;
this.first = null;
}
public String toString() {
if (first != null) {
return "TreeChild$Node[data=" + data + ", first=" + first.pos + "]";
} else {
return "TreeChild$Node[data=" + data + ", first=-1]";
}
}
}
private final int DEFAULT_TREE_SIZE = 100;
private int treeSize = 0;
// 使用一个Node[]数组来记录该树里的所有节点
private Node<E>[] nodes;
// 记录节点数
private int nodeNums;
// 以指定根节点创建树
public TreeChild(E data) {
treeSize = DEFAULT_TREE_SIZE;
nodes = new Node[treeSize];
nodes[0] = new Node<E>(data);
nodeNums++;
}
// 以指定根节点、指定treeSize创建树
public TreeChild(E data, int treeSize) {
this.treeSize = treeSize;
nodes = new Node[treeSize];
nodes[0] = new Node<E>(data);
nodeNums++;
}
// 为指定节点添加子节点
public void addNode(E data, Node parent) {
for (int i = 0; i < treeSize; i++) {
// 找到数组中第一个为null的元素，该元素保存新节点
if (nodes[i] == null) {
// 创建新节点，并用指定数组元素保存它
nodes[i] = new Node(data);
if (parent.first == null) {
parent.first = new SonNode(i, null);
} else {
SonNode next = parent.first;
while (next.next != null) {
next = next.next;
}
next.next = new SonNode(i, null);
}
nodeNums++;
return;
}
}
throw new RuntimeException("该树已满，无法添加新节点");
}
// 判断树是否为空
public boolean empty() {
// 根结点是否为null
return nodes[0] == null;
}
// 返回根节点
public Node<E> root() {
// 返回根节点
return nodes[0];
}
// 返回指定节点（非叶子节点）的所有子节点
public List<Node<E>> children(Node parent) {
List<Node<E>> list = new ArrayList<Node<E>>();
// 获取parent节点的第一个子节点
SonNode next = parent.first;
// 沿着孩子链不断搜索下一个孩子节点
while (next != null) {
// 添加孩子链中的节点
list.add(nodes[next.pos]);
next = next.next;
}
return list;
}
// 返回指定节点（非叶子节点）的第index个子节点
public Node<E> child(Node parent, int index) {
// 获取parent节点的第一个子节点
SonNode next = parent.first;
// 沿着孩子链不断搜索下一个孩子节点
for (int i = 0; next != null; i++) {
if (index == i) {
return nodes[next.pos];
}
next = next.next;
}
return null;
}
// 返回该树的深度
public int deep() {
// 获取该树的深度
return deep(root());
}
// 这是一个递归方法：每棵子树的深度为其所有子树的最大深度 + 1
private int deep(Node node) {
if (node.first == null) {
return 1;
} else {
// 记录其所有子树的最大深度
int max = 0;
SonNode next = node.first;
// 沿着孩子链不断搜索下一个孩子节点
while (next != null) {
// 获取以其子节点为根的子树的深度
int tmp = deep(nodes[next.pos]);
if (tmp > max) {
max = tmp;
}
next = next.next;
}
// 最后，返回其所有子树的最大深度 + 1
return max + 1;
}
}
// 返回包含指定值得节点
public int pos(Node node) {
for (int i = 0; i < treeSize; i++) {
// 找到指定节点
if (nodes[i] == node) {
return i;
}
}
return -1;
}
}
|
测试类：
|
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
|
package com.ietree.basic.datastructure.tree;
import java.util.List;
/**
* Created by ietree
* 2017/4/30
*/
public class TreeChildTest {
public static void main(String[] args) {
TreeChild<String> tp = new TreeChild<String>("root");
TreeChild.Node root = tp.root();
System.out.println(root);
tp.addNode("节点1", root);
tp.addNode("节点2", root);
tp.addNode("节点3", root);
System.out.println("添加子节点后的根结点：" + root);
System.out.println("此树的深度：" + tp.deep());
// 获取根节点的所有子节点
List<TreeChild.Node<String>> nodes = tp.children(root);
System.out.println("根节点的第一个子节点：" + nodes.get(0));
// 为根节点的第一个子节点新增一个子节点
tp.addNode("节点4", nodes.get(0));
System.out.println("此树第一个子节点：" + nodes.get(0));
System.out.println("此树的深度：" + tp.deep());
}
}
|
程序输出：
TreeChild$Node[data=root, first=-1]
添加子节点后的根结点：TreeChild$Node[data=root, first=1]
此树的深度：2
根节点的第一个子节点：TreeChild$Node[data=节点1, first=-1]
此树第一个子节点：TreeChild$Node[data=节点1, first=4]
此树的深度：3
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：http://www.cnblogs.com/Dylansuns/p/6791270.html