（JAVA）开始熟悉 “二叉树” 的数据结构
1. 二叉树入门
符号表的增删查改操作，随着元素个数N的增多，其耗时也是线性增多的。时间复杂度都是O(n)，为了提高运算效率，下面将学习 树 这种数据结构
1.1 树的基本定义
树是我们计算机中非常重要的一种数据结构，同时使用树这种数据结构，可以描述现实生活中的很多事务，例如家谱、单位的组织架构等等
树是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像是一颗倒挂的树，也就是说它是根朝上，而叶是朝下的
- 树具有以下特点：
- 每个节点有零个或多个子节点
- 没有父节点的节点为根节点
- 每一个非根节点只有一个父节点
- 每个节点及其后代节点整体上可以看作是一棵树，称为当前节点的父节点的一个子树。
1.2 树的相关术语
节点的度
- 一个节点含有的子树的个数称为该节点的度
叶节点
- 度为0的节点称为叶节点，也可以叫做终端节点
分支节点
- 度不为0的节点称为分支节点，也可以叫做非终端节点
节点的层次
- 从根节点开始，根节点的层次为1，根的直接后继层次为2，依次类推
节点的层序编号
- 将树种的节点，按照从上层到下层，同层从左到右的次序排成一个线性序列，把他们编成连续的自然数
树的度
- 树种所有节点的度的最大值
树的高度（深度）
- 树种节点的最大层次
森林
-
m(m>=0)个互不相交的树的集合，将一颗非空树的根节点删除，树就变成了一个森林；给森林增加一个统一的根节点，森林就变成了一棵树
孩子节点
- 一个节点的直接后继节点称为该节点的孩子节点
双亲节点（父节点）
- 一个节点的直接前驱称为该节点的双亲节点
兄弟节点
- 同一双亲节点的孩子节点间互称兄弟节点
1.3 二叉树的基本定义
二叉树就是度不超过2的树（每个节点最多有两个子节点）
满二叉树
- 一个二叉树，如果每一层的节点数都达到最大值，那么这个二叉树就是满二叉树
- 2^k-1
完全二叉树
- 叶节点只能出现在最下层和次下层，并且最下面一层的节点但都集中在该层最左边的若干位置的二叉树
2. 二叉查找树的创建
2.1 二叉树的节点类
根据对图的观察，我们发现二叉树其实就是由一个一个的节点及其之间的关系组成的，按照面向对象的思想，我们设计一个系欸但来描述系欸但那这个事物
| 类名 | Node<Key,Value> |
|---|---|
| 构造方法 | Node(Key key,Value value,Node left,Node right)：创建Node对象 |
| 成员变量 | 1. public Node left：记录左子节点 2. public Node right：记录右子节点 3. public Key key：存储键 4. public Value value：存储值 |
2.2 二叉查找树API设计
| 类名 | BinaryTree<Key extends Comparable,Value value> |
|---|---|
| 构造方法 | BinaryTree()：创建BinaryTree对象 |
| 成员变量 | 1. private Node root：记录根节点 2. private int N：记录树中元素的个数 |
| 成员方法 | 1. public void put(Key key,Value value)：向树种插入一个键值对 2. public Node put(Node x,Key key,Value value)：给指定树x上， |
2.3 二叉查找树的实现
2.3.1 插入方法put实现思想
- 如果当前树种没有任何一个节点，则直接把新节点当作根节点使用
- 如果当前树不为空，则从根节点开始：
- 如果新节点的key小于当前节点的key，则继续找当前节点的左子节点；
- 如果新节点的key大于当前节点的key，则继续找当前节点的右子节点；
- 如果新节点的key等于当前节点的key，则树种已经存在这样的节点，替换掉该节点的value值。
2.3.2 查找方法get的实现思想：
-
从根节点开始：
- 如果新节点的key小于当前节点的key，则继续找当前节点的左子节点；
- 如果新节点的key大于当前节点的key，则继续找当前节点的右子节点；
- 如果新节点的key等于当前节点的key，则数中返回当前节点的value
2.3.3 删除方法delete实现思想：
- 找到被删除的节点
- 找到被删除节点右子数的最小节点
- 删除右子数中的最小节点
- 让被删除节点的左子树成为最小节点的左子树，让被删除节点的右子数成为最小节点的右子树
- 让被删除节点的父节点指向最小节点
2.4 二叉查找树源码：
package com.renexdemo.tree;// 二叉查找树
public class BinaryTree<Key extends Comparable<Key> ,Value> {private Node root;// 根节点private int N;// 节点类private class Node{public Key key;public 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;}}public int size(){return N;}/*** 例如： key=1 value=张三 root=null （node1）* key=2 value=李四 root=node1（node2）：* node1——key=1，2，李四 node1.left = node2* tree —— 1_张三** key=3 value=王五 root=node1 root.right=node2** @param key* @param value*/// 向树中添加元素public void put(Key key, Value value){// node1，2，李四// node1，3，王五root = put(root, key, value);}// 向某个树添加元素public Node put(Node x,Key key, Value value){// 如果x为空if (x==null){N++;return new Node(key,value,null,null);}// 如果x不为空// 比较x节点的键和key的大小int cmp = key.compareTo(x.key);if (cmp>0){// x.right = null，2，李四// 如果子树的键要大于key，则继续找x节点的右子树x.right = put(x.right,key,value);// x.right —— node2// 经过回调重新赋予了子树节点// x.right（node2）：key=2 value=李四// 再次调用，直到找到子树为null，重新赋予该子树的节点键和值}else if (cmp<0){// 如果子树的键要小于key，则继续找x节点的左子树x.left = put(x.left,key,value);}else {// 如果子树的键要等于key，则替换valuex.value = value;}return x;}// 根据对应的key查找到对应的值public Value get(Key key){return get(root,key);}public Value get(Node x,Key key){// x为nullif (x==null){return null;}else {// x不为null// 比较键的大小int cmp = key.compareTo(x.key);if (cmp>0){// 如果子树的键要大于key，则继续找x节点的右子树return get(x.right,key);}else if (cmp<0){// 如果子树的键要小于key，则继续找x节点的左子树return get(x.left,key);}else {// 如果子树的键要等于key，则替换valuereturn x.value;}}}// 删除树种key对应的valuepublic void delete(Key key){delete(root,key);}public Node delete(Node x,Key key){// 1 找到被删除的节点if (x==null){// 1.1 x树为nullreturn null;}// 1.2 x树不为nullint cmp = key.compareTo(x.key);if (cmp>0){// 1.2.1 如果子树的键要大于key，则继续找x节点的右子树x.right = delete(x.right,key);}else if (cmp<0){// 1.2.2 如果子树的键要小于key，则继续找x节点的左子树x.left = delete(x.left,key);}else {// 2 删除x节点的键，完成真正的删除操作// 6 元素个数-1N--;// 2.1 找到右子数中最小的节点if (x.right == null){return x.left;}// 2.2 找到左子树中最大节点if (x.left == null){return x.right;}// 2.3 找到最小节点Node minNode = x.right;while (minNode.left != null){minNode = minNode.left;}// 2.4 删除右子数中最小的节点Node n = x.right;while (n.left != null){if (n.left.left==null){n.left = null;}else{n = n.left;}}// 3 让x节点的左子树成为minNode的左子树minNode.left = x.left;// 4 让x节点的右子树成为minNode的右子树minNode.right = x.right;// 5 让x节点的父节点指向minNodex = minNode;}return x;}// 查找整个树种最小的键public Key min(){return min(root).key;}// 在指定树中找出最小键所在的节点public Node min(Node x){if (x.left != null){return min(x.left);}else {return x;}}// 查找整个树种最大的键public Key max(){return min(root).key;}// 在指定树中找出最大键所在的节点public Node max(Node x){if (x.right != null){return min(x.right);}else {return x;}}}
2.5 二叉查找树其他便捷方法
2.5.1 查找二叉树中最小的键
在某些情况下，我们需要查找出树中存储所有元素的键的最小值。
| 方法 | 说明 |
|---|---|
| public Key min() | 找出树中最小的键 |
| public Node min(Node x) | 找出指定树x中，最小键所在的节点 |
2.5.2 查找二叉树中最大的键
在某些情况下，我们需要查找出树中存储所有元素的键的最小值。
| 方法 | 说明 |
|---|---|
| public Key max() | 找出树中最大的键 |
| public Node max(Node x) | 找出指定树x中，最大键所在的节点 |
2.6 二叉树的基础遍历
很多情况下，我们可能需要像遍历数组一样，遍历树，从而拿到数中存储的每一个元素，由于树状结构和线性结构不一样，它没有办法从头开始依次向后遍历，所以存在如何遍历，也就是按照什么样的搜索路径进行遍历的问题。
我们把树简单的画作上图中的样子，由一个根节点，一个左子数，一个右子树组成，那么按照根节点什么时候被访问，我们可以把二叉树的遍历分为以下三种方式：
-
前序遍历：
先访问根节点，如何再访问左子树，最后访问右子树
-
中序遍历：
先访问左子树，中间访问根节点，最后访问右子树
-
后续遍历：
先访问左子树，再访问右子树，最后访问根节点
如果我们分别对下面的树使用三种遍历方式进行遍历，得到结果如下：
2.6.1 前序遍历
我们在4.4中创建的树上，添加前序遍历的API：
| 方法 | 说明 |
|---|---|
| public Queue preErgodic() | 使用前序遍历，获取整个树中的所有键 |
| public void preErgodic(Node x,Queue keys) | 使用前序遍历，把指定树x中的所有键放入到keys队列中 |
实现过程中，我们通过前序遍历，把每个节点的键取出，放入到队列中返回即可
2.6.1.1实现步骤
- 把当前节点的key放入到队列中
- 找到当前节点的左子树，如果不为空，递归遍历左子树
- 找到当前节点的右子树，如果不为空，递归遍历右子树
2.6.2 中序遍历
我们在4.4中创建的树上，添加中序遍历的API：
| 方法 | 说明 |
|---|---|
| public Queue midErgodic() | 使用中序遍历，获取整个树中的所有键 |
| public void midErgodic(Node x,Queue keys) | 使用中序遍历，把指定树x中的所有键放入到keys队列中 |
2.6.2.1实现步骤
- 找到当前节点的左子树，如果不为空，递归遍历左子树
- 把当前节点的key放入到队列中
- 找到当前节点的右子树，如果不为空，递归遍历右子树
2.6.3 后序遍历
我们在4.4中创建的树上，添加后序遍历的API：
| 方法 | 说明 |
|---|---|
| public Queue afterErgodic() | 使用后序遍历，获取整个树中的所有键 |
| public void afterErgodic(Node x,Queue keys) | 使用后序遍历，把指定树x中的所有键放入到keys队列中 |
2.6.2.1实现步骤
- 找到当前节点的左子树，如果不为空，递归遍历左子树
- 找到当前节点的右子树，如果不为空，递归遍历右子树
- 把当前节点的key放入到队列中
2.7 二叉树的层序遍历
所谓的层序遍历，就是从根节点（第一层）开始，依次往下，获取每一层的所有节点的值，有二叉树如下：
那么层序遍历的结果是：EBGADFHC
我们在4.4中创建的树上，添加层序遍历的API：
| 方法 | 说明 |
|---|---|
| public Queue layerErgodic() | 使用层序遍历，获取整个数中的所有键 |
2.7.1 实现步骤
- 创建队列，存储每一层的节点
- 使用循环从队列中弹出一个节点
- 获取当前节点的key
- 如果当前节点的左子节点不为空，则把左子节点放入到队列中
- 如果当前节点的右子节点不为空，则把右子节点放入到队列中
2.8 二叉树的最大深度
需求：
给定一棵树，请计算树的最大深度（树的最远叶子节点的最长路径上的节点数）；
上面这棵树的最大深度为4
实现：
在原有API的基础上添加如下API求最大深度：
| 方法 | 说明 |
|---|---|
| public int maxDepth() | 计算整个树的最大深度 |
| private int maxDepth(Node x) | 计算指 定树x的最大深度 |
实现步骤：
- 如果根节点为空，则最大深度为0；
- 计算左子树的最大深度
- 计算右子树最大深度
- 当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1
3. 折纸问题
需求:
请把一段纸条竖着放在桌子上，如何从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。
如果纸条的下边向上方连续对着2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
- 给定一个输入参数N，代表纸条都从下边向上方连续对着N次，请从上到下打印所有折痕的方向
- 例如：N=1时，打印：down；N=2时，打印：down down up
如图：粉色为正面，黑色为背面。向粉色面折一次代表down，向黑色面折一次代表up
分析：
我们把对着后的纸张翻过来，让粉色朝下，这时把第一次对着产生的折痕看作是根节点，那第二次对着产生的下折痕就是该节点的左子节点，而第二次对着产生的折痕就是该节点的右子节点，这样我们就可以使用数据结构来描述对着后产生的折痕。
- 这棵树有这样的特点：
- 根节点为下折痕
- 每一个节点的左子节点为下折痕
- 每一个节点的右子节点为上折痕
实现步骤：
- 定义节点类
- 构建深度为N的折痕树
- 使用中序遍历，打印出数中所有节点的内容
构建深度为N的折痕树：
- 第一次对折，只有一条折痕，创建根节点
- 如果不是第一次对着，则使用队列保存根节点
- 循环遍历队列
- 从队列中弹出一个节点
- 如果这个节点的左子节点不为空，则把这个左子节点添加到队列中
- 如果这个节点的右子节点不为空，则把这个右子节点添加到队列中
- 判断当前节点的左子节点和右子节点都不为空，如果是，则需要为当前节点创建一个值为down的左子节点，一个值为up的右子节点
实现代码
/**
* 模拟对折过程，产生树
* @param n 对折次数
* @return
*/
public static Node<String> createTree(int n){// 定义根节点Node<String> root =null;for (int i = 0; i < n; i++) {// 1. 当前树为空if (i==0){root = new Node<>("down",null,null);continue;}// 2. 当前树不为空// 定义一个辅助队列，通过层序遍历思想找到叶子节点，给叶子节点添加子节点Queue<Node> queue = new Queue<>();queue.enqueue(root);// 3. 循环遍历队列while (!queue.isEmpty()){// 从队列中弹出节点Node<String> tmp = queue.dequeue();// 如果有左子节点，则把左子系欸但放入到队列中if (tmp.left != null){queue.enqueue(tmp.left);}// 如果有右子节点，则把左子系欸但放入到队列中if (tmp.right != null){queue.enqueue(tmp.right);}// 如果左右两个子节点都没有，那么该节点为叶子节点，只需要给该节点添加左子节点和右子节点if (tmp.right == null && tmp.left == null){tmp.left = new Node<String>("down",null,null);tmp.right = new Node<String>("up",null,null);}}}return root;
}// 打印树中的全部节点
public static void printTree(Node<String> root){// 使用中序遍历if (root==null){return;}// 打印左子树的每个节点if(root.left!=null){printTree(root.left);}// 打印当前节点System.out.print(root.item=" ");// 打印右子树的每个节点if(root.right!=null){printTree(root.right);}
}// 节点类
public static class Node<T>{public T item;public Node left;public Node right;public Node(T item, Node left, Node right) {this.item = item;this.left = left;this.right = right;}
}