Java数据结构学习之二叉树

一、背景知识：树（Tree）

在之前的笔记中，我们介绍的链表、栈、队列、数组和字符串都是以线性结构来组织数据的。本篇笔记要介绍的树采用的是树状结构，这是一种非线性的数据组织形式。

树结构由节点和边构成，且不存在环。我们曾在线性表型的数据结构中介绍过循环链表和循环队列，这两种数据结构使得存储容器中的元素形成一个闭环，具体可参看“数据结构学习笔记”系列的相关博文，链接贴在下面：

链表：https://www.jb51.net/article/215278.htm

队列：https://www.jb51.net/article/211502.htm

树状结构与线性结构最重要的区别在于：树只能有分叉，不能有闭环。如下图所示：

树结构不允许有环其实是树的层级性决定的。树结构中最顶端的结点是根节点， 根节点即整棵树的顶级父节点。除了根节点只有子节点，最底层的节点只有父节点，其余各层的节点都是上层节点的子节点、下层节点的父节点。也就是说，树中的数据只与其上下层的数据有关，同层数据间不能有直接联系，这也就是树结构不能有环的原因。

树层级的多少往往被描述为树的高度(height)，由于我们是从上往下观察树结构的，因此也被描述为树的深度(depth)。上面图示中两颗树的深度都是3.

二、何为二叉树（Binray Tree）

2.1 二叉树的概念与结构

二叉树顾名思义，即每个父节点最多只有两个分叉的树，这是数据结构领域使用频率极高的一种树结构，这与我们常常用二元对立的观点认识世界的思维习惯有关。

二叉树的结构不仅具有层级性，还具有递归性，一个父节点连接左子节点和右子节点，而左右子节点又可以作为父节点再各自连接两个子节点，以此类推。因此二叉树是一种层次嵌套的数据结构，除了根节点外，树中任意一个父节点都能作为一棵子树的根，位于上层父节点左侧的子树被称为左子树，位于右侧的子树被称为右子树。

二叉树体现了人们用二元思维认识自然的方式。笔者的本行是语言学，语言学界主流的对句法结构的分析方法就是类似于二叉树的二分法。拿汉语的句法结构来说，有主谓、述宾、定中、状中、述补等基本的结构类型。句法结构具有层次嵌套和递归的特点，同时也有对语序的要求，即句法二叉树中的左右节点的位置并不是任意的。这种分析方法语言学上被称为层次分析法，如果我们用该方法分析句子“文程同学热爱编程”，传统图示和句法树图示分别如下：

2.2 满二叉树与完全二叉树

二叉树中有两个特殊的结构类型：满二叉树和完全二叉树。满二叉树的结构特点是除了最后一层外，所有层级的节点都有两个子节点；完全二叉树的结构特点是除了最后两层外，所有层级的节点都有两个子节点，倒数第二层的子节点（即最后一层节点）全部靠左排列。如下图所示：

由此可见，满二叉树一定是完全二叉树，完全二叉树可满可不满。这两种二叉树体现了我们采用树状结构存储数据时，对于空间利用率的追求。比如我们设计一个深度为n的二叉树，那么整个二叉树能容纳的最大节点数为2^n-1，满二叉树就是达到了最大节点数，用足了二叉树的容量。完全二叉树除了n层没有子节点，除n-1层外各层父节点都充分利用了自己拥有子节点的名额，也算是尽可能做到了对空间的充分利用。

为了更好地理解完全二叉树的空间利用率，我们看一个非完全二叉树的例子，如下图所示：

上图是一个深度为4的非完全二叉树，前3层的父节点都预留了左右两个子节点的位置，然而第二层的第2个结点只使用了右子节点的空间，浪费了左子节点的空间。如果二叉树的深度很深，其中很多层级的父节点都存在浪费子节点“名额”的现象，那么会造成相当大的空间资源的浪费，二叉树也失去了“二叉”的意义。但是完全二叉树最多浪费倒数第二层父节点的子节点名额， 整体上能够保证较高的空间利用率。

2.3 二叉树的三种遍历方式

二叉树的形状整体上构成一个三角形，最小的二叉树由一个位于中间的父节点和位于左右两侧的子节点构成，这导致遍历访问一棵二叉树的所有节点有三种顺序：前序遍历（Preorder Traversal , VLR）、中序遍历（Inorder Traversal , LDR）和后序遍历（Inorder Traversal , LRD）。

无论哪种遍历方式，二叉树都是从上到下、从左到右遍历的，即从父节点层到子节点层、从左子树到右子树。2.1解释了二叉树的递归性，遍历二叉树时采用的也是递归(recursion)的方式。对于整棵树或某一子树，都是从根开始，先遍历其左子树，再遍历其右子树；分别遍历左右子树时，同样是从根开始，从左向右遍历；以此类推，直到遍历到最后一个右子节点。

如果我们以打印节点数据的方式来表示对节点的访问，那么前序、中序和后序的区别就在于打印节点的时机不同。前序遍历的操作顺序是打印节点在遍历左子树和遍历右子树之前，中序遍历的操作顺序是打印节点在遍历左子树和遍历右子树之间，后序遍历的操作顺序是打印节点在遍历左子树和遍历右子树之后。子树遍历的过程是递归实现的。 

如果我们想遍历2.1演示的“文程同学热爱编程”的句法二叉树，那么用三种遍历方法得到的遍历结果分别如下：

三、二叉树及其遍历的简单实现（Java）

我们用Java语言实现“文程同学热爱编程”这个句子对应的句法二叉树，设计思路是：将同层级的父节点（二叉树及其各子树的根节点）存入数组中，数组中存入的是结点，包括数据和左右指针，左右指针分别指向位于下一层节点的左右子节点，如果没有子节点则指针为空指针。

用数组的好处是，可以通过节点所在的索引建立上下层级父节点和子节点的指针联系。假设父节点在它所在的层级数组中的索引为i，那么左子节点在它所在层级数组中的索引为(i+1)*2-2，右子节点的索引为(i+1)*2-1，即左子节点的索引＋1。

遍历默认从整棵二叉树的根节点开始，通过方法的重写实现默认参数的效果。

准备工作1：MyBinaryTree.java，创建一个二叉树的类

package com.notes.data_structure6;

import com.notes.data_structure6.NumberOfNodesException;

public class MyBinaryTree {
// 树的根结点
private Node[] root;
// 树的深度（当前层级数）
private int depth;
// 将每一层所有的 结点 都存储在数组中，结点数是 2的 层数 次幂
private Node[] currentLevel;

public MyBinaryTree(String data) {
Node[] rootArray = new Node[] {new Node(data)};
this.root = rootArray;
this.currentLevel = rootArray;
}

// 定义一个结点类
private class Node{
private String data; // 数据
private Node leftNext; // 左指针
private Node rightNext; // 右指针

// 构造方法：Node实例化时传入数据
public Node(String data) {
this.data = data;
}
}

// 向树中增加一层结点
public void add(String[] datas) throws NumberOfNodesException {
// 层级数增加1
depth++;
// 新增 层级 的最大结点数
int nodeNum = numberOfNextNodes();
// 如果传入的 数据数 与 当前层级 最大结点数 不符，抛出异常
if(datas.length != nodeNum) {
throw new NumberOfNodesException("第"+depth+"层最大父节点数为"+nodeNum);
}
// 将传入的 数据数组 转换为 结点数组
Node[] newLevel = new Node[nodeNum];
// 当前 层级的 结点数量（新增层级的父）
int nodeNum2 = (int) Math.pow(2, depth-1);
// 让每一个结点都与上层 父结点 建立连接
for(int i=0;i<nodeNum2;i++) {
// 让父结点 的左指针 指向 左子结点
int leftIndex = (i+1)*2-2; // 计算左子结点对应的新层级数组的索引
currentLevel[i].leftNext = new Node(datas[leftIndex]); // 建立指针指向
newLevel[leftIndex] = currentLevel[i].leftNext; // 将结点加入新层级结点数组
// 让父结点 的右指针 指向 右子结点
int rightIndex = leftIndex+1; // 计算右子结点对应的新层级数组的索引
currentLevel[i].rightNext = new Node(datas[rightIndex]); // 建立指针指向
newLevel[rightIndex] = currentLevel[i].rightNext; // 将结点加入新层级结点数组
}
// 让新增层级的数组成为当前层级的数组
currentLevel =  newLevel;
}

// 前序遍历所有结点
public void preTraversal(Node node) {
if(node==null) {
return;
}
System.out.print(node.data+" ");
preTraversal(node.leftNext);
preTraversal(node.rightNext);
}

// 重写 前序遍历 方法，让遍历从 根结点 开始
public void preTraversal() {
Node node = root[0];
if(node==null) {
return;
}
// 递归时调用带参数的方法
System.out.print(node.data+" ");
preTraversal(node.leftNext);
preTraversal(node.rightNext);
}

// 中序遍历所有结点
public void midTraversal(Node node) {
if(node==null) {
return;
}
midTraversal(node.leftNext);
System.out.print(node.data+" ");
midTraversal(node.rightNext);
}

// 重写中序遍历 方法，让遍历从 根结点 开始
public void midTraversal() {
Node node = root[0];
if(node==null) {
return;
}
// 递归时调用带参数的方法
midTraversal(node.leftNext);
System.out.print(node.data+" ");
midTraversal(node.rightNext);
}

// 后序遍历所有结点
public void posTraversal(Node node) {
if(node==null) {
return;
}
posTraversal(node.leftNext);
posTraversal(node.rightNext);
System.out.print(node.data+" ");
}

// 重写后序遍历 方法，让遍历从 根结点 开始
public void posTraversal() {
Node node = root[0];
if(node==null) {
return;
}
// 递归时调用带参数的方法
posTraversal(node.leftNext);
posTraversal(node.rightNext);
System.out.print(node.data+" ");
}

// 查看 新增层级 的最大结点数
public int numberOfNextNodes() {
return (int) Math.pow(2,depth);
}

// 查看 树 的深度（层级数）
public int getDepth() {
return depth;
}

}

准备工作2：NumberOfNodesException.java，为add()方法创建一个自定义异常，如果传入的数据数与当前层级最大结点数不符，则抛出该异常（如果二叉树不满，在数组的相应位置传入null）。

package com.notes.data_structure6;

public class NumberOfNodesException extends Exception{
public NumberOfNodesException(String message) {
super(message);
}
}

句法二叉树的实现及其遍历：TreeDemo.java

package com.notes.data_structure6;

public class TreeDemo {
public static void main(String[] args) throws NumberOfNodesException {
// 实例化二叉树类，并且传入根节点的数据
MyBinaryTree tree = new MyBinaryTree("句子");
// 加入第一层节点的数据
tree.add(new String[] {"主语","谓语"});
// 加入第二层节点的数据
tree.add(new String[] {"定语","中心语","述语","宾语"});

// 前序遍历
tree.preTraversal(); // 句子 主语 定语 中心语 谓语 述语 宾语
System.out.println();
// 中序遍历
tree.midTraversal(); // 定语 主语 中心语 句子 述语 谓语 宾语
System.out.println();
// 后序遍历
tree.posTraversal(); // 定语 中心语 主语 述语 宾语 谓语 句子
}
}

来源：https://blog.csdn.net/weixin_45370422/article/details/117859121