二叉树（从建树、遍历到存储）Java

目录

一、二叉树的定义1.特别二叉树（1）斜树（2）满二叉树（3）完全二叉树

二、二叉树的遍历1.前序遍历（递归+非递归）2.中序遍历（递归+非递归）3.后序遍历（递归+非递归）4.层次遍历代码图解

三、二叉树的建立1.前序遍历数组创建二叉树代码

四、二叉树的存储1.用一维数组存储2.代码

五、完整代码写在最后

一、二叉树的定义

特别学究的话我们就不说了， 因为我喜欢看图说话。二叉树的结构就是一个父节点挂一个或者两个子节点。 而且我们要注意到，在左右子节点不为空的情况下，若左子节点小于它的父节点，且右子节点大于它的父节点，那是二叉排序树，不是二叉树。在上网查资料的时候有时会看到一些人将其弄混了。

1.特别二叉树

大部分情况下二叉树都是一个父节点挂一到两个子节点的，但有三种情况比较特殊，它们有专属的名称，分别是斜树、满二叉树、完全二叉树。

（1）斜树

所有的节点都是左节点，称为左斜树。

所有的节点都是右节点，成为右斜树。

（2）满二叉树

曾经看一本小说的时候，里面有个境界叫“天境大圆满”，与满二叉树类似，一听这个名字就知道是什么意思了。

满二叉树就是只要有节点生孩子，就必须生俩，而且同辈分的其他节点都必须跟着生两个孩子！就是这么圆满！

下面两个图都是满二叉树：

（3）完全二叉树

我们一般用按层次标号的方法来判断，一个二叉树是否是完全二叉树。

比如我们遇到图二、图三、图四的二叉树要判断是否是完全二叉树，我可以将其补全为满二叉树，如图一。 只有图四中的每一个节点的编号和满二叉树中相同位置的节点编号相同，所以图四是完全二叉树。 图二是因为编号为6、7、8.、9的节点在满二叉树中的编号是8、9、10、11,所以不是；图三是因为编号为10的节点在满二叉树中的编号是11，所以不是。

二、二叉树的遍历

这块内容是二叉树最核心的部分。学习遍历不但可以遍历二叉树中的节点，而且可以（1）用前、中、后序遍历数组创建二叉树；（2）用一维数组存储二叉树。

1.前序遍历（递归+非递归）

二叉树前序遍历Java.

2.中序遍历（递归+非递归）

二叉树中序遍历Java.

3.后序遍历（递归+非递归）

二叉树后序遍历Java.

4.层次遍历

代码

public void levelOrder() {

if (root == null) {

return;

}

//把LinkedList作为队列使用

LinkedList q = new LinkedList();

q.addFirst(root);

Node current;

while (!q.isEmpty()) {

current = q.removeLast();

System.out.print(current.data + " -> ");

if (current.left != null)

q.addFirst(current.left);

if (current.right != null)

q.addFirst(current.right);

}

}

图解

初始。 图一：

图二：

图三：

图四：

图五：

图六：

图七：

打印顺序为：ABCDEFGHIJ

三、二叉树的建立

我们要建立如下图所示的二叉树（图一），为了确定每个节点是否有左右儿子，我们对其进行扩展，变成图二的样子。

图一：

图二：

1.前序遍历数组创建二叉树

要建立上面图二的二叉树，则前序遍历数组为：

Integer[] arr = { 1, 2, null, 4, null, null, 3, 5, null, null, null };

代码

前序遍历数组创建二叉树代码：

public Node CreateTree(Integer[] c) {

Integer var = c[size++];

if (var == null) {

return null;

}

//创建根节点

Node node = new Node(var);

//构造左子树

node.left = CreateTree(c);

//构造右子树

node.right = CreateTree(c);

//返回根节点

return node;

}

请对比前序遍历代码：

public void preOrderRecur(Node root) {

if (root == null) {

return;

}

System.out.print(root.data + " -> ");

preOrderRecur(root.left);

preOrderRecur(root.right);

}

注意： （1）我们可以发现两者的原理是相同的。只不过在原本打印节点的地方改为创建节点。 （2）其中的Node类是我自己写的节点类，文章最后有完整代码。

所以如果认真阅读过二叉树前序遍历Java这篇文章的话，对于使用前序遍历数组创建二叉树的代码也不难理解。

四、二叉树的存储

这里我们主要谈一谈用顺序存储结构来存储二叉树，也是面试过程中可能问到的问题。

1.用一维数组存储

即用一维数组存储二叉树中的节点，并且节点的存储位置，也就是数组的下标要能体现节点之间的逻辑关系，比如父节点与儿子节点的关系，左右兄弟节点的关系等。

先来看看完全二叉树的顺序存储。

将这个二叉树存入数组中，应为下图所示：

对于一般的二叉树，用一维数组进行存储的时候，我们选择将其补全为完全二叉树的形式，只不过，把不存在的节点设置为一个特殊字符#，或者直接为null。 最极端的，如果是一个右斜树。 我们可以看到为了存储三个节点，我们要分配7个节点大小的空间，这显然是对存储空间的浪费。同时也说明了完全二叉树虽然定义上麻烦，规则很多，也是有它的优越性的。

2.代码

从上面的几个例子可以看出，用一维数组存储二叉树的核心算法其实就是层次遍历，只不过多了一个存入数组的过程。

从理论上说是这么简单，但是把非完全二叉树补全为完全二叉树再存储到一维数组中的算法我实在没想出来，如果看到这里的你已经有了自己的想法，请不吝赐教，万分感谢！

完全二叉树存储一维数组还是可以实现的

public Integer[] toArray() {

//先用LinkedList存储一下，最后再转化为数组

LinkedList list = new LinkedList();

if (root == null) {

return null;

}

LinkedList q = new LinkedList();

q.addFirst(root);

Node current;

while (!q.isEmpty()) {

current = q.removeLast();

list.add(current.data);

if (current.left != null)

q.addFirst(current.left);

if (current.right != null)

q.addFirst(current.right);

}

//将list转化为数组

Integer[] arr = new Integer[list.size()];

arr = list.toArray(arr);

return arr;

}

对比层次遍历的代码：

public void levelOrder() {

if (root == null) {

return;

}

//把LinkedList作为队列使用

LinkedList q = new LinkedList();

q.addFirst(root);

Node current;

while (!q.isEmpty()) {

current = q.removeLast();

System.out.print(current.data + " -> ");

if (current.left != null)

q.addFirst(current.left);

if (current.right != null)

q.addFirst(current.right);

}

}

只是多了用LinkedList存储再转化为数组的代码。

五、完整代码

这是我在学习过程中模仿Java集合类写的一个二叉树类，以Integer类为例，如果引入泛型的话，所有类都可以，欢迎大家指导。

BinaryTree类：

import java.util.LinkedList;

public class BinaryTree {

//节点个数

private int size;

//根节点

private Node root;

public BinaryTree() {

}

//有参构造方法

public BinaryTree(Integer[] c) {

this();

root = addAllRecur(c);

}

//前序遍历数据创建二叉树（递归）

private Node addAllRecur(Integer[] c) {

Integer var = c[size++];

if (var == null) {

return null;

}

Node node = new Node(var);

node.left = addAllRecur(c);

node.right = addAllRecur(c);

return node;

}

//前序遍历，递归

public void preOrderRecur() {

preOrderRecur(root);

}

public void preOrderRecur(Node root) {

if (root == null) {

return;

}

System.out.print(root.data + " -> ");

preOrderRecur(root.left);

preOrderRecur(root.right);

}

//前序遍历，非递归

public void preOrder() {

if (root == null)

return;

Node current;

LinkedList s = new LinkedList();

s.addFirst(root);

while (!s.isEmpty()) {

current = s.removeFirst();

System.out.print(current.data + " -> ");

if (current.right != null)

s.addFirst(current.right);

if (current.left != null)

s.addFirst(current.left);

}

}

//中序遍历，递归

public void inOrderRecur() {

inOrderRecur(root);

}

public void inOrderRecur(Node root) {

if (root == null) {

return;

}

inOrderRecur(root.left);

System.out.print(root.data + " -> ");

inOrderRecur(root.right);

}

//中序遍历，非递归

public void inOrder() {

Node current = root;

LinkedList s = new LinkedList();

while (current != null || !s.isEmpty()) {

while (current != null) {

s.addFirst(current);

current = current.left;

}

if (!s.isEmpty()) {

current = s.removeFirst();

System.out.print(current.data + " -> ");

current = current.right;

}

}

}

//后序遍历，遍历

public void postOrderRecur() {

postOrderRecur(root);

}

public void postOrderRecur(Node root) {

if (root == null) {

return;

}

postOrderRecur(root.left);

postOrderRecur(root.right);

System.out.print(root.data + " -> ");

}

//后序遍历，非遍历

public void postOrder() {

Node current = root;

LinkedList s1 = new LinkedList();

LinkedList s2 = new LinkedList();

while (current != null || !s1.isEmpty()) {

while (current != null) {

//s1起到前序遍历非递归2的作用

s1.addFirst(current);

s2.addFirst(current);

current = current.right;

}

if (!s1.isEmpty()) {

current = s1.removeFirst();

current = current.left;

}

}

while (!s2.isEmpty()) {

System.out.print(s2.removeFirst().data + " -> ");

}

}

//层次遍历

public void levelOrder() {

if (root == null) {

return;

}

LinkedList q = new LinkedList();

q.addFirst(root);

Node current;

while (!q.isEmpty()) {

current = q.removeLast();

System.out.print(current.data + " -> ");

if (current.left != null)

q.addFirst(current.left);

if (current.right != null)

q.addFirst(current.right);

}

}

/* 用一维数组存储

* 目前只支持完全二叉树

*/

public Integer[] toArray() {

//先用LinkedList存储一下，最后再转化为数组

LinkedList list = new LinkedList();

if (root == null) {

return null;

}

LinkedList q = new LinkedList();

q.addFirst(root);

Node current;

while (!q.isEmpty()) {

current = q.removeLast();

list.add(current.data);

if (current.left != null)

q.addFirst(current.left);

if (current.right != null)

q.addFirst(current.right);

}

//将list转化为数组

Integer[] arr = new Integer[list.size()];

arr = list.toArray(arr);

return arr;

}

private static class Node {

Integer data;

Node right;

Node left;

Node(Integer data) {

this.data = data;

}

}

}

测试类：

public class Demo {

public static void main(String[] args) {

//前序遍历建树

Integer[] arr = { 1, 2, 4, null, null, 5, null, null, 3, null, null };

BinaryTree tree = new BinaryTree(arr);

System.out.print("前序遍历(递归)：");

tree.preOrderRecur();

System.out.println();

System.out.print("前序遍历(非递归)：");

tree.preOrder();

System.out.println();

System.out.print("中序遍历(递归)：");

tree.inOrderRecur();

System.out.println();

System.out.print("中序遍历(非递归)：");

tree.inOrder();

System.out.println();

System.out.print("后序遍历（递归）：");

tree.postOrderRecur();

System.out.println();

System.out.print("后序遍历(非递归)：");

tree.postOrder();

System.out.println();

System.out.print("层次遍历：");

tree.levelOrder();

System.out.println();

System.out.print("一维数组存储：");

Integer[] array = tree.toArray();

for (int i = 0; i < array.length; i++) {

System.out.print(array[i] + ",");

}

}

}

结果：

前序遍历(递归)：1 -> 2 -> 4 -> 5 -> 3 ->

前序遍历(非递归)：1 -> 2 -> 4 -> 5 -> 3 ->

中序遍历(递归)：4 -> 2 -> 5 -> 1 -> 3 ->

中序遍历(非递归)：4 -> 2 -> 5 -> 1 -> 3 ->

后序遍历（递归）：4 -> 5 -> 2 -> 3 -> 1 ->

后序遍历(非递归)：4 -> 5 -> 2 -> 3 -> 1 ->

层次遍历：1 -> 2 -> 3 -> 4 -> 5 ->

一维数组存储：1,2,3,4,5,

写在最后

分享这篇文章的目的不仅仅是与大家一起讨论二叉树的使用，更大的目的是为了对付JDK1.8中的HashMap，其中用到了红黑树这种数据结构。

所以接下来还会分享其他类型二叉树的使用，总的路线为：二叉树——>二叉排序树（二叉搜索树）——>红黑树，再加一个哈希表（hash table）喜欢的话可以持续关注哦。

系列上的第二篇文章——二叉排序树已经更新，有兴趣的可以看看来来来！热乎的二叉排序树（搜索树）查找、增加、删除操作.

第三篇文章——红黑树已经更新，有兴趣的点击数据结构：关于红黑树你所要了解的.