你每天都那么努力,忍受了那么多的寂寞和痛苦。可我也没见你有多优秀。
当我还是一个年轻男孩的时候画的一张关于树的画。
当你第一次学习编码时,大部分人都是将数组作为主要数据结构来学习。
之后,你将会学习到哈希表。如果你是计算机专业的,你肯定需要选修一门数据结构的课程。上课时,你又会学习到链表,队列和栈等数据结构。这些都被统称为线性的数据结构,因为它们在逻辑上都有起点和终点。
当你开始学习树和图的数据结构时,你会觉得它是如此的混乱。因为它的存储方式不是线性的,它们都有自己特定的方式存储数据。
这篇文章帮助你更好的理解树形数据结构并尽可能的帮你解决你的疑问。本章我们将学到
当学习编程时,我们更容易理解线性的数据结构而不是树和图的数据结构。
树是众所周知的非线性数据结构。它们不以线性方式存储数据。他们按层次组织数据。
我们所说的层次组织到底是是什么呢?
想象一下我们的家谱:祖父母,父母,子女,兄弟姐妹等等,我们通常按层次结构组织家谱。
我的家庭族谱
上图是我的家谱。tossico,akikazu,hitomi和takemi是我的祖父母。
Toshiaki 和 Juliana 是我的父母。
TK 、Yuji 、Bruno 和 Kaio 是我父母的孩子(我和我的兄弟们)。
另一个层次结构的例子是企业的组织结构。
公司的结构也是是一个层次结构的例子
在 HTML 中,文档对象模型(DOM)是树形结构的。
文档对象模型(dom)
HTML 标签包含其他的标签。我们有一个 head 标签和 body 标签。这些标签包含特点的元素。head 标签中有 meta 和 title 标签。body 标签中有在用户界面展示的标签,如 h1 、a 、li 等等。
树(tree
)是被称为结点(node
)的实体的集合。结点通过边(edge
)连接。每个结点都包含值或数据(value/date
),并且每结节点可能有也可能没有子结点。
树的首结点叫根结点(即root
结点)。如果这个根结点和其他结点所连接,那么根结点是父结点(parent node
,与根结点连接的是子结点(child node
)。
所有的结点都通过边(edge
)连接。它是树中很重要得一个概念,因为它负责管理节点之间的关系。
叶子结点(leaves
)是树末端,它们没有子结点。像真正的大树一样,我们可以看到树上有根、枝干和树叶。
树的高度(height
)和深度(depth
)
现在我们来讨论一个特殊的树类型。我们把它叫作二叉树。
“在计算机科学领域,二叉树是一种树形数据结构,它的每个节点最多有两个孩子,被叫作左孩子和右孩” — Wikipedia
当我们要实现二叉树时,我们需要牢记的第一件事是它是一个结点集合。每个结点都有三个属性:value
,left_child和right_child
。
那么我们怎么才能实现一个有这三个属性的简单二叉树呢?
我们来实现一个二叉树的例子
/**
* Created on 2018/4/16.
*
* @author zlf
* @since 1.0
*/
public class BinaryTree {
public BinaryTree left; //左节点
public BinaryTree right; //右节点
public String data; //树的内容
public BinaryTree() {
}
/**
* 构造方法
*
* @param data
* @param left
* @param right
*/
public BinaryTree(String data, BinaryTree left, BinaryTree right) {
this.left = left;
this.right = right;
this.data = data;
}
/**
* 构造方法
*
* @param data
*/
public BinaryTree(String data) {
this(data, null, null);
}
好,这就是我们的二叉树类
当我们实例化一个对象时,我们把值(点的相关数据)作为参数传递给类。看上面类的左孩子结点和右孩子结点。两个都被赋值为null。
为什么?
因为当我们创建节点时,它还没有孩子,只有结点数据。
代码测试
/**
* 构建树
*/
public static void testCreate() {
BinaryTree node = new BinaryTree("a");
System.out.println("【node data】:" + node.getData());
System.out.println("【node left data】:" + (node.left==null?"null":node.left.getData()));
System.out.println("【node right data】:" + (node.right==null?"null":node.right.getData()));
}
输出:
【node data】:a
【node left data】:null
【node right data】:null
我们可以将字符串’a’作为参数传给二叉树结点。如果将值、左孩子结点、右孩子结节点输出的话,我们就可以看到这个值了。
下面开始插入部分的操作。那么我们需要做些什么工作呢?
有两个要求:
图形如下:
下面是插入的代码:
/**
* 插入节点 ,如果当前的节点没有左节点,我们就创建一个新节点,然后将其设置为当前节点的左节点。
*
* @param node
* @param value
*/
public static void insertLeft(BinaryTree node, String value) {
if (node != null) {
if (node.left == null) {
node.setLeft(new BinaryTree(value));
}
} else {
BinaryTree newNode = new BinaryTree(value);
newNode.left = node.left;
node.left = newNode;
}
}
再次强调,如果当前结点没有左结点,我们就创建一个新结点,并将其置为当前结点的左结点。否则,就将新结点放在左结点的位置,再将原左结点置为新左结点的左结点。
同样,我们编写插入右结点的代码
/**
* 同插入左结点
* @param node
* @param value
*/
public static void insertRight(BinaryTree node, String value) {
if (node != null) {
if (node.right == null) {
node.setRight(new BinaryTree(value));
}
} else {
BinaryTree newNode = new BinaryTree(value);
newNode.right = node.right;
node.right = newNode;
}
}
但是这还不算完成。我们得测试一下。
我们来构造一个像下面这样的树:
下面是这棵树的实现代码:
/**
* 测试插入结点
*/
public static void testInsert() {
BinaryTree node_a = new BinaryTree("a");
node_a.insertLeft(node_a, "b");
node_a.insertRight(node_a, "c");
BinaryTree node_b = node_a.left;
node_b.insertRight(node_b, "d");
BinaryTree node_c = node_a.right;
node_c.insertLeft(node_c, "e");
node_c.insertRight(node_c, "f");
BinaryTree node_d = node_b.right;
BinaryTree node_e = node_c.left;
BinaryTree node_f = node_c.right;
System.out.println("【node_a data】:" + node_a.getData());
System.out.println("【node_b data】:" + node_b.getData());
System.out.println("【node_c data】:" + node_c.getData());
System.out.println("【node_d data】:" + node_d.getData());
System.out.println("【node_e data】:" + node_e.getData());
System.out.println("【node_f data】:" + node_f.getData());
}
输出:
【node_a data】:a
【node_b data】:b
【node_c data】:c
【node_d data】:d
【node_e data】:e
【node_f data】:f
插入已经结束
现在,我们来考虑一下树的遍历。
树的遍历有两种选择,深度优先搜索(DFS)和广度优先搜索(BFS)。
DFS是用来遍历或搜索树数据结构的算法。从根节点开始,在回溯之前沿着每一个分支尽可能远的探索。 — Wikipedia
BFS是用来遍历或搜索树数据结构的算法。从根节点开始,在探索下一层邻居节点前,首先探索同一层的邻居节点。 — Wikipedia
下面,我们来深入了解每一种遍历算法。
DFS 在回溯和搜索其他路径之前找到一条到叶节点的路径。让我们看看这种类型的遍历的示例。
输出结果为: 1–2–3–4–5–6–7
为什么?
让我们分解一下:
当我们深入到叶结点时回溯,这就被称为 DFS 算法。
既然我们对这种遍历算法已经熟悉了,我们将讨论下 DFS 的类型:前序、中序和后序。
这和我们在上述示例中的作法基本类似。
/**
* 前序遍历
*
* @param node
*/
public static void preOrder(BinaryTree node) {
if (node != null) {
System.out.println(node.data);
if (node.left != null) {
node.left.preOrder(node.left);
}
if (node.right != null) {
node.right.preOrder(node.right);
}
}
}
示例中此树的中序算法的结果是3–2–4–1–6–5–7。
左结点优先,之后是中间,最后是右结点。
代码实现:
/**
* 中序遍历
*
* @param node
*/
public static void inOrder(BinaryTree node) {
if (node != null) {
if (node.left != null) {
node.left.inOrder(node.left);
}
System.out.println(node.data);
if (node.right != null) {
node.right.inOrder(node.right);
}
}
}
以此树为例的后序算法的结果为 3–4–2–6–7–5–1 。
左结点优先,之后是右结点,根结点的最后。
代码实现:
/**
* 后序遍历
*
* @param node
*/
public static void postOrder(BinaryTree node) {
if (node != null) {
if (node.left != null) {
node.left.postOrder(node.left);
}
if (node.right != null) {
node.right.postOrder(node.right);
}
System.out.println(node.data);
}
}
BFS是一层层逐渐深入的遍历算法
下面这个例子是用来帮我们更好的解释该算法。
我们来一层一层的遍历这棵树。本例中,就是1-2-5-3-4-6-7.
代码实现:
/**
* 广度排序
*
* @param node
*/
public static void bfsOrder(BinaryTree node) {
if (node != null) {
Queue<BinaryTree> queue = new ArrayDeque<BinaryTree>();
queue.add(node);
while (!queue.isEmpty()) {
BinaryTree current_node = queue.poll();
System.out.println(current_node.data);
if (current_node.left != null) {
queue.add(current_node.left);
}
if (current_node.right != null) {
queue.add(current_node.right);
}
}
}
}
为了实现BFS算法,我们需要用到一个数据结构,那就是队列。
队列具体是用来干什么的呢?
请看下面解释。
二叉搜索树有时候被称为二叉有序树或二叉排序树,二叉搜索树的值存储在有序的顺序中,因此,查找表和其他的操作可以使用折半查找原理。——Wikipedia
二叉搜索树中的一个重要性质是,二叉搜索树中一个节点的值大于其左结点,但是小于其右结点
代码实现二叉树搜索
现在想像一下我们有一棵空树,我们想将几个节点添加到这棵空树中,这几个结点的值为:50、76、21、4、32、100、64、52。
首先我们需要知道的是,50是不是这棵树的根结点。
现在我们开始一个一个的插入结点
你注意到这里的模式了吗?
让我们把它分解。
代码实现:
/**
* 插入树
*
* @param node
* @param value
*/
public void insertNode(BinaryTree node, Integer value) {
if (node != null) {
if (value <= Integer.valueOf(node.data) && node.left != null) {
node.left.insertNode(node.left, value);
} else if (value <= Integer.valueOf(node.data)) {
node.left = new BinaryTree(String.valueOf(value));
} else if (value > Integer.valueOf(node.data) && node.right != null) {
node.right.insertNode(node.right, value);
} else {
node.right = new BinaryTree(String.valueOf(value));
}
}
}
看起来很简单。
该算法的强大之处是其递归部分,即第9行和第13行。这两行代码均调用 insertNode 方法,并分别为其左结点和右结点使用它。第11行和第15行则在子结点处插入新结点。
我们现在要构建的算法是关于搜索的。对于给定的值(整数),我们会搜索出我们的二叉查找树有或者没有这个值。
需要注意的一个重要事项是我们如何定义树的插入算法。 首先我们有根结点。所有左子的节点值都比根结点小。所有右子树的节点值都比根结点大。
让我们看一个例子。
假设我们有这棵树。
现在我们想知道是否有一个结点的值为52。
让我们把它分解。
代码实现:
/**
* 查找节点是否存在
*
* @param node
* @param value
* @return
*/
public boolean findNode(BinaryTree node, Integer value) {
if (node != null) {
if (value < Integer.valueOf(node.data) && node.left != null) {
return node.left.findNode(node.left, value);
}
if (value > Integer.valueOf(node.data) && node.right != null) {
return node.right.findNode(node.right, value);
}
return value == Integer.valueOf(node.data);
}
return false;
}
代码分析:
删除是一个更复杂的算法,因为我们需要处理不同的情况。对于给定值,我们需要删除具有此值的结点。想象一下这个节点的以下场景:它没有孩子,有一个孩子,或者有两个孩子。
# |50| |50|
# / \ / \
# |30| |70| (DELETE 20) ---> |30| |70|
# / \ \
# |20| |40| |40|
如果要删除的结点没有子结点,我们简单地删除它。该算法不需要重组树。
# |50| |50|
# / \ / \
# |30| |70| (DELETE 30) ---> |20| |70|
# /
# |20|
在这种情况下,我们的算法需要使节点的父节点指向子结点。如果节点是左孩子,则使其父结点指向其子结点。如果结点是右孩子,则使其父结点指向其子结点。
# |50| |50|
# / \ / \
# |30| |70| (DELETE 30) ---> |40| |70|
# / \ /
# |20| |40|
当节点有两个孩子,则需要从该节点的右孩子开始,找到具有最小值的结点。我们将把具有最小值的这个节点置于被删除的节点的位置。
代码实现:
/**
* 删除节点
* @param node
* @param value
* @param parent
* @return
*/
public boolean removeNode(BinaryTree node, Integer value, BinaryTree parent) {
if (node != null) {
if (value < Integer.valueOf(node.data) && node.left != null) {
return node.left.removeNode(node.left, value, node);
} else if (value < Integer.valueOf(node.data)) {
return false;
} else if (value > Integer.valueOf(node.data) && node.right != null) {
return node.right.removeNode(node.right, value, node);
} else if (value > Integer.valueOf(node.data)) {
return false;
} else {
if (node.left == null && node.right == null && node == parent.left) {
parent.left = null;
node.clearNode(node);
} else if (node.left == null && node.right == null && node == parent.right) {
parent.right = null;
node.clearNode(node);
} else if (node.left != null && node.right == null && node == parent.left) {
parent.left = node.left;
node.clearNode(node);
} else if (node.left != null && node.right == null && node == parent.right) {
parent.right = node.left;
node.clearNode(node);
} else if (node.right != null && node.left == null && node == parent.left) {
parent.left = node.right;
node.clearNode(node);
} else if (node.right != null && node.left == null && node == parent.right) {
parent.right = node.right;
node.clearNode(node);
} else {
node.data=String.valueOf(node.right.findMinValue(node.right));
node.right.removeNode(node.right,Integer.valueOf(node.right.data),node);
}
return true;
}
}
return false;
}
value
和 parent
。我们想找到值等于该 value
的 node
,并且该 node
的父节点对于删除该 node
是至关重要的。true
。否则返回 false
。value
的 node
。如果该 value
小于 current node
值,我们进入左子树,递归处理(当且仅当,current node
有左孩子)。如果该值大于,则进入右子树。递归处理。true
。从第11行到第31行,我们处理了这些情况。所以直接返回 true
,这就够了。/**
* 清空n节点
*
* @param node
*/
public void clearNode(BinaryTree node) {
node.data = null;
node.left = null;
node.right = null;
}
/**
* 查找树中最小值
*/
public Integer findMinValue(BinaryTree node) {
if (node != null) {
if (node.left != null) {
return node.left.findMinValue(node.left);
} else {
return Integer.valueOf(node.data);
}
}
return null;
}
原文链接:Everything you need to know about tree data structures
从我的 github 中下载,【译】数据结构中关于树的一切(java版)