Question

概述

二叉树是树的特殊一种，具有如下特点：

• 每个结点最多有两颗子树，结点的度最大为 2。
• 左子树和右子树是有顺序的，次序不能颠倒。
• 即使某结点只有一个子树，也要区分左右子树。

二叉树五种基本形态

1. 空二叉树。
2. 只有一个根结点。
3. 根结点只有左子树。
4. 根结点只有右子树。
5. 根结点既有左子树又有右子树。

特殊二叉树

斜树

• 斜树一定要是斜的，但是往哪斜还是有讲究。所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树 。
• 斜树有很明显的特点，就是每 一层都只有一个结点，结点的个数与二叉树的深度相同 。

满二叉树

• 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树
• 单是每个结点都存在左右子树，不能算是满二叉树，还必须要所有的叶子都在同一层上，这就做到了整棵树的平衡

完全二叉树

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

满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的 。
完全二叉树的所有结点与同样深度的满二叉树，它们按层序编号相同的结点是一 一对应的

• 像图 6-5-7 中的树 1,因为 5 结点 没有左子树，却有右子树，那就使得按层序编号的第 10 个编号空档了。
• 同样道理，图 6-5-7 中的树 2,由于 3 结点没有子树，所以使得 6、7 编号的位置空挡了。
• 图 6-5-7 中的树 3 又是因为 5 编号下没有子树造成第 10 和第 11 位置空档。
• 只有图 6-5-6 中的 树，尽管它不是满二叉树，但是编号是连续的，所以它是完全二叉树。

完全二叉树的特点:

• 叶子结点只能出现在最下两层。
• 最下层的叶子一定集中在左部连续位置。
• 倒数二层，若有叶子结点，一定都在右部连续位置。
• 如果结点度为 1,则该结点只有左孩子，即不存在只有右子树的情况。 同样结点数的二叉树，完全二叉树的深度最小。

二叉树的性质

• 在二叉树的第 i 层上至多有 2 的 i-1 次方个结点 ((2i−12^i-12i−1))。

• 深度为 k 的二叉树至多有 2 的 k 次方减 1 个结点(2k−12^k-12k−1)。

• 对任何一棵二叉树 T,如果其终端结点数为 n0n_0n0​,度为 2 的结点数为 n2n_2n2​,则 n0n_0n0​=n2n_2n2​+1

• 比如图 6-6-1 的例子，结点总数为 10,宫是由 A、 B、 c、 D 等度为 2 结点, F、 G、H、 l、J 等度为 0 的叶子结点和 E 这个度为 1 的结点组成。 总和为 4+1+5=10。

• 具有 n 个结点的完全二叉树的深度为[logn2n]+1

如果对一棵有 n 个结点的完全二叉树（其深度为 [logn2n]+1) 的结点按层 序编号（从第 1 层到第[logn2n]+1 层，每层从左到右),对任一结点 i (1<=i<=n) 有:

1. 如果 i=1 ,则结点 i 是二叉树的棍，无双亲;如果 i> 1,则其双亲是结点 i2\frac{i}{2}2i​。
2. 如果 2*i>n ,则结点 i 左孩子（结点 i 为叶子结点) ;否则其左孩子是结点 2*i。
3. 如果 2*i+1>0 ,则结点 i 无右孩子;否则其右孩子是结点 2*i+1 .

• i=l 时就是根结点。 i>1 时，比如结点 7 的双亲就是 7/2=3, 结点 9 它的双亲就是 9/2=4
• 第二条，比如结点 6,因为 2X6=12 超过了结点总数 10,所以结点 6 元左孩子 , 它是叶子结点。 同样，而结点 5, 因为 2XS=10 正好是结点，总数 10,所以它的左孩子 是结点 10。
• 第三条，比如结点 5,因为 2X5+1=l1,大于结点总数 10,所以它无右孩子。 而 结点 3,因为 2X3 吐=7 小于 10,所以宫的右孩子是结点 7

二叉树的顺序存储结构

• 二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，井且结点的存储位
  置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右 兄弟的关系等。
• 顺序存储 结构一般只用于完全二叉树。

package com.example.qxw.tree;

import java.util.Arrays;

/**
 *  二叉树的顺序存储结构:
 *
 *  二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，井且结点的存储位 置,
 *  也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右 兄弟的关系等
 *
 *  顺序存储结构一般只用于完全二叉树
 *
 * @author qinxuewu
 * @create 19/2/9 下午 6:12
 * @since 1.0.0
 */


public class TreeTest01<T> {
    //二叉树的默认深度
    private final int DEFAULT_DEEP=16;
    //二叉树的深度
    private int k;
    //用来存储数组的长
    private int length;
    //数据区域
    private Object[] data;


    //初始化二叉树
    public TreeTest01(){
        k=DEFAULT_DEEP;
        //深度为 k 的二叉树至多有 2 的 k 次方减 1 个结点
        length=(int) Math.pow(2, k);
        data=new Object[length];
    }
    public TreeTest01(int deep){
        this.k=deep;
        length=(int) Math.pow(2, deep);
        data=new Object[length];

    }
    //初始化二叉树 指定根结点
    public TreeTest01(T element,int deep){
        this.k=deep;
        length=(int) Math.pow(2, deep);
        data=new Object[length];
        data[0]=element;
    }

    //根据元素查找在二叉树出现的第一个位置
    public int indexOf(T element){
        for(int i=0;i<data.length;i++){
            if(data[i].equals(element)){
                return i;
            }
        }
        return -1;
    }
    //根节点
    public T getRoot(){
        return (T) data[0];
    }

    //

    /**
     * 查找指定结点的父节点
     *
     * 根据二叉树的性质：
     * 如果 i=1 ,则结点 i 是二叉树的根，无双亲;如果 i> 1,则其双亲是结点(i/2)
     * 所以得出求父节点公式：(index-1)/2  因为数据下标从 0 开始所以 index-1。
     */
    public T getParent(int index){
        if(index==0){
            throw new RuntimeException("该节点不存在父节点");
        }
        return (T) data[(index-1)/2];
    }

    //判断二叉树是否为空
    public boolean isEmpty(){
        return data[0]==null;
    }

    //获取指定结点
    public T get(int index){
        if(index>length||index<0){
            throw new RuntimeException("超出底层数组范围");
        }
        return (T) data[index];
    }


    /**
     * 为指定结点添加子节点
     * @param index
     * @param element
     * @param left 是否是左结点
     */
    public void add(int index,T element,boolean left){
        if(data[index]==null){
            throw new RuntimeException("该节点为空，不能添加子节点");
        }
        if(index*2+1>length||index*2+2>length){
            throw new RuntimeException("超出底层数组范围");
        }
        if(left){
            /**
             * 根据二叉树的性质：
             * 如果对一棵有 n 个结点的完全二叉树的结点按层序编号（每层从左到右)) 对任一结点 i
             * 如果 2*i>n(i=结点编号即下标 n=结点总数),则结点 i 无左孩子
             * 所以得出 data[index*2+1]下标处如果为空就不存在左子节点可以进行插入
             */
            if(data[index*2+1]!=null){
                throw new RuntimeException("该节点已经存在左子节点");
            }else{
                data[index*2+1]=element;
            }
        }else{
            /**
             * 根据二叉树的性质：
             * 如果对一棵有 n 个结点的完全二叉树的结点按层序编号（每层从左到右)) 对任一结点 i
             * 如果 2*i+1>n(i=结点编号即下标 n=结点总数),则结点 i 无右孩子
             * 所以得出 data[index*2+1++]下标处如果为空就不存在右子节点可以进行插入
             */
            if(data[index*2+2]!=null){
                throw new RuntimeException("该节点已经存在右子节点");
            }else{
                data[index*2+2]=element;
            }
        }
    }

    //获取指定结点的右节点
    public T getRight(int index){
        if(index*2+1>length||index*2+2>length){
            throw new RuntimeException("超出底层数组范围");
        }
        return (T) data[index*2+2];
    }

    //获取指定结点的左结点
    public T getLeft(int index){
        if(index*2+1>length||index*2+2>length){
            throw new RuntimeException("超出底层数组范围");
        }
        return (T) data[index*2+1];
    }
    public String toString(){
        if(data[0]==null){
            return "[]";
        }else{
            return Arrays.toString(data);
        }
    }


    public static void main(String[] args) {
        //完全二叉树
        TreeTest01<String> tree=new TreeTest01<>("A",4);
        tree.add(0,"B",true); //左结点
        tree.add(0,"C",false);//右结点
        tree.add(1,"D",true);
        tree.add(1,"E",false);
        tree.add(2,"F",true);
        tree.add(2,"G",false);
        tree.add(3,"H",true);
        tree.add(3,"I",false);
        tree.add(4,"J",true);
        System.out.println(tree.toString());
        System.out.println(tree.get(2)); // 获取下标 2 的结点：C
        System.out.println(tree.getParent(2));// 获取下标 2 的双亲结结点：A
        System.out.println(tree.getRight(2));// 获取下标 2 的右子结点：G
        System.out.println(tree.getLeft(2));// 获取下标 2 的左子结点：F
    }


}

二叉树的链式存储结构

• 二叉树每个结点最多有 两个孩子，所以为它设计一个数据域和两个指针域是 比较自然的想法，我们称这样的 链表叫做二叉链衰

data 是数据区域。lchild 和 民 rchild 都是指针域分别存放指向左孩子和右孩子的指针

遍历二叉树

• 二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点.使得每个结点被访问-次 旦仅被访问一次 。
• 二叉树的遍历次序不同于线性结构，最多也就是从头至尾、循环、双向等简单的 遍历方式。树的结点之间不存在唯一的前驱和后继关系，在访问 一个结点后，下一个 被访问的结点面临着不同的选择 。

二叉树遍历方法

如果我们限制了从左到右的习惯方式，那么主要就分为四种

1. 前序遍历

• 若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子 树 , 再前序遍历右子树

2. 中序遍历

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

3. 后序遍历

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

4. 层序遍历

• 若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的颇用才结点逐个访问

JAVA 实现二叉树的链式存储以及遍历

public class TreeNode<E> {
    private E data;   //数据域
    private TreeNode<E> lchild;  //左孩子
    private TreeNode<E> rchild;  //右孩子

    TreeNode(){}

    TreeNode(E e){
        this.data = e;
    }

    TreeNode(E data,TreeNode<E> lchild, TreeNode<E> rchild){
        this.data = data;
        this.lchild = lchild;
        this.rchild = rchild;
    }

    public void setData(E data){
        this.data = data;
    }

    public E getData(){
        return this.data;
    }

    public void setLchild(TreeNode<E> lchild){
        this.lchild = lchild;
    }

    public TreeNode<E> getLchild(){
        return this.lchild;
    }

    public void setRchild(TreeNode<E> rchild){
        this.rchild = rchild;
    }

    public TreeNode<E> getRchild(){
        return this.rchild;
    }
}

public class BinaryTree<E> {

    private TreeNode<E> root;  //根节点
    private List<TreeNode> nodeList = null;   //二叉树节点的链式结构

    public BinaryTree(){

    }
    public BinaryTree(TreeNode<E> root){
        this.root = root;
    }

    //把一个数组转化为一颗完全二叉树
    public TreeNode<E> buildTree(E[] array){
        nodeList = new LinkedList<TreeNode>();
        //将数组中的元素依次转换为 TreeNode 节点，存放于链表中
        for(int i=0; i< array.length; i++){
            nodeList.add(new TreeNode(array[i]));
        }
        //对前（array.length / 2 - 1）个父节点，按照父节点与孩子节点的数字关系建立完全二叉树
        for(int j=0; j < (array.length/2-1);j++){
            /**
             * 根据二叉树的性质：
             * 如果对一棵有 n 个结点的完全二叉树的结点按层序编号（每层从左到右)) 对任一结点 i
             * 如果 2*i>n(i=结点编号即下标 n=结点总数),则结点 i 无左孩子
             * 如果 2*i+1>n(i=结点编号即下标 n=结点总数),则结点 i 无右孩子
             */

            //左孩子 (2*i+1）
            nodeList.get(j).setLchild(nodeList.get(j*2+1));
            //右孩子 2*i+2）
            nodeList.get(j).setRchild(nodeList.get(j*2+2));
        }
        //最后一个父节点：因为最后一个父节点可能没有右孩子，所以单独处理
        int index = array.length/2 -1;
        //左孩子
        nodeList.get(index).setLchild(nodeList.get(index*2+1));
        //右孩子：如果数组的长度为奇数才有右孩子
        if(array.length % 2 == 1){
            nodeList.get(index).setRchild(nodeList.get(index*2+2));
        }
        root=nodeList.get(0); //设置根节点
        return root;
    }

    //得到树的高度
    public int height(TreeNode<E> node){
        if(node == null){
            return 0;
        }else{
            int i = height(node.getLchild());
            int j = height(node.getRchild());
            return (i<j)?(j+1):(i+1);
        }
    }

    //递归计算节点的总个数
    public int size(TreeNode<E> node){
        if(node == null){
            return 0;
        }else{
            //根节点+左子节点+右子节点
            return 1+ size(node.getLchild())+size(node.getRchild());
        }
    }


    /**
     * 递归实现先序遍历
     * 先访问根结点，然后前序遍历左子 树 , 再前序遍历右子树
     * @param node
     */
    public void preOrder(TreeNode<E> node){
        if(node != null){
            System.out.print(node.getData() + " ");
            preOrder(node.getLchild());
            preOrder(node.getRchild());
        }
    }

    /**
     * 递归实现中序遍历
     * 从根结点开始（注意并不是先访问根结点),中序遍历根结点的左子树,
     * 然后是访问根结点，最后中序遍历右子树
     * @param node
     */
    public void inOrder(TreeNode<E> node){
        if(node != null){
            inOrder(node.getLchild());
            System.out.print(node.getData() + " ");
            inOrder(node.getRchild());
        }
    }


    /**
     * 递归实现后序遍历
     * 从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点
     * @param node
     */
    public void postOrder(TreeNode<E> node){
        if(node != null){
            postOrder(node.getLchild());
            postOrder(node.getRchild());
            System.out.print(node.getData() + " ");
        }
    }

    /**
     * 层序遍历
     *
     * 从树的第一层，也就是根结点开始访问，从上而下逐层遍历,
     * 在同一层中，按从左到右的颇用才结点逐个访问
     * @param root
     */
    public void levelOrder(TreeNode<E> root){
        Queue<TreeNode<E>> nodeQueue = new LinkedList<TreeNode<E>>();
        TreeNode<E> node = null;
        nodeQueue.add(root);  //将根节点入队
        while(!nodeQueue.isEmpty()){  //队列不空循环
            node = nodeQueue.peek();
            System.out.print(node.getData()+" ");
            nodeQueue.poll();     //队头元素出队
            if(node.getLchild() != null){     //左子树不空，则左子树入队列
                nodeQueue.add(node.getLchild());
            }
            if(node.getRchild() != null){     //右子树不空，则右子树入队列
                nodeQueue.add(node.getRchild());
            }
        }
    }

    public static void main(String[] args) {
        //将一个数组转化为一颗完全二叉树
        //将一个数组转化为一颗完全二叉树
        Object[] array = {1,2,3,4,5,6,7,8};
        BinaryTree bt = new BinaryTree();
        TreeNode root = bt.buildTree(array);
        System.out.println("height: "+bt.height(root));
        System.out.println("size: "+bt.size(root));
        System.out.println("先序遍历：");
        bt.preOrder(root);
        System.out.println();

        System.out.println("中序遍历：");
        bt.inOrder(root);
        System.out.println();

        System.out.println("中序遍历：");
        bt.levelOrder(root);
        System.out.println();

        System.out.println("层次遍历：");
        bt.levelOrder(root);

    }
}