（JAVA）开始熟悉 “二叉树” 的数据结构

1. 二叉树入门

​ 符号表的增删查改操作，随着元素个数N的增多，其耗时也是线性增多的。时间复杂度都是O(n)，为了提高运算效率，下面将学习 树 这种数据结构

1.1 树的基本定义

​ 树是我们计算机中非常重要的一种数据结构，同时使用树这种数据结构，可以描述现实生活中的很多事务，例如家谱、单位的组织架构等等

​ 树是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像是一颗倒挂的树，也就是说它是根朝上，而叶是朝下的

• 树具有以下特点：
  1. 每个节点有零个或多个子节点
  2. 没有父节点的节点为根节点
  3. 每一个非根节点只有一个父节点
  4. 每个节点及其后代节点整体上可以看作是一棵树，称为当前节点的父节点的一个子树。

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实现思想：

1. 找到被删除的节点
2. 找到被删除节点右子数的最小节点
3. 删除右子数中的最小节点
4. 让被删除节点的左子树成为最小节点的左子树，让被删除节点的右子数成为最小节点的右子树
5. 让被删除节点的父节点指向最小节点

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 二叉树的基础遍历

很多情况下，我们可能需要像遍历数组一样，遍历树，从而拿到数中存储的每一个元素，由于树状结构和线性结构不一样，它没有办法从头开始依次向后遍历，所以存在如何遍历，也就是按照什么样的搜索路径进行遍历的问题。

我们把树简单的画作上图中的样子，由一个根节点，一个左子数，一个右子树组成，那么按照根节点什么时候被访问，我们可以把二叉树的遍历分为以下三种方式：

1. 前序遍历：

   先访问根节点，如何再访问左子树，最后访问右子树

2. 中序遍历：

   先访问左子树，中间访问根节点，最后访问右子树

3. 后续遍历：

   先访问左子树，再访问右子树，最后访问根节点

如果我们分别对下面的树使用三种遍历方式进行遍历，得到结果如下：

2.6.1 前序遍历

我们在4.4中创建的树上，添加前序遍历的API：

方法	说明
public Queue preErgodic()	使用前序遍历，获取整个树中的所有键
public void preErgodic(Node x,Queue keys)	使用前序遍历，把指定树x中的所有键放入到keys队列中

实现过程中，我们通过前序遍历，把每个节点的键取出，放入到队列中返回即可

2.6.1.1实现步骤

1. 把当前节点的key放入到队列中
2. 找到当前节点的左子树，如果不为空，递归遍历左子树
3. 找到当前节点的右子树，如果不为空，递归遍历右子树

2.6.2 中序遍历

我们在4.4中创建的树上，添加中序遍历的API：

方法	说明
public Queue midErgodic()	使用中序遍历，获取整个树中的所有键
public void midErgodic(Node x,Queue keys)	使用中序遍历，把指定树x中的所有键放入到keys队列中

2.6.2.1实现步骤

1. 找到当前节点的左子树，如果不为空，递归遍历左子树
2. 把当前节点的key放入到队列中
3. 找到当前节点的右子树，如果不为空，递归遍历右子树

2.6.3 后序遍历

我们在4.4中创建的树上，添加后序遍历的API：

方法	说明
public Queue afterErgodic()	使用后序遍历，获取整个树中的所有键
public void afterErgodic(Node x,Queue keys)	使用后序遍历，把指定树x中的所有键放入到keys队列中

2.6.2.1实现步骤

1. 找到当前节点的左子树，如果不为空，递归遍历左子树
2. 找到当前节点的右子树，如果不为空，递归遍历右子树
3. 把当前节点的key放入到队列中

2.7 二叉树的层序遍历

所谓的层序遍历，就是从根节点（第一层）开始，依次往下，获取每一层的所有节点的值，有二叉树如下：

那么层序遍历的结果是：EBGADFHC

我们在4.4中创建的树上，添加层序遍历的API：

方法	说明
public Queue layerErgodic()	使用层序遍历，获取整个数中的所有键

2.7.1 实现步骤

1. 创建队列，存储每一层的节点
2. 使用循环从队列中弹出一个节点
   1. 获取当前节点的key
   2. 如果当前节点的左子节点不为空，则把左子节点放入到队列中
   3. 如果当前节点的右子节点不为空，则把右子节点放入到队列中

2.8 二叉树的最大深度

需求：

给定一棵树，请计算树的最大深度（树的最远叶子节点的最长路径上的节点数）；

上面这棵树的最大深度为4

实现：

在原有API的基础上添加如下API求最大深度：

方法	说明
public int maxDepth()	计算整个树的最大深度
private int maxDepth(Node x)	计算指 定树x的最大深度

实现步骤：

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

3. 折纸问题

需求:

请把一段纸条竖着放在桌子上，如何从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。

如果纸条的下边向上方连续对着2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。

• 给定一个输入参数N，代表纸条都从下边向上方连续对着N次，请从上到下打印所有折痕的方向
• 例如：N=1时，打印：down；N=2时，打印：down down up

如图：粉色为正面，黑色为背面。向粉色面折一次代表down，向黑色面折一次代表up

分析：

​ 我们把对着后的纸张翻过来，让粉色朝下，这时把第一次对着产生的折痕看作是根节点，那第二次对着产生的下折痕就是该节点的左子节点，而第二次对着产生的折痕就是该节点的右子节点，这样我们就可以使用数据结构来描述对着后产生的折痕。

• 这棵树有这样的特点：
  1. 根节点为下折痕
  2. 每一个节点的左子节点为下折痕
  3. 每一个节点的右子节点为上折痕

实现步骤：

1. 定义节点类
2. 构建深度为N的折痕树
3. 使用中序遍历，打印出数中所有节点的内容

构建深度为N的折痕树：

1. 第一次对折，只有一条折痕，创建根节点
2. 如果不是第一次对着，则使用队列保存根节点
3. 循环遍历队列
   1. 从队列中弹出一个节点
   2. 如果这个节点的左子节点不为空，则把这个左子节点添加到队列中
   3. 如果这个节点的右子节点不为空，则把这个右子节点添加到队列中
   4. 判断当前节点的左子节点和右子节点都不为空，如果是，则需要为当前节点创建一个值为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;}
}