数据结构与算法之四：树

树结构用处很多，如现代计算机文件系统使用的B+树，本文对树结构进行详细的整理，从二叉树到红黑树，希望可以有一个比较完整清晰的认识。

基本概念

树是一种一对多的的线性结构，一对多的意思是一个元素只能有一个前驱，但是可以有多个后继。
树（tree）是n（n>=0）个结点的有穷集。n=0时称为空树。在任意一个非空树中：

每个元素称为结点（node）
仅有一个特定的结点被称为根结点或树根（root）
当n>1时，其余结点可分为m（m≥0）个互不相交的集合T1，T2，……Tm，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作根的子树（subtree）。

注意：

n>0时，根节点是唯一的。
m>0时，子树的个数没有限制，但它们一定是互不相交的。

结点拥有的子树数被称为结点的度（Degree）。度为0的结点称为叶节点（Leaf）或终端结点，度不为0的结点称为分支结点。

除根结点外，分支结点也被称为内部结点。结点的子树的根称为该结点的孩子（Child），该结点称为孩子的双亲或父结点。同一个双亲的孩子之间互称为兄弟。树的度是树中各个结点度的最大值。

结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度。如果将树中结点的各个子树看成从左到右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。森林是m（m>=0）棵互不相交的树的集合。

树的定义：

树的存储结构

由于树中每个结点的孩子可以有多个，所以简单的顺序存储结构无法满足树的实现要求。下面介绍三种常用的表示树的方法：双亲表示法、孩子表示法和孩子兄弟表示法。

双亲表示法

由于树中每个结点都仅有一个双亲结点（根节点没有），我们可以使用指向双亲结点的指针来表示树中结点的关系。这种表示法有点类似于前面介绍的静态链表的表示方法。具体做法是以一组连续空间存储树的结点，同时在每个结点中，设一个「游标」指向其双亲结点在数组中的位置。代码如下：

public class PTree<E> {
    private static final int DEFAULT_CAPACITY = 100;
    private int size;
    private Node[] nodes;
    private class Node() {
        E data;
        int parent;
        Node(E data, int parent) {
            this.data = data;
            this.parent = parent;
        }
    }
    public PTree() {
        nodes = new PTree.Node[DEFAULT_CAPACITY];
    }
}

由于根结点没有双亲结点，我们约定根节点的parent域值为-1。树的双亲表示法如下所示：

这样的存储结构，我们可以根据结点的parent域在O(1)的时间找到其双亲结点，但是只能通过遍历整棵树才能找到它的孩子结点。一种解决办法是在结点结构中增加其孩子结点的域，但若结点的孩子结点很多，结点结构将会变的很复杂。

孩子表示法

由于树中每个结点可能有多个孩子，可以考虑用多重链表，即每个结点有多个指针域，每个指针指向一个孩子结点，我们把这种方法叫多重链表表示法。它有两种设计方案：

方案一：指针域的个数等于树的度。其结点结构可以表示为：

class Node() {
    E data;
    Node child1;
    Node child2;
    ...
    Node childn;
}

对于上一节中的树，树的度为3，其实现为：

显然，当树中各结点的度相差很大时，这种方法对空间有很大的浪费。

方案二：每个结点指针域的个数等于该结点的度，取一个位置来存储结点指针的个数。其结点结构可以表示为：

这种方法克服了浪费空间的缺点，但由于各结点结构不同，在运算上会带来时间上的损耗。

为了减少空指针的浪费，同时又使结点相同。我们可以将顺序存储结构和链式存储结构相结合。具体做法是：把每个结点的孩子结点以单链表的形式链接起来，若是叶子结点则此单链表为空。然后将所有链表存放进一个一维数组中。这种表示方法被称为孩子表示法。其结构为：

代码表示：

public class CTree<E> {
    private static final int DEFAULT_CAPACITY = 100;
    private int size;
    private Node[] nodes;
    private class Node() {
        E data;
        ChildNode firstChild;
    }
    
    //链表结点
    private class ChildNode() {
        int cur; //存放结点在nodes数组中的下标
        ChildNode next;
    }
    public CTree() {
        nodes = new CTree.Node[DEFAULT_CAPACITY];
    }
}

这种结构对于查找某个结点的孩子结点比较容易，但若想要查找它的双亲或兄弟，则需要遍历整棵树，比较麻烦。可以将双亲表示法和孩子表示法相结合，这种方法被称为双亲孩子表示法。其结构如下：

其代码和孩子表示法的基本相同，只需在Node结点中增加parent域即可。

孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在则是唯一的，它的右兄弟如果存在也是唯一的。因此，我们可以使用两个分别指向该结点的第一个孩子和右兄弟的指针来表示一颗树。其结点结构为：

class Node() {
    E data;
    Node firstChild;
    Node rightSib;
}

其结构如下：

这个方法，可以方便的查找到某个结点的孩子，只需先通过firstChild找到它的第一个孩子，然后通过rightSib找到它的第二个孩子，接着一直下去，直到找到想要的孩子。若要查找某个结点的双亲和左兄弟，使用这个方法则比较麻烦。

这个方法最大的好处是将一颗复杂的树变成了一颗二叉树。这样就可以使用二叉树的一些特性和算法了。

二叉树

基本概念

二叉树（Binary Tree）是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

二叉树的特点：

二叉树不存在度大于2的结点。
二叉树的子树有左右之分，次序不能颠倒。

如下图中，树1和树2是同一棵树，但它们是不同的二叉树。

斜树

所有的结点都只有左子树的二叉树叫左斜树。所有的结点都只有右子树的二叉树叫右斜树。这两者统称为斜树。

斜树每一层只有一个结点，结点的个数与二叉树的深度相同。其实斜树就是线性表结构。

满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树具有如下特点：

叶子只能出现在最下一层
非叶子结点的度一定是2
同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树

若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

对于一棵具有n个节点的二叉树（按层序编号），如果编号为i的节点与同样深度的满二叉树中编号为i的节点在二叉树的位置完全相同，则为完全二叉树。

完全二叉树的特点：

叶子结点只能出现在最下两层
最下层叶子在左部并且连续
同样结点数的二叉树，完全二叉树的深度最小

平衡二叉树

平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树.

平衡二叉树一般是一个有序树，它具有二叉树的所有性质，其遍历操作和二叉树的遍历操作相同。但是由于其对二叉树施加了额外限制，因而其添加、删除操作都必须保证平衡二叉树的因子被保持。

平衡二叉树中引入了一个概念：平衡二叉树节点的平衡因子，它指的是该节点的两个子树，即左子树和右子树的高度差，即用左子树的高度减去右子树的高度，如果该节点的某个子树不存在，则该子树的高度为0,如果高度差的绝对值超过1就要根据情况进行调整。

平衡的调整共有四种情况：分别为LL,LR,RR,RL。

二叉树的性质

在二叉树的第 i 层至多有 2^(i －1)个结点。(i>=1)
深度为 k 的二叉树至多有 2^(k-1)个结点(k >=1)。
对任何一棵二叉树T, 如果其叶结点数为n0, 度为2的结点数为 n2,则n0＝n2＋1。
具有 n (n>=0) 个结点的完全二叉树的深度为log2(n)+1
如将一棵有n个结点的完全二叉树自顶向下，同层自左向右连续为结点编号0,1, …, n-1，则有：
- 若i = 0, 则 i 无双亲, 若i > 0, 则 i 的双亲为(i -1)/2
- 若2*i+1 < n, 则i 的左子女为 2*i+1，若2*i+2 < n, 则 i 的右子女为2*i+2
- 若结点编号i为偶数，且i != 0,则左兄弟结点i-1.
- 若结点编号i为奇数，且i != n-1,则右兄弟结点为i+1.
- 结点i 所在层次为log2(i+1)

二叉树的实现

二叉树是一种特殊的树，它的存储结构相对于前面谈到的一般树的存储结构要简单一些。

顺序存储

二叉树的顺序存储结构就是用一维数组来存储二叉树中的结点。不使用数组的第一个位置。结点的存储位置反映了它们之间的逻辑关系：位置k的结点的双亲结点的位置为k/2，它的两个孩子结点的位置分别为2k和2k+1。

代码实现：

public class ArrayBinaryTree<E> {
    private static final int DEFAULT_DEPTH = 5;
    private int size = 0;
    private E[] datas;
    ArrayBinaryTree() {
        this(DEFAULT_DEPTH);
    }
    @SuppressWarnings("unchecked")
    ArrayBinaryTree(int depth) {
        datas = (E[]) new Object[(int)Math.pow(2, depth)];
    }
    public boolean isEmpty() { return size == 0; }
    public int size(){ return size; }
    public E getRoot() { return datas[1]; }
    // 返回指定节点的父节点    
    public E getParent(int index) {  
        checkIndex(index);  
        if (index == 1) {    
            throw new RuntimeException("根节点不存在父节点！");    
        }    
        return datas[index/2];    
    }    
        
    //获取右子节点    
    public E getRight(int index){    
        checkIndex(index*2 + 1);  
        return datas[index * 2 + 1];    
    }    
        
    //获取左子节点    
    public E getLeft(int index){    
        checkIndex(index*2);    
        return datas[index * 2];    
    }     
        
    //返回指定数据的位置    
    public int indexOf(E data){    
       if(data==null){   
         throw new NullPointerException();  
       } else {  
           for(int i=0;i<datas.length;i++) {  
               if(data.equals(datas[i])) {  
                   return i;  
               }  
           }  
       }  
        return -1;    
    }
    //顺序添加元素
    public void add(E element) {
        checkIndex(size + 1);
        datas[size + 1] = element;
        size++;
    }
    //在指定位置添加元素
    public void add(E element, int parent, boolean isLeft) {
        if(datas[parent] == null) {  
            throw new RuntimeException("index["+parent+"] is not Exist!");  
        }  
        if(element == null) {  
            throw new NullPointerException();  
        } 
        if(isLeft) {
            checkIndex(2*parent);
            if(datas[parent*2] != null) {  
                throw new RuntimeException("index["+parent*2+"] is  Exist!");  
            }
            datas[2*parent] = element;
        }else {
            checkIndex(2*parent + 1);
            if(datas[(parent+1)*2]!=null) {  
                throw new RuntimeException("index["+ parent*2+1 +"] is  Exist!");  
            } 
            datas[2*parent + 1] = element;
        }
        size++;
    }
    //检查下标是否越界
    private void checkIndex(int index) {  
        if(index <= 0 || index >= datas.length) {  
            throw new IndexOutOfBoundsException();  
        }  
    } 
    public static void main(String[] args) {
        char[] data = {'A','B','C','D','E','F','G','H','I','J'};
        ArrayBinaryTree<Character> abt = new ArrayBinaryTree<>();
        for(int i=0; i<data.length; i++) {
            abt.add(data[i]);
        }
        System.out.print(abt.getParent(abt.indexOf('J')));
    }
}

一棵深度为k的右斜树，只有k个结点，但却需要分配2k-1个顺序存储空间。所以顺序存储结构一般只用于完全二叉树。

链式存储

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域即可。我们称这样的链表为二叉链表。其结构如下图：

代码如下：

import java.util.*;
public class LinkedBinaryTree<E> {    
    private List<Node> nodeList = null;  
   
    private class Node {  
        Node leftChild;  
        Node rightChild;  
        E data;  
  
        Node(E data) {  
            this.data = data;  
        }  
    }  
  
    public Node getRoot() {
        return nodeList.get(0);
    }
    public void createBinTree(E[] array) {  
        nodeList = new LinkedList<Node>();  
        for (int i = 0; i < array.length; i++) {  
            nodeList.add(new Node(array[i]));  
        }  
        // 对前lasti-1个父节点按照父节点与孩子节点的数字关系建立二叉树  
        for (int i = 0; i < array.length / 2 - 1; i++) {   
            nodeList.get(i).leftChild = nodeList.get(i * 2 + 1);    
            nodeList.get(i).rightChild = nodeList.get(i * 2 + 2);  
        }  
        // 最后一个父节点:因为最后一个父节点可能没有右孩子，所以单独拿出来处理  
        int lastParent = array.length / 2 - 1;  
        nodeList.get(lastParent).leftChild = nodeList  .get(lastParent * 2 + 1);  
        // 右孩子,如果数组的长度为奇数才建立右孩子  
        if (array.length % 2 == 1) {  
            nodeList.get(lastParent).rightChild = nodeList.get(lastParent * 2 + 2);  
        }  
    } 
    public static void main(String[] args) {
        Character[] data = {'A','B','C','D','E','F','G','H','I','J'};
        LinkedBinaryTree<Character> ldt = new LinkedBinaryTree<>();
        ldt.createBinTree(data);
    }
}

二叉树的遍历

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

二叉树的遍历主要包括前序遍历、中序遍历、后序遍历和层序遍历四种，其中前三种是非常常用的。

前序遍历

二叉树为空就空操作返回，否则先访问根结点，然后遍历左子树，最后遍历右子树。

//顺序存储
public void preOrderTraverse(int index) {  
    if (datas[index] == null)  
        return;  
    System.out.print(datas[index] + " ");  
    preOrderTraverse(index*2);  
    preOrderTraverse(index*2+1);  
} 
//链式存储
 public void preOrderTraverse(Node node) {  
    if (node == null)  
        return;  
    System.out.print(node.data + " ");  
    preOrderTraverse(node.leftChild);  
    preOrderTraverse(node.rightChild);  
}

前序遍历有如下技巧

从根节点的左边开始，绕过所有节点和边，画出一条封闭的、有向的遍历曲线（如上图红色所示）
对于每个节点，曲线第一次从连线进入节点的位置标记为1，最后一次从节点出去的位置标记为2 。
如上图的标记所示，沿着遍历曲线的方向，依次经过标记为1的节点为前序遍历序列：ABEFIJCDGH 。

中序遍历

若二叉树为空，则空操作返回，否则从根节点开始（注意不是先访问根节点），中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树。

先遍历左子树，然后遍历根结点，最后遍历右子树。

//链式存储
 public void inOrderTraverse(Node node) {  
    if (node == null)  
        return;  
    inOrderTraverse(node.leftChild);
    System.out.print(node.data + " ");  
    inOrderTraverse(node.rightChild);  
}

同样的技巧

对于所有叶子节点，在标记1和2中间加上标记0。
当父节点只有左子树时，在该节点右下方标记0；当父节点只有右子树时，在该节点的左下方标记0 。
当父节点同时有左右子树时，在其正下方标记0 。
沿着遍历曲线的方向，依次经过标记为0的节点为中序遍历序列：DGBAECHF 。

后续遍历

若二叉树为空，则空操作返回，否则从左到右先叶子后节点的方式遍历访问左右子树，最后是访问根节点。

先遍历左子树，然后遍历右子树，最后遍历根结点。

//链式存储
 public void postOrderTraverse(Node node) {  
    if (node == null)  
        return;  
    postOrderTraverse(node.leftChild);
    postOrderTraverse(node.rightChild);  
    System.out.print(node.data + " ");  
}

沿着遍历曲线的方向，依次经过标记为2的节点为后序遍历序列：EIJFBCGHDA 。

层序遍历

从上到下逐层遍历，在同一层中，按从左到右的顺序遍历。

遍历的性质

已知前序遍历和中序遍历，可以唯一的确定一个二叉树；
已知后序遍历和中序遍历，可以唯一的确定一个二叉树；
但是，已知前序遍历和后序遍历，是不能唯一的确定一棵二叉树的。

比如，如前序遍历是ABC，后序遍历是CBA的二叉树有如下，我们可以确定A是根节点，但是无法确定那个是左子树，哪个是右子树。

线索二叉树

对于n个结点的二叉树，在二叉链存储结构中有n+1个空指针域，利用这些空指针域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针被称为线索，加上线索的二叉树称为线索二叉树。

结点结构如下：

其中：

lTag为0时，lChild指向该结点的左孩子，为1时指向该结点的前驱
rTag为0时，rChild指向该结点的右孩子，为1时指向该结点的后继。

线索二叉树的结构图为：图中蓝色虚线为前驱，红色虚线为后继

代码如下：

public class ThreadedBinaryTree<E> {
    private TBTreeNode root;
    private int size;          // 大小  
    private TBTreeNode pre;   // 线索化的时候保存前驱  
    class TBTreeNode {
        E element;
        boolean lTag; //false表示指向孩子结点，true表示指向前驱或后继的线索
        boolean rTag;
        TBTreeNode lChild;
        TBTreeNode rChild;
        public TBTreeNode(E element) {
            this.element = element;
        }
    }
    
    public ThreadedBinaryTree(E[] data) {
        this.pre = null;  
        this.size = data.length;  
        this.root = createTBTree(data, 1);
    }
    //构建二叉树
    public TBTreeNode createTBTree(E[] data, int index) {  
        if (index > data.length){  
            return null;  
        }  
        TBTreeNode node = new TBTreeNode(data[index - 1]);  
        TBTreeNode left = createTBTree(data, 2 * index);  
        TBTreeNode right = createTBTree(data, 2 * index + 1);  
        node.lChild = left;  
        node.rChild = right;  
        return node;  
    } 
    /** 
     * 将二叉树线索化   
     */  
    public void inThreading(TBTreeNode node) {  
        if (node != null) {  
            inThreading(node.lChild);     // 线索化左孩子 
            if (node.lChild == null) {  // 左孩子为空  
                node.lTag = true;    // 将左孩子设置为线索  
                node.lChild = pre;  
            }  
            if (pre != null && pre.rChild == null) {  // 右孩子为空  
                pre.rTag = true;  
                pre.rChild = node;  
            }  
            pre = node;  
            inThreading(node.rChild);  // 线索化右孩子  
        }  
    }  
  
    /** 
     * 中序遍历线索二叉树 
     */  
    public void inOrderTraverseWithThread(TBTreeNode node) {
        while(node != null) {
            while(!node.lTag) { //找到中序遍历的第一个结点
                node = node.lChild;
            }
            System.out.print(node.element + " "); 
            while(node.rTag && node.rChild != null) { //若rTag为true，则打印后继结点
                node = node.rChild;
                System.out.print(node.element + " "); 
            }
            node = node.rChild;
        }
    }  
  
    /** 
     * 中序遍历，线索化后不能使用
     */  
    public void inOrderTraverse(TBTreeNode node) {  
        if(node == null)
            return;
        inOrderTraverse(node.lChild);  
        System.out.print(node.element + " ");  
        inOrderTraverse(node.rChild);  
    } 
    public TBTreeNode getRoot() { return root;}
    public static void main(String[] args) {
        Character[] data = {'A','B','C','D','E','F','G','H','I','J'};
        ThreadedBinaryTree<Character> tbt = new ThreadedBinaryTree<>(data);
        tbt.inOrderTraverse(tbt.getRoot());
        System.out.println();
        tbt.inThreading(tbt.getRoot());
        tbt.inOrderTraverseWithThread(tbt.getRoot());
    }
}