树

什么是树？

TreeSet、TreeMap是比较常用的；再到具体的应用，就是文件系统中的应用了。

树状图是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树的基本定义：
树（tree）是包含n（n>0）个结点的有穷集，其中：
（1）每个元素称为结点（node）；
（2）有一个特定的结点被称为根结点或树根（root）。
（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。
（4）结点拥有的子树数称为结点的度(degree)。
比如：下图中A的度为4；B的度为1；F度为0，算做叶子；
（5）树种结点的最大层次为树的深度(depth)或高度，如图中根节点为A的树中，树的深度为3。

树.png 树2.png

森林(forest)是m(m≥0)棵互不相交的树的集合。
森林里可能会有哪些树呢？

树的种类：
无序树：左右结点可换位置。
有序树：如上图，结点从左至右。
二叉树：每个节点最多含有两个子树的树称为二叉树；
完全二叉树：只有最下面的两层结点度小于2
满二叉树：一颗非常完美的树，除了叶节点其他节点都有两个孩子
哈夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；

平衡二叉树：左右两个子树的高度差的绝对值不超过 1。
红黑树：是一种自平衡二叉查找树

线索二叉树：
n个结点的二叉链表中含有n+1(2n-(n-1)=n+1)个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）。

5种二叉树.png 完全二叉树.png 满二叉树.png 哈夫曼树.png 平衡二叉树.png 红黑树.png

哈夫曼树中的带权路径长度？
结点的权：在一些应用中,赋予树中结点的一个有某种意义的实数.
结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积.
树的带权路径长度：定义为树中所有叶结点的带权路径长度之和

二叉树的数组和链表实现？
二叉树的遍历方式？

二叉树的定义：
二叉树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为节点）按分支关系组织起来的结构，而且每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉链表方式存储的二叉树，单个节点包含的内容：

image.png

二叉树的两种实现方式：
数组实现：
因为一棵h层的二叉树最多有2^h - 1个元素。那么创建这么多个元素的数组；

缺点：浪费空间。如下图，数组中需要很多补0 的地方。

数组实现的树.png

链表实现：
每个节点都记住它的左、右两个子节点，为每个节点增加left、right两个指针，分别引用该节点的左、右两个子节点；

二叉树的遍历方式：
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

先序遍历
首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树；（根左右）

中序遍历
首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树；（左根右）

后序遍历
首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根；（左右根）

层次遍历
即按照层次访问，通常用队列来做。访问根，访问子女，再访问子女的子女（越往后的层次越低）（两个子女的级别相同）（从上到下，从左到右）
如图：

树的遍历.png

先序遍历：A B D H I E J C F K G
中序遍历：H D I B E J A F K C G
后序遍历：H I D J E B K F G C A

常见遍历二叉树的面试题
(1) 根据先序、中序遍历的结果，求后续遍历
例：
先序遍历：G D A F E M H Z
中续遍历：A D E F G H M Z
思路：
根据前序遍历的特点，我们知道根结点为G，则中序遍历中G左边的ADEF即为左孩子，G右边的HMZ为右孩子；
然后判断先序遍历中第二个数D，D作为左孩子之中的根结点。D左边的A即为左孩子，D右边的EF为右孩子；

则推导出树是这样的：

树的遍历2.png

代码实现：

package tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

//通过先序方式将数组依次添加到二叉树
public class CreateTreeByArray<E> {
    public static class Node<E>{
        Node<E> left = null;  //左子树
        Node<E> right = null; //右子树
        E data = null;          //数据域
        
        //初始化节点
        public Node(E data){
            this.data = data;
            this.left = null;
            this.right = null;
        }
        
        public Node(){
            
        }
    }
    private Node<E> root = null; //根节点
    private List<Node<E>> list = null; //节点列表，用于将数组元素转化为节点
    
    public Node<E> getRoot(){
        return this.root;
    }
    
    //将将数组转化为一颗二叉树，转换规则：依次为节点列表中节点的左右孩子赋值。左孩子为i*2+1,右孩子为i*2+2
    @SuppressWarnings("unchecked")
    public void createTreeByArray(Object[] array){
        this.list = new ArrayList<Node<E>>();
        
        //将数组添加到节点列表
        for (int i = 0; i < array.length; i++) {
            list.add(new Node<E>((E) array[i]));
        }
        
        System.out.println("头节点->" + list.get(0).data);
        this.root = new Node<E>(list.get(0).data); //根节点
        
        //为二叉树指针赋值
        for(int j = 0; j < (list.size() / 2); j ++){
            try {
                //为左子树赋值  j*2+1
                list.get(j).left = list.get(j * 2 + 1);
                System.out.println("节点" + list.get(j).data + "左子树 ->" + list.get(j * 2 + 1).data);
                //为右子树赋值 j*2+2
                list.get(j).right = list.get(j * 2 + 2);
                System.out.println("节点" + list.get(j).data + "右子树 ->" + list.get(j * 2 + 2).data);
            } catch (Exception e) {
                
            }
        }
        
    }
    
    //先序遍历二叉树
    public void Indorder(Node<E> root){
        if(root == null){
            return;
        }
        System.out.println(root.data);
        Indorder(root.left);  //递归输出左子树
        Indorder(root.right); //递归遍历右子树
    }
    
    //中序遍历二叉树
    public void inOrderTraverse(Node<E> root){
        if(root == null){
            return;
        }
        inOrderTraverse(root.left);  //遍历左子树
        System.out.println(root.data);
        inOrderTraverse(root.right); //遍历右子树
    }
    
    //后序遍历
    public void postOrderTraverse(Node<E> root){
        if(root == null){
            return;
        }
        postOrderTraverse(root.left);  //遍历左子数节点
        postOrderTraverse(root.right); //遍历右子树节点
        System.out.println(root.data); //从下往上遍历
    }
        
    
    public static void main(String[] args) {
        CreateTreeByArray<Integer> createTreeByArray = new CreateTreeByArray<Integer>();
        Object[] arrays = {new Integer(1),new Integer(2),new Integer(3),new Integer(4),5,6,7,8,9,10};
        createTreeByArray.createTreeByArray(arrays);
        System.out.println("===============================");
        createTreeByArray.postOrderTraverse(createTreeByArray.list.get(0));
    
    }

}

除了树的遍历，还有很多树的操作方式。插入子树、删除子树、获取最左边的结点、获取结点的兄弟结点和父结点等等。。。