学习理论知识时，我们都是学习的二叉树。但是在实际场景中，却都是N叉树。此处记录一下N叉树的构建与遍历。
本文源码meethigher/java-tree-examples: 树相关的知识，示例代码使用Java实现
一、二叉树
二叉树：每个节点最多有两个子节点（左子节点和右子节点）。结构如下
1
2
3
4
5
| 1
/ \
2 3
/ \ / \
4 5 6 7
|
遍历方式有三种
- 前序遍历（根左右）：由根开始
- 中序遍历（左根右）：根放中间
- 后序遍历（左右根）：由根结束
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
| public class Tree {
public static class TreeNode {
public int value;
public TreeNode left;
public TreeNode right;
public TreeNode(int value, TreeNode left, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
public TreeNode(int value) {
this.value = value;
}
}
public static void preOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.value+" ");
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
public static void inOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
inOrderTraversal(node.left);
System.out.print(node.value+" ");
inOrderTraversal(node.right);
}
public static void postOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
postOrderTraversal(node.left);
postOrderTraversal(node.right);
System.out.print(node.value+" ");
}
public static void main(String[] args) {
TreeNode root = new Tree.TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
System.out.println("前序遍历结果：");
preOrderTraversal(root);
System.out.println();
System.out.println("中序遍历结果：");
inOrderTraversal(root);
System.out.println();
System.out.println("后序遍历结果：");
postOrderTraversal(root);
System.out.println();
}
}
|
二、N叉树（通用树）
多叉树：每个节点可以有任意数量的子节点。
公司的组织机构，就是一个N叉树。
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
| 公司
├─亚太区
│ ├─中国区
│ │ ├─上海分公司
│ │ │ ├─产品设计部
│ │ │ ├─人力资源部
│ │ │ ├─客服部
│ │ │ ├─市场部
│ │ │ ├─技术支持部
│ │ │ ├─数据分析部
│ │ │ ├─研发部
│ │ │ ├─财务部
│ │ │ ├─销售部
│ │ │ └─项目管理部
│ │ ├─北京分公司
│ │ │ ├─产品设计部
│ │ │ │ ├─产品设计小组A
│ │ │ │ └─产品设计小组B
│ │ │ ├─人力资源部
│ │ │ │ ├─员工关系小组
│ │ │ │ ├─培训小组
│ │ │ │ ├─招聘小组
│ │ │ │ └─绩效管理小组
│ │ │ ├─客服部
│ │ │ │ ├─客服团队A
│ │ │ │ └─客服团队B
│ │ │ ├─市场部
│ │ │ │ ├─品牌推广小组
│ │ │ │ ├─市场调研小组
│ │ │ │ └─广告策划小组
│ │ │ ├─技术支持部
│ │ │ │ ├─技术支持小组A
│ │ │ │ └─技术支持小组B
│ │ │ ├─数据分析部
│ │ │ │ ├─数据分析小组A
│ │ │ │ └─数据分析小组B
│ │ │ ├─研发部
│ │ │ │ ├─测试小组
│ │ │ │ ├─硬件开发小组
│ │ │ │ └─软件开发小组
│ │ │ ├─财务部
│ │ │ │ ├─会计小组
│ │ │ │ ├─审计小组
│ │ │ │ └─财务分析小组
│ │ │ ├─销售部
│ │ │ │ ├─销售团队A
│ │ │ │ ├─销售团队B
│ │ │ │ └─销售团队C
│ │ │ └─项目管理部
│ │ │ ├─项目管理小组A
│ │ │ └─项目管理小组B
│ │ └─深圳分公司
│ │ ├─产品设计部
│ │ ├─人力资源部
│ │ ├─客服部
│ │ ├─市场部
│ │ ├─技术支持部
│ │ ├─数据分析部
│ │ ├─研发部
│ │ ├─财务部
│ │ ├─销售部
│ │ └─项目管理部
│ └─日本区
│ ├─东京分公司
│ └─大阪分公司
├─北美区
│ ├─加拿大区
│ │ ├─多伦多分公司
│ │ └─温哥华分公司
│ └─美国区
│ ├─洛杉矶分公司
│ └─纽约分公司
└─欧洲区
├─德国区
│ ├─慕尼黑分公司
│ └─柏林分公司
└─法国区
├─巴黎分公司
└─里昂分公司
|
N叉树的遍历有两种
- 深度优先（Depth-First Search），使用递归或者栈
- 广度优先（Breadth-First Search），使用队列
二叉树的前序、中序、后序遍历，本质上就是N叉树的深度优先遍历而已。
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
132
133
| import java.io.Serializable;
import java.util.*;
public class Tree {
public static class Org implements Serializable {
private String code;
private String name;
private String parentCode;
private String parentName;
private Integer orgNum;
private List<Org> children = new ArrayList<>();
public Integer getOrgNum() {
return orgNum;
}
public void setOrgNum(Integer orgNum) {
this.orgNum = orgNum;
}
public String getCode() {
return code;
}
public void setCode(String code) {
this.code = code;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getParentCode() {
return parentCode;
}
public void setParentCode(String parentCode) {
this.parentCode = parentCode;
}
public String getParentName() {
return parentName;
}
public void setParentName(String parentName) {
this.parentName = parentName;
}
public List<Org> getChildren() {
return children;
}
public void setChildren(List<Org> children) {
this.children = children;
}
}
public static void depthFirstTraversalTree(Org tree) {
if (tree.getChildren() == null || tree.getChildren().isEmpty()) {
tree.setOrgNum(0);
return;
}
int sum = tree.getChildren().size();
for (Org child : tree.getChildren()) {
depthFirstTraversalTree(child);
sum += child.getOrgNum();
}
tree.setOrgNum(sum);
}
public static void breadthFirstTraversal(Org root) {
if (root == null) {
return;
}
Queue<Org> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Org current = queue.poll();
System.out.println("Code: " + current.getCode() + ", Name: " + current.getName());
if (current.getChildren() != null) {
for (Org child : current.getChildren()) {
queue.add(child);
}
}
}
}
public static Org buildTree(List<Org> list) {
Org tree = new Org();
tree.setCode("root");
tree.setName("root");
Map<String, Org> codeToOrgMap = new HashMap<>();
for (Org org : list) {
codeToOrgMap.put(org.getCode(), org);
}
for (Org org : list) {
if (org.getParentCode() == null || org.getCode().equals(org.getParentCode())) {
tree.getChildren().add(org);
} else {
Org t = codeToOrgMap.get(org.getParentCode());
if (t != null) {
t.getChildren().add(org);
}
}
}
return tree;
}
}
|
