二叉树

二叉树

左子树和右子树都为空的元素称为叶节点。

性质

• 二叉树第i层上的节点数目至多为$2^{i-1}$
• 深度为k的二叉树至多有$2^k-1$个节点
• 在任何一棵二叉树中，如果叶子节点的数量为n0，度为2的子节点数量为n2，则n0=n2+1
• 具有n个节点的完全二叉树的深度为${log_2 n} +1$

分类

二叉树可以分为以下几种：

• 二叉树：每个节点最多含有两个子树的树称为二叉树；

• 二叉查找树(BST)：首先它是一颗二叉树

  • 若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  • 若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  • 左、右子树也分别为二叉排序树；

  极端情况下会退化为链表

• 满二叉树：叶节点除外的所有节点均含有两个子树的树被称为满二叉树，包含$2^k-1$个节点；

• 完全二叉树：如果一颗二叉树除去最后一层节点为满二叉树，且最后一层的节点依次从左到右分布

• 霍夫曼树(最优二叉树)：带权路径最短的二叉树，又称最优二叉树。

• 红黑树：红黑树是一颗特殊的二叉查找树，每个节点都是黑色或者红色，根节点、叶子节点是黑色。如果一个节点是红色的，则它的子节点必须是黑色的，且从根节点到某个无子节点或者只有一个子节点的元素的所有路径中，黑色元素的数量必须相同

  通过引入红黑节点，舍弃了AVL严格的平衡，旋转次数会有所减少，但是由于二叉树可能数比较高，IO次数比较多，所以在磁盘场景中会使用B树

• 平衡二叉树（AVL）：符合二叉查找树的定义，且满足

  • 一棵空树或它的左右两个子树的高度差的绝对值不超过1
  • 左右两个子树都是一棵平衡二叉树，通过左旋和右旋来得到插入或更新后树的平衡性

  旋转比较耗时，删除数据时效率比较低，在删除操作较多时，性能可能会比较差，所以用红黑树比用AVL多

二叉树的存储方式

顺序存储(使用数组)

利用满二叉树的特性，每层节点数分别为1、2、4…$2^{i-1}$，只需要创建一个长度为$2^i-1$的数组就可以存储，但是并不是所有的二叉树都是满二叉树，所以会有一些位置空着，造成了空间浪费

public class ArrayBinTree<T> {
    
    private T[] datas;
    // 深度
    private int deep;
    
    private int arraySize;
    
    public ArrayBinTree(int deep) {
        this.deep = deep;
        arraySize = (int)Math.pow(2, deep) - 1;
        datas = (T[]) new Object[arraySize];
    }

    /**
     * 
     * @param index 父节点的索引位置
     * @param data
     * @param left 是否为左子树
     */
    public void add(int index,T data,boolean left){
        if(datas[index] == null)
            throw new RuntimeException("节点为空，无法添加子节点");
        if(2 * index + 1 >= arraySize)
            throw new RuntimeException("添加子节点超出数组容量");
        if(left){ // 左子节点
            datas[2 * index + 1] = data;
        } else {
            datas[2 * index + 2] = data;
        }
    }
    
}

链表存储

public class LinkBinTree<E> {
    static class TreeNode<E>{
        E data;
        TreeNode<E> left;
        TreeNode<E> right;

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

        public TreeNode(E data, TreeNode<E> left, TreeNode<E> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }

    // 根节点
    private TreeNode<E> root;
    public LinkBinTree(E root) {
        this.root = new TreeNode<>(root);
    }

    /**
     *
     * @param parent 父节点
     * @param data
     * @param left 是否为左节点
     * @return
     */
    public TreeNode<E> add(TreeNode<E> parent,E data,boolean left) {
        if(parent == null)
            throw new RuntimeException("节点为空，不可添加子节点");
        if(left && parent.left != null)
            throw new RuntimeException("左子节点已存在，不可添加");
        if(!left && parent.right != null)
            throw new RuntimeException("右子节点已存在，不可添加");
        TreeNode<E> newNode = new TreeNode<>(data);
        if(left){
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }
        return newNode;
    }
}

链表的存储方式在遍历树节点时效率不高，获取父节点也比较困难，可以在TreeNode中加上parent的引用

static class TreeNode<E>{
        E data;
        TreeNode<E> left;
        TreeNode<E> right;
                TreeNode<E> parent;
        
    }

这样就使得每个节点除了可以向下访问节点，也可以向下访问节点

遍历方式

如果使用数组存储二叉树的话，遍历二叉树比较容易，直接遍历底层数组即可。如果采用的是链表存储的话，有两类遍历方式：深度优先遍历和广度优先遍历

深度优先遍历

先访问到树中最深层次的节点

深度优先遍历的遍历算法其实我们经常会听到就是大学的时候学的

L表示左子树，D表示根，R表示右子树

• 前序遍历DLR：遍历顺序为 根节点->左子树->右子树
• 中序遍历LDR：遍历顺序为 左子树->根节点->右子树
• 后序遍历LRD：遍历顺序为 左子树->右子树->根节点

前序遍历

• 先访问根节点
• 递归遍历左子树
• 递归遍历右子树

/**
 * 前序遍历
 * @return
 */
public List<TreeNode<E>> preIterator(){
    return preIterator(root);
}

public List<TreeNode<E>> preIterator(TreeNode<E> root){
    List<TreeNode<E>> list = new ArrayList<>();
    if(root!= null){
        list.add(root);

        if(root.left != null){
            list.addAll(preIterator(root.left));
        }

        if(root.right != null){
            list.addAll(preIterator(root.right));
        }
    }

    return list;

}

中序遍历

• 递归遍历左子树
• 访问根节点
• 递归遍历右子树

/**
 * 中序遍历
 *
 * @return
 */
public List<TreeNode<E>> inIterator() {
    return inIterator(root);
}

public List<TreeNode<E>> inIterator(TreeNode<E> root) {
    List<TreeNode<E>> list = new ArrayList<>();
    if (root != null) {
        if (root.left != null) {
            list.addAll(inIterator(root.left));
        }

        list.add(root);

        if (root.right != null) {
            list.addAll(inIterator(root.right));
        }
    }

    return list;

}

后序遍历

• 递归遍历左子树
• 递归遍历右子树
• 访问根节点

/**
 * 后序遍历
 *
 * @return
 */
public List<TreeNode<E>> postIterator() {
    return postIterator(root);
}

public List<TreeNode<E>> postIterator(TreeNode<E> root) {
    List<TreeNode<E>> list = new ArrayList<>();
    if (root != null) {
        if (root.left != null) {
            list.addAll(postIterator(root.left));
        }


        if (root.right != null) {
            list.addAll(postIterator(root.right));
        }

        list.add(root);
    }

    return list;

}

广度优先遍历

逐层访问每层的节点，为了实现广度优先遍历，需要使用队列来实现。实现步骤

• 把树的根节点压入队列
• 从队列中弹出一个节点(第一次弹出的是根节点)，然后把该节点的左右节点压入队列，如果没有子节点，说明已经到达叶子节点了
• 重复上述步骤

/**
 * 广度优先遍历
 *
 * @return
 */
public List<TreeNode<E>> breadthFirst() {
    Queue<TreeNode<E>> queue = new ArrayDeque<>();

    List<TreeNode<E>> result = new ArrayList<>();

    if (root != null) {
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode<E> node = queue.poll();
            result.add(node);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

    return result;
}