二叉树入门

一、树的基本定义二、树的相关术语三、二叉树的基本定义四、二叉查找树的创建五、二叉树的基础遍历六、二叉树的层序遍历七、二叉树的应用最大深度问题折纸问题 总结

---

一、树的基本定义

树是计算机中非常重要的一种数据结构，同时可以用来描述生活中很多事物，比如家谱、单位的组织架构等等。 树是由n个有限结点组合起来具有层次关系的集合。（n>=1）

树的特点：

没有父结点的结点称为根节点；每个结点有零个或多个子结点；每个非根结点只有一个父结点；每个当前结点及其后代结点整体上也可以看做一棵树，称作当前结点的父结点的一个子树。

二、树的相关术语

结点的度：

一个结点含有的子树的个数；

叶结点： 度为0的结点，也称为终端结点；

分支结点：

度不为0的结点，也称为非终端结点；

结点的层次：

从根结点开始，根结点为1层，根结点的后继层次为2层，以此类推；

结点的层序编号：

将树中的结点，按照从上层到下层，同层从左到右的顺序排成一个线性序列，把他们编成连续的自然数；

树的度：

树中结点的度的最大值；

树的高度（深度）：

树中结点的最大层次；

森林：

m(m>=0)个互不相交的树的集合。删掉一棵非空树的根结点就成了一片森林；给森林增加一个公共的根结点，森林就变成了一棵树。

孩子结点：

一个结点的直接后继结点称为该结点的孩子结点；

双亲结点（父节点）：

一个结点的直接前驱称为该结点的双亲结点；

兄弟节点：

同一个双亲结点的孩子结点间互称为兄弟结点；

三、二叉树的基本定义

二叉树：度不超过2的树（每个结点最多有两个子结点） 满二叉树：每一层的结点数都达到最大值的二叉树

四、二叉查找树的创建

观察发现，二叉树是由一个一个结点及其之间的关系组成的，按照面向对象的思想，用一个结点类来描述二叉树：

1.4.1 二叉树的结点类

结点类的API代码实现：

private class Node<Key,Value>{ //存储键 public Key key; //存储值 private Value value; //记录左子结点 public Node left; //记录右子结点 public Node right; public Node(Key key, Value value, Node left, Node right) { this.key = key; this.value = value; this.left = left; this.right = right; } }

1.4.2 二叉查找树实现

插入方法put实现思想：

如果当前树还没有结点，把新结点作为根结点使用；如果当前树已有结点，从根结点开始寻找： 2.1 如果新结点的key小于当前结点的key，则继续找当前结点的左子节点； 2.2 如果新结点的key大于当前结点的key，则继续找当前结点的右子节点； 2.3 如果新结点的key等于当前结点的key，则表示该结点已存在，替换当前结点的value值即可。

查询方法get实现思想：

从根结点开始：

如果要查询的key小于当前结点的key，则继续找当前结点的左子节点；如果要查询的key大于当前结点的key，则继续找当前结点的右子节点；如果要查询的key等于当前结点的key，则返回当前结点的value。

删除方法delete实现思想：

找到被删除结点；找到被删除结点右子树中的最小结点minNode删除右子树中的最小结点让被删除结点的左子树成为最小结点minNode的左子树，让被删除结点的右子树称为最小结点minNode的右子树让被删除结点的父节点指向最小结点minNode

五、二叉树的基础遍历

可以将树简化为下图所示，由一个根结点、左子树、右子树组成。

三种遍历方式：

前序遍历； 先访问根结点，然后再访问左子树，最后访问右子树中序遍历； 先访问左子树，中间访问根节点，最后访问右子树后序遍历； 先访问左子树，再访问右子树，最后访问根节点

分别对下列树进行三种遍历，得到的结果为：

六、二叉树的层序遍历

什么是层序遍历？层序遍历就是从根结点（第一层）开始，依次向下，获取每一层所有结点的值。 层序遍历的结果为：EBGADFHC

层序遍历的实现步骤：

创建队列，存储每一层的结点；使用循环，从队列中弹出一个结点： 2.1 获取当前结点的key； 2.2 如果当前结点的左子结点不为空，则把左子结点放入到队列中； 2.3 如果当前结点的右子结点不为空，则把右子结点放入到队列中；

七、二叉树的应用

最大深度问题

需求：给定一棵树，求树的最大深度（树的根结点到最远叶子结点的路径上的结点数）； 上面这棵树的最大深度为4。

实现步骤：（使用递归的方式）

如果根结点为空，则最大深度为0；计算左子树的最大深度；计算右子树的最大深度；当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1

折纸问题

需求： 请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时 折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2 次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。

给定一个输入参数N，代表纸条都从下边向上方连续对折N次，请从上到下打印所有折痕的方向 例如：N=1时，打印： down；N=2时，打印： down down up 如图所示： 分析： 我们把对折后的纸张翻过来，让粉色朝下，这时把第一次对折产生的折痕看做是根结点，那第二次对折产生的下折痕就是该结点的左子结点，而第二次对折产生的上折痕就是该结点的右子结点，这样我们就可以使用树型数据结构来描述对折后产生的折痕。 这棵树有这样的特点：

根结点为下折痕；每一个结点的左子结点为下折痕；每一个结点的右子结点为上折痕；

实现步骤：

定义结点类构建深度为N的折痕树；使用中序遍历，打印出树中所有结点的内容；

构建深度为N的折痕树：

第一次对折，只有一条折痕，创建根结点；如果不是第一次对折，则使用队列保存根结点；循环遍历队列： 3.1 从队列中拿出一个结点； 3.2 如果这个结点的左子结点不为空，则把这个左子结点添加到队列中； 3.3 如果这个结点的右子结点不为空，则把这个右子结点添加到队列中； 3.4 判断当前结点的左子结点和右子结点都不为空，如果是，则需要为当前结点创建一个值为down的左子结点，一个值为up的右子结点。

---

总结

本文仅仅简单的介绍了树的定义和相关术语，以及二叉树的创建、遍历方法和应用。欢迎各位大佬指正！