一、树
树与线性表、栈、队列等线性结构不同，树是一种非线性结构。
一棵树只有一个根节点，如果一棵树有了多个根节点，那它已经不再是一棵树了，而是多棵树的集合，也被称为森林。
二、树的父节点表示法
树中除根节点之外每个节点都有一个父节点，为了记录树中节点与节点之间的父子关系，可以为每个节点增加一个parent域，用以记录该节点的父节点。
1 package com.ietree.basic.datastructure.tree;
2
3 import java.util.ArrayList;
4 import java.util.List;
5
6 /**
7 * Created by ietree
8 * 2017/4/30
9 */
10 public class TreeParent<E> {
11
12 public static class Node<T> {
13
14 T data;
15 // 保存其父节点的位置
16 int parent;
17
18 public Node() {
19
20 }
21
22 public Node(T data) {
23 this.data = data;
24 }
25
26 public Node(T data, int parent) {
27 this.data = data;
28 this.parent = parent;
29 }
30
31 public String toString() {
32 return "TreeParent$Node[data=" + data + ", parent=" + parent + "]";
33 }
34
35 }
36
37 private final int DEFAULT_TREE_SIZE = 100;
38 private int treeSize = 0;
39 // 使用一个Node[]数组来记录该树里的所有节点
40 private Node<E>[] nodes;
41 // 记录树的节点数
42 private int nodeNums;
43
44 // 以指定节点创建树
45 public TreeParent(E data) {
46 treeSize = DEFAULT_TREE_SIZE;
47 nodes = new Node[treeSize];
48 nodes[0] = new Node<E>(data, -1);
49 nodeNums++;
50 }
51
52 // 以指定根节点、指定treeSize创建树
53 public TreeParent(E data, int treeSize) {
54 this.treeSize = treeSize;
55 nodes = new Node[treeSize];
56 nodes[0] = new Node<E>(data, -1);
57 nodeNums++;
58 }
59
60 // 为指定节点添加子节点
61 public void addNode(E data, Node parent) {
62 for (int i = 0; i < treeSize; i++) {
63 // 找到数组中第一个为null的元素，该元素保存新节点
64 if (nodes[i] == null) {
65 // 创建新节点，并用指定的数组元素保存它
66 nodes[i] = new Node(data, pos(parent));
67 nodeNums++;
68 return;
69 }
70 }
71 throw new RuntimeException("该树已满，无法添加新节点");
72 }
73
74 // 判断树是否为空
75 public boolean empty() {
76 // 根结点是否为null
77 return nodes[0] == null;
78 }
79
80 // 返回根节点
81 public Node<E> root() {
82 // 返回根节点
83 return nodes[0];
84 }
85
86 // 返回指定节点（非根结点）的父节点
87 public Node<E> parent(Node node) {
88 // 每个节点的parent记录了其父节点的位置
89 return nodes[node.parent];
90 }
91
92 // 返回指定节点（非叶子节点）的所有子节点
93 public List<Node<E>> children(Node parent) {
94 List<Node<E>> list = new ArrayList<Node<E>>();
95 for (int i = 0; i < treeSize; i++) {
96 // 如果当前节点的父节点的位置等于parent节点的位置
97 if (nodes[i] != null && nodes[i].parent == pos(parent)) {
98 list.add(nodes[i]);
99 }
100 }
101 return list;
102 }
103
104 // 返回该树的深度
105 public int deep() {
106 // 用于记录节点的最大深度
107 int max = 0;
108 for (int i = 0; i < treeSize && nodes[i] != null; i++) {
109 // 初始化本节点的深度
110 int def = 1;
111 // m 记录当前节点的父节点的位置
112 int m = nodes[i].parent;
113 // 如果其父节点存在
114 while (m != -1 && nodes[m] != null) {
115 // 向上继续搜索父节点
116 m = nodes[m].parent;
117 def++;
118 }
119 if (max < def) {
120 max = def;
121 }
122 }
123 return max;
124 }
125
126 // 返回包含指定值的节点
127 public int pos(Node node) {
128 for (int i = 0; i < treeSize; i++) {
129 // 找到指定节点
130 if (nodes[i] == node) {
131 return i;
132 }
133 }
134 return -1;
135 }
136
137 }
测试类：
1 package com.ietree.basic.datastructure.tree;
2
3 import java.util.List;
4
5 /**
6 * Created by ietree
7 * 2017/4/30
8 */
9 public class treeParentTest {
10
11 public static void main(String[] args) {
12
13 TreeParent<String> tp = new TreeParent<String>("root");
14 TreeParent.Node root = tp.root();
15 System.out.println(root);
16 tp.addNode("节点1", root);
17 System.out.println("此树的深度：" + tp.deep());
18 tp.addNode("节点2", root);
19 // 获取根节点的所有子节点
20 List<TreeParent.Node<String>> nodes = tp.children(root);
21 System.out.println("根节点的第一个子节点：" + nodes.get(0));
22 // 为根节点的第一个子节点新增一个子节点
23 tp.addNode("节点3", nodes.get(0));
24 System.out.println("此树的深度：" + tp.deep());
25
26 }
27 }
程序输出：
TreeParent$Node[data=root, parent=-1]
此树的深度：2
根节点的第一个子节点：TreeParent$Node[data=节点1, parent=0]
此树的深度：3
三、子节点链表示法
让父节点记住它的所有子节点。
1 package com.ietree.basic.datastructure.tree;
2
3 import java.util.ArrayList;
4 import java.util.List;
5
6 /**
7 * Created by ietree
8 * 2017/4/30
9 */
10 public class TreeChild<E> {
11
12 private static class SonNode {
13 // 记录当前节点的位置
14 private int pos;
15 private SonNode next;
16
17 public SonNode(int pos, SonNode next) {
18 this.pos = pos;
19 this.next = next;
20 }
21 }
22
23 public static class Node<T> {
24 T data;
25 // 记录第一个子节点
26 SonNode first;
27
28 public Node(T data) {
29 this.data = data;
30 this.first = null;
31 }
32
33 public String toString() {
34 if (first != null) {
35 return "TreeChild$Node[data=" + data + ", first=" + first.pos + "]";
36 } else {
37 return "TreeChild$Node[data=" + data + ", first=-1]";
38 }
39 }
40 }
41
42 private final int DEFAULT_TREE_SIZE = 100;
43 private int treeSize = 0;
44 // 使用一个Node[]数组来记录该树里的所有节点
45 private Node<E>[] nodes;
46 // 记录节点数
47 private int nodeNums;
48
49 // 以指定根节点创建树
50 public TreeChild(E data) {
51 treeSize = DEFAULT_TREE_SIZE;
52 nodes = new Node[treeSize];
53 nodes[0] = new Node<E>(data);
54 nodeNums++;
55 }
56
57 // 以指定根节点、指定treeSize创建树
58 public TreeChild(E data, int treeSize) {
59 this.treeSize = treeSize;
60 nodes = new Node[treeSize];
61 nodes[0] = new Node<E>(data);
62 nodeNums++;
63 }
64
65 // 为指定节点添加子节点
66 public void addNode(E data, Node parent) {
67 for (int i = 0; i < treeSize; i++) {
68 // 找到数组中第一个为null的元素，该元素保存新节点
69 if (nodes[i] == null) {
70 // 创建新节点，并用指定数组元素保存它
71 nodes[i] = new Node(data);
72 if (parent.first == null) {
73 parent.first = new SonNode(i, null);
74 } else {
75 SonNode next = parent.first;
76 while (next.next != null) {
77 next = next.next;
78 }
79 next.next = new SonNode(i, null);
80 }
81 nodeNums++;
82 return;
83 }
84 }
85 throw new RuntimeException("该树已满，无法添加新节点");
86 }
87
88 // 判断树是否为空
89 public boolean empty() {
90 // 根结点是否为null
91 return nodes[0] == null;
92 }
93
94 // 返回根节点
95 public Node<E> root() {
96 // 返回根节点
97 return nodes[0];
98 }
99
100 // 返回指定节点（非叶子节点）的所有子节点
101 public List<Node<E>> children(Node parent) {
102
103 List<Node<E>> list = new ArrayList<Node<E>>();
104 // 获取parent节点的第一个子节点
105 SonNode next = parent.first;
106 // 沿着孩子链不断搜索下一个孩子节点
107 while (next != null) {
108 // 添加孩子链中的节点
109 list.add(nodes[next.pos]);
110 next = next.next;
111 }
112 return list;
113
114 }
115
116 // 返回指定节点（非叶子节点）的第index个子节点
117 public Node<E> child(Node parent, int index) {
118 // 获取parent节点的第一个子节点
119 SonNode next = parent.first;
120 // 沿着孩子链不断搜索下一个孩子节点
121 for (int i = 0; next != null; i++) {
122 if (index == i) {
123 return nodes[next.pos];
124 }
125 next = next.next;
126 }
127 return null;
128 }
129
130 // 返回该树的深度
131 public int deep() {
132 // 获取该树的深度
133 return deep(root());
134 }
135
136 // 这是一个递归方法：每棵子树的深度为其所有子树的最大深度 + 1
137 private int deep(Node node) {
138 if (node.first == null) {
139 return 1;
140 } else {
141 // 记录其所有子树的最大深度
142 int max = 0;
143 SonNode next = node.first;
144 // 沿着孩子链不断搜索下一个孩子节点
145 while (next != null) {
146 // 获取以其子节点为根的子树的深度
147 int tmp = deep(nodes[next.pos]);
148 if (tmp > max) {
149 max = tmp;
150 }
151 next = next.next;
152 }
153 // 最后，返回其所有子树的最大深度 + 1
154 return max + 1;
155 }
156 }
157
158 // 返回包含指定值得节点
159 public int pos(Node node) {
160 for (int i = 0; i < treeSize; i++) {
161 // 找到指定节点
162 if (nodes[i] == node) {
163 return i;
164 }
165 }
166 return -1;
167 }
168
169 }
测试类：
1 package com.ietree.basic.datastructure.tree;
2
3 import java.util.List;
4
5 /**
6 * Created by ietree
7 * 2017/4/30
8 */
9 public class TreeChildTest {
10
11 public static void main(String[] args) {
12
13 TreeChild<String> tp = new TreeChild<String>("root");
14 TreeChild.Node root = tp.root();
15 System.out.println(root);
16 tp.addNode("节点1", root);
17 tp.addNode("节点2", root);
18 tp.addNode("节点3", root);
19 System.out.println("添加子节点后的根结点：" + root);
20 System.out.println("此树的深度：" + tp.deep());
21 // 获取根节点的所有子节点
22 List<TreeChild.Node<String>> nodes = tp.children(root);
23 System.out.println("根节点的第一个子节点：" + nodes.get(0));
24 // 为根节点的第一个子节点新增一个子节点
25 tp.addNode("节点4", nodes.get(0));
26 System.out.println("此树第一个子节点：" + nodes.get(0));
27 System.out.println("此树的深度：" + tp.deep());
28
29 }
30
31 }
程序输出：
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