【树】二叉树的设计、实现与遍历

一、树的基本概念与术语

树是数据元素之间具有次层关系的非线性的结构，树是由n(n≥0)个结点组成的有限集合，n=0的树是空树，n大于0的树T由以下两个条件约定构成：

1.有一个特殊的结点，称为根结点（root），它没有前驱结点只有后继结点。
2.除了根结点之外的其他结点分为m(0≤m≤n)个互不相交的集合T₀,T₁,T₂,…,T_m-1，其中吧每个集合T_i也是一个树型结构，称之为子树(Subtree)。

（该定义源于java数据结构书）

以下是树的图形都是树的结构：

这里我们需要明白树是递归定义，这也是博主在开头强调的在递归的基础上学习树的原因，如果对于递归还不明白的，建议先看看博主的上一篇文章，毕竟在本篇内容中，递归是随处可见的。嗯，接下来我们先来认识一下树的一些常用术语，这些术语并不要求我们去死记硬背，但在看到这些术语时，我们必须有所了解或者明白其主要含义（以上图为例介绍以下的术语）。

根结点： 根结点是没有双亲的结点，一棵树中最多有一个根结点（如上图的A结点）。
孩子结点：一棵树中，一个结点的子树的根结点称为其孩子结点，如上图的A的孩子结点右B、C、D。
父母结点：相对于孩子结点而已其前驱结点即为父母结点，如上图的B、C、D 三个结点的父母结点都为A，当然E、F结点的父母结点则是B。
兄弟结点：拥有相同的父母结点的所有孩子结点叫作兄弟结点，如上图B、C、D 三个结点共同父结点为A，因此它们是兄弟结点，E、F也是兄弟结点，但是F、G就肯定不是兄弟结点了。
祖先结点：如果存在一条从根结点到结点Q的路径，而且结点P出现在这条路径上，那么P就是Q的祖先结点，而结点Q也称为P的子孙结点或者后代。如上图的E的祖先结点有A和B，而E则是A和B的子孙结点。
叶子结点：没有孩子结点的结点叫作叶子结点，如E、F、G、H等。
结点的度：指的是结点所拥有子树的棵数。如A的度为3，F的度为0，即叶子结点的度为0，而树的度则是树中各个结点度的最大值，如图（d）树的度为3（A结点）
树的层：又称结点的层，该属性反映结点处于树中的层次位置，我们约定根结点的层为1，如上图所示，A层为1，B层为2，E的层为3。
树的高度(深度)：是指树中结点的最大层数，图（d）的高度为3。
边：边表示从父母结点到孩子结点的链接线，如上图（d）中A到B间的连线则称为边。

二、二叉树的定义及其基本性质

在树的数据结构中，二叉树可谓是重中之重，因此我们必须好好学习它！以下是二叉树的定义（源于java数据结构原文）

关于二叉树的定义：二叉树（Binary Tree）是n(n≥0)个结点组成的有限集合，n=0时称为空二叉树；n>0的二叉树由一个根结点和两棵互不相交、分别称为左子树和右子树的子二叉树构成，二叉树也是递归定义的，在树种定义的度、层次等术语，同样适用于二叉树。

关于二叉树的定义：二叉树（Binary Tree）是n(n≥0)个结点组成的有限集合，n=0时称为空二叉树；n>0的二叉树由一个根结点和两棵互不相交、分别称为左子树和右子树的子二叉树构成，二叉树也是递归定义的。在树中定义的度、层次等术语，同样适用于二叉树。

二叉树主要有以下5种基本形态：

二叉树的性质（可以用等比数列理解）

性质1：在二叉树的第i层上至多有2^i-1个结点（i≥1）。层
性质2：深度为k的二叉树至多有2^k-1个结点。深度（和）
性质3：对任何一颗二叉树T，如果其终端结点数为n₀，度为2的结点数为n₂，则n₀=n₂+1。
性质4：具有n个结点的完全二叉树的深度为[log₂n]+1（[x]表示不大于x的最大整数）
性质5：如果对一颗有n个结点的完全二叉树（其深度为[log₂n]+1）的结点按层序编号（从第1层到第[log₂n]+1，每层从左到右），对任一结点i（1≤i≤n）有：

1.如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是节点[i/2]（向下取整）

2.如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是节点2i

3.如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1

三、二叉树抽象数据类型及其存储结构

1.二叉树抽象数据类型

与链表、栈、队列等抽象数据类型相似，二叉树抽象数据类型也有插入、删除、查找等操作，同时二叉树还有4种遍历算法，这个我们后面会详细分析。现在我们声明二叉树的抽象数据类型顶级接口Tree如下：T表示结点元素的类型，该类型必须实现了Comparable接口，方便比较数据。而 BinaryNode是二叉树的结点类。Tree接口声明如下：

public interface Tree<T extends Comparable> {
	//判空
    boolean isEmpty();
    //二叉树的结点个数
    int size();
    //返回二叉树的高度或者深度,即结点的最大层次
    int height();
    //先根次序遍历
    String preOrder();
    //中根次序遍历
    String inOrder();
    //后根次序遍历
    String postOrder();
    //层次遍历
    String levelOrder();
    //将data 插入
    void insert(T data);
    //删除
    void remove(T data);
    //查找最大值
    T findMin();
    //查找最小值
    T findMax();
    //根据值找到结点
    BinaryNode findNode(T data);
    //是否包含某个值
    boolean contains(T data) throws Exception;
    //清空
    void clear();
}

2.二叉树存储结构

关于二叉树的存储结构主要采用的是链式存储结构，至于顺序存储结构仅适用于完全二叉树或满二叉树，这个我们后面再介绍，这里我们主要还是分析二叉树的链式存储结构。二叉树的链式存储结构主要有二叉链表和三叉链表两种，下面分别说明。

二叉树的二叉链表存储结构

二叉链表结构主要由一个数据域和两个分别指向左、右孩子的结点组成。其结构如下：

BinaryNode(T data , BinaryNode<T> left , BinaryNode<T> right )

从图中可以看出，采用二叉链表存储结构，每个结点只存储了到其孩子结点的单向关系，而没有存储到父结点的关系，这样的话，每次要获取父结点时将消耗较多的时间，因为需要从root根结点开始查找，花费的时间是遍历部分二叉树的时间，而且与该结点的位置有关。为了更高效的获取父结点，三叉链表存储结构孕育而生了。

二叉树的三叉链表存储结构

三叉链表主要是在二叉链表的基础上多添加了一个指向父结点的域，这样我们就存储了父结点与孩子结点的双向关系，当然这样也增加了一定的空开销其结点结构如下：

ThreeNode(T data ,ThreeNode<T> parent,ThreeNode<T> left,ThreeNode<T> right)

二叉树的静态二/三叉链表存储结构（了解即可）

除了以上两种结构，其实我们也可采用一个结点数组存储所有二叉树的所有结点，这种结构称为静态二/三叉链表，在这样的结构中，每个结点存储其（父结点）左、右孩子下标，通过下标表示结点间的关系，-1表示无此结点。二叉树静态二叉链表存储结构如下：

	data	parent	left	right
0	A	-1	1	2
1	B	0	3	-1
2	C	0	4	-1
3	D	1	-1	5
4	E	2	-1	-1
5	G	3	-1	-1

四、二叉树的设计

为了使二叉树的实现变得更有具体意义，我们将实现一种叫二叉查找树的数据结构，二叉查找树的特性是：对于树中的每个结点T（T可能是父结点）,它的左子树中所有项的值小T中的值，而它的右子树中所有项的值都大于T中的值。这意味着该树所有的元素可以用某种规则进行排序(取决于Comparable接口的实现)。二叉查找树使用二叉链表存储结构实现。

二叉树结点BinaryNode＜T＞声明如下：

/**
 * Created by zejian on 2016/12/14.
 * Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
 * 二叉树结点
 */
public class BinaryNode<T extends Comparable> implements Serializable{
    private static final long serialVersionUID = -6477238039299912313L;

    public BinaryNode<T> left;//左结点

    public BinaryNode<T> right;//右结点

    public T data;

    public BinaryNode(T data,BinaryNode left,BinaryNode right){
        this.data=data;
        this.left=left;
        this.right=right;
    }

    public BinaryNode(T data){
        this(data,null,null);
    }

    //判断是否为叶子结点
    public boolean isLeaf(){
        return this.left==null&&this.right==null;
    }
}

二叉查找树BinarySearchTree类架构定义如下：

/**
 * Created by zejian on 2016/12/19.
 * Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
 */
public class BinarySearchTree<T extends Comparable> implements Tree<T> {
    //根结点
    protected BinaryNode<T> root;

    public BinarySearchTree(){
        root =null;
    }
    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public int height() {
        return 0;
    }

    @Override
    public String preOrder() {
        return null;
    }

    @Override
    public String inOrder() {
        return null;
    }

    @Override
    public String postOrder() {
        return null;
    }

    @Override
    public String levelOrder() {
        return null;
    }

    @Override
    public void insert(T data) {

    }

    @Override
    public void remove(T data) {

    }

    @Override
    public T findMin() {
        return null;
    }

    @Override
    public T findMax() {
        return null;
    }

    @Override
    public BinaryNode findNode(T data) {
        return null;
    }

    @Override
    public boolean contains(T data) throws Exception {
        return false;
    }

    @Override
    public void clear() {

    }
}

五、二叉查找树基本操作的实现

1.插入算法的实现（递归）

事实上对于二叉查找树的插入操作的设计是比较简单，我们只要利用二叉查找树的特性（即对每个父结点，它的左子树中所有项的值小T中的值，而它的右子树中所有项的值都大于T中的值），找到对应的插入位置即可。假如现在我们要插入data=4的结点，那么可以这样操作：沿着树查找（比较结点的数据与data的大小从而决定往左/右子树继续前行），如果找到data（4）,则什么也不做，否则将data插入到遍历的路径上的最后一个点。

2.删除算法的实现（递归与非递归）

对于二叉树来说，删除是一种比较麻烦的操作，因为涉及到了多种情况（设要删除的结点为q，其父母结点为p）：

如果要删除的结点q恰好是叶子结点，那么它可以立即被删除
如果要删除的结点q拥有一个孩子结点，则应该调整要被删除的父结点(p.left 或 p.right)指向被删除结点的孩子结点（q.left 或 q.right）
如果要删除的结点q拥有两个孩子结点，则删除策略是用q的右子树的最小的数据替代要被删除结点的数据，并递归删除用于替换的结点(此时该结点已为空)，此时二叉查找树的结构并不会被打乱，其特性仍旧生效。采用这样策略的主要原因是右子树的最小结点的数据替换要被删除的结点后可以满足维持二叉查找树的结构和特性，又因为右子树最小结点不可能有左孩子，删除起来也相对简单些。

3.最大和最小值查找算法的实现（递归）

二叉查找树中的findMin和findMax方法分别返回的是树种的最小值和最大值，对于findMin()，则需要从根结点开始并且只要有左孩子就向左进行即可，其终止点即为最小值的元素；而对于findMax()，也需要从根结点开始并且只要有右孩子就向右进行即可，终止点即为值最大的元素。同样的我们使用递归实现它们。

4.深度和大小计算的实现（递归）

根据前面的术语，可知树的深度即为最大层的结点所在层次，而大小就是树的结点数，关于深度，我们只需要从根结点开始寻找，然后计算出左子树的深度和右子树的深度，接着比较左子树与右子树的深度，最后返回深度大的即可。

接着在看看求解二叉树大小(size)的算法该如何实现，实际上，size的求解跟上篇文章分析递归时，汉诺塔问题求解过程十分相似（其实不止是大小求解过程，二叉查找树的所有使用递归的操作都是这样的思想）。

六、二叉查找树的遍历算法

通过前面分析，我们已熟悉了二叉树的一些主要操作方法，那么现在接着来了解二叉查找树的遍历算法，二叉树的遍历规则主要有四种，深度遍历：先根次序遍历（前序遍历），中根次序遍历（中序遍历），后根次序遍历（后序遍历）以及广度遍历：层次遍历。

因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁，而对于广度遍历来说，需要其他数据结构的支撑，比如堆了。所以，对于一段代码来说，可读性有时候要比代码本身的效率要重要的多。

四种主要的遍历思想为：

前序遍历：根结点 —> 左子树 —> 右子树

中序遍历：左子树—> 根结点 —> 右子树

后序遍历：左子树 —> 右子树 —> 根结点

层次遍历：只需按层次遍历即可

二叉树节点：

public class BinaryTree {
	private Node root;
	//内部节点类
	private class Node {
		private int value;
		private Node left;
		private Node right;

		public Node(int value) {
			this.left = null;
			this.right = null;
			this.value = value;
		}
	}
	public BinaryTree() {
		root = null;
	}
}

二叉搜索树的构建

//递归创建二叉搜索树
public void buildTree(Node node, int value) {
    if (root == null) {
        root = new Node(value);
    } else {
        if (value < node.value) {
            if (node.left == null) {
                node.left = new Node(value);
            } else {
                buildTree(node.left, value);
            }
        } else {
            if (node.right == null) {
                node.right = new Node(value);
            } else {
                buildTree(node.right, value);
            }
        }
    }
}

/**
  * 	 20
  * 	/  \
  *    4   45  
  *   / \  / \
  *  3  12 21 111
  */
public static void main(String[] args) {
    int[] a = { 20, 4, 3, 12, 45, 21, 111 };
    BinaryTree bTree = new BinaryTree();
    for (int i = 0; i < a.length; i++) {
        bTree.buildTree(bTree.root, a[i]);
    }
}

1.前序遍历（根左右）

先根次序遍历算法，其访问规则是先遍历根结点，再遍历左子树，最后遍历右子树。如下图先根遍历的次序为ABEFC

从图可知，先根遍历每次总是先访问根结点，再访问左子树，最后访问右子树。而对于一个复杂的树，我们可以先将其简化为三个结点的树（两个结点或者一个结点则空白填补，最后去掉即可），然后解出该子树的顺序，再求解其上层的子树。

如上图的步骤(1)(2)的过程，我们可先求出以B为根的三个结点的子树，先根遍历次序为BEF，然后再求出以A为根结点的树，然后将已解出的(2)作为左子树整体插入到A(BEF)C的序列中即可，这样整棵树的遍历顺序求出来了。事实上这里我们又再次运用递归思维(复杂化简单求解问题)。

递归算法实现前序遍历

//前序遍历
public void preOrder(Node node) {
    if (node != null) {
        System.out.print(node.data+" ");
        preOrder(node.left);
        preOrder(node.right);
    }
}

根据前序遍历的顺序，优先访问根结点，然后再访问左子树和右子树。所以，对于任意结点node，第一部分即直接访问之，之后在判断左子树是否为空，不为空时即重复上面的步骤，直到其为空。若为空，则需要访问右子树。注意，再访问过左孩子之后，需要反过来访问其右孩子，所以，需要栈这种数据结构的支持。

对于任意一个结点node，具体步骤如下：

（1）访问之，并把结点node入栈，当前结点置为左孩子

（2）判断结点node是否为空，若为空，则取出栈顶结点并出栈，将右孩子置为当前结点；否则重复（1）步直到当前结点为空或者栈为空（可以发现栈中的结点就是为了访问右孩子才存储的）

非递归算法实现前序遍历

//非递归先序遍历
public static void preOrderTraversal(Node root) {
    if(root == null){
        return;
    }
    //用来暂存节点的栈
    ArrayDeque<Node> stack = new ArrayDeque<Node>();
    //新建一个游标节点为根节点
    Node node = root;
    //结束的条件：左右子树都为空，并且栈也为空
    while(node!=null || !stack.isEmpty()){
        //若当前考查节点非空，则输出该节点的值。由考查顺序得知，需要一直往左走
        if(node!=null){
            System.out.print(node.value+" ");
            stack.push(node);//为了之后能找到该节点的右子树，暂存该节点
            node = node.left;
        }else{//node == null && !stack.isEmpty()
            // 左子树为空，则开始考虑右子树。如果栈已空，就不需要再考虑。
            node = stack.pop();
            node = node.right;
        }
    }
}

或者

public static void preOrderTraversal2(Node root) {
    if(root == null){
        return;
    }
    ArrayDeque<Node> stack = new ArrayDeque<Node>();
    Node node = root;    
    while(node!=null || !stack.isEmpty()){
        while(node!=null)
            System.out.print(node.value+" ");
            stack.push(node);
            node = node.left;
        }
        //一直到左子树为空，则开始考虑右子树
        //如果栈已空，就不需要再考虑
        //弹出栈顶元素，将游标等于该节点的右子树
        if(!stack.isEmpty()){
            node = stack.pop();
            node = node.right;
        }
    }
}

图的原理跟先根次序的的原理是一样的，唯一不同的是根结点的遍历顺序罢了。

2.中序遍历（左根右）

遍历思路：左子树 —> 根结点 —> 右子树

递归遍历

//中序遍历
public void inOrder(Node node) {
    if (node != null) {
        inOrder(node.left);
        System.out.print(node.value+" ");
        inOrder(node.right);
    }
}

非递归遍历

//非递归中序遍历
public static void inOrderTraversal(Node root) {
    if(root == null){
        return;
    }
    ArrayDeque<Node> stack = new ArrayDeque<Node>();
    Node node = root;
    //结束的条件：左右子树都为空，并且栈也为空
    while(node!=null || !stack.isEmpty()){
        if(node!=null){//由考查顺序得知，需要一直往左走
            stack.push(node);//为了之后能找到该节点的右子树，暂存该节点
            node = node.left;
        }else{//node == null && !stack.isEmpty()
            node = stack.pop();
            //左子树为空，则打印
            System.out.print(node.value+" ");
            node = node.right;
        }
    }
}

3.后序遍历（左右根）

遍历思路：左子树 —> 右子树 —> 根结点

递归遍历

//后序遍历
public void postOrder(Node node) {
    if (node != null) {
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.value+" ");
    }
}

非递归遍历

后序非递归遍历和先序、中序非递归遍历不太一样。

后序遍历在决定是否可以输出当前节点的值的时候，需要考虑其左右子树是否都已经遍历完成。

所以需要设置一个lastVisit游标。若lastVisit等于当前考查节点的右子树，表示该节点的左右子树都已经遍历完成，则可以输出当前节点。并把lastVisit节点设置成当前节点，将当前游标节点node设置为空，下一轮就可以访问栈顶元素。

否则，需要接着考虑右子树，node = node.right。

//非递归后序遍历
public static void postOrderTraversal(Node root) {
    if(root == null){
        return;
    }
    ArrayDeque<Node> stack = new ArrayDeque<Node>();
    Node node = root;
    Node lastVisit = root;
    //结束的条件：左右子树都为空，并且栈也为空
    while(node != null || !stack.isEmpty()){
        if(node != null){
            stack.push(node);
            node = node.left;
        }else{ //node == null && !stack.isEmpty()
            node = stack.peek();//查看当前栈顶元素
            //1.左右子树都为空；2.右子树已经被访问。符合这两种情况则可以打印节点
            if(node.right == null || lastVisit == node.right){
                System.out.print(node.value+" ");
                stack.pop();
                lastVisit = node;
                node = null;
            }else{
                //否则，继续遍历右子树
                node = node.right;
            }
        }
    }
}

4.层次遍历

二叉查找树的层次遍历特性就是兄弟结点优先访问，两个兄弟结点的访问顺序是先左后右的。同样它们的后代结点的访问次序也是先左后右，左兄弟的所有孩子结点一定优先右兄弟的孩子访问。对于二叉查找树的层次遍历算法，我们需要明确如何解决一下的存在的问题（假设p从根结点开始访问）：

p点如何到达其兄弟结点? B->C
p点如何到达它同层下一个结点(非兄弟结点)？D->E
p点如何在访问完当前层的最后一个结点时，进入下一层的第一个结点？C->D

很显然，我们现在遇到的问题跟前面非递归算法遍历的问题有些类似，也就是二叉链表的本身根本无法满足以上任意一个问题。因为从B到C，从D到E，从C到D根本没有桥梁，此时肯定得借助第3方容器来满足需求。那么这个容器该如何选呢？该容器必须告诉我们下一个访问结点是谁？层次遍历的规则是兄弟优先，从左往右。因此，在访问时，必须先将当前正在访问的结点P的左右孩子依次放入容器，如P=C时，E、H必须已在栈中，而且先进入必须先访问。即先进E再进H，然后先访问E再访问H，显然该容器必须满足“先进先出”的原则，那也就是队列了。

层次遍历算法描述如下：
p点从根结点开始访问，设一个空队列，当前p结点不为空时，重复以下操作：
① 访问p结点，将p结点的左右孩子依次入队。
② 使p指向一个出队结点，重复①的操作，直到队列为空。

其过程如下图所示：

层次遍历的代码比较简单，只需要一个队列即可，先在队列中加入根结点。之后对于任意一个结点来说，在其出队列的时候，访问之。同时如果左孩子和右孩子有不为空的，入队列。代码如下：

//层次遍历
public static void levelOrder(Node root){
    if(root == null){
        return;
    }
    //存放需要遍历的结点,左结点一定优先右节点遍历
    ArrayDeque<Node> queue = new ArrayDeque<Node>();
    Node node = root;
    while(node != null){
        System.out.print(node.value+" ");
        //先按层次遍历结点,左结点一定在右结点之前访问
        if(node.left!=null){
            //左孩子结点入队
            queue.offer(node.left);
        }
        if(node.right!=null){
            //右孩子结点入队
            queue.offer(node.right);
        }
        node = queue.poll();
    }
}