[TOC]

二叉树

参考文档:

百度百科

https://www.jianshu.com/p/bf73c8d50dc2

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

1、定义

二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。 [1]

2、特点

1. 每个节点最多有两棵子树，即两个子节点。
2. 左子树和右子树是有顺序的，次序不能任意颠倒
3. 即使树中某节点只有一颗子树，也要区分他是左子树还是右子树

3、性质

在二叉树的第i层上最多有 2的（i-1）次方个节点。（i>=1）
二叉树中如果深度为k，那么最多有2的k次方-1个节点（i>=1）
n0 = n2 + 1 n0表示度数为0的节点数，n2表示度数为2的节点数。

证：假设该二叉树总共有n个结点(n=n0+n1+n2)，则该二叉树总共会有n-1条边，度为2的结点会延伸出两条边，同理，度为1的结点会延伸出一条边，则可列公式：n-1 = 2n2 + 1n1 合并两个式子可得：2n2 + 1n1 +1 =n0 + n1 + n2 ，则计算可知 n0=n2+1。

n0 = n2 + 1 n0表示度数为0的节点数，n2表示度数为2的节点数。

4、分类

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

满二叉树的特点有：

- 叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
- 非叶子结点的度一定是2。
- 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
- 满二叉树一定是完全二叉树
完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

特点：

- 叶子结点只能出现在最下层和次下层。
- 最下层的叶子结点集中在树的左部。
- 倒数第二层若存在叶子结点，一定在右部连续位置。
- 如果结点度为1，则该结点只有左孩子，即没有右子树。
- 同样结点数目的二叉树，完全二叉树深度最小。
平衡二叉树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。
二叉排序树 当二叉树有一定顺序的时候它就是二叉排序树。

特点：

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

5、遍历表达法

- - 先序遍历：先访问根节点，再访问左子树，最后访问右子树。 ABDECF
  - 中序遍历：先左子树，再根节点，最后右子树。DBEAFC
  - 后序遍历：先左子树，再右子树，最后根节点。DEBFCA
  - 层序遍历：每一层从左到右访问每一个节点。ABCDEF
```
  前面三种是深度优先遍历 ，最后一种是广度优先遍历
```

6、二叉树的存储结构

1、数组

二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。当二叉树为完全二叉树时，结点数刚好填满数组。

那么当二叉树不为完全二叉树时，出现空间浪费

2、链表

7、代码实现

1、完全二叉树

package com.ss.study.tree.binary;

import lombok.Data;

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

/**
 *  完全二叉树
 * @author xia17
 * @date 2019/12/18 15:25
 */
public class CompleteBinaryTree<T> {

    /**
     * // 父节点
     */
    private BinaryNode<T> root;
    private int maxIndex;
    private int level ;
    /**
     * 所有节点
     */
    private List<BinaryNode<T>> nodes = new ArrayList<>();

    public void add(T value){
        BinaryNode<T> node  = new BinaryNode<>(value);
        if (root == null){
            root = node;
        }else {
            BinaryNode<T> father ;
            // 是添加左节点 还是有节点
            if (maxIndex % 2 == 0){
                father = nodes.get(level - 2);
                father.setRight(father);
            }else {
                father = nodes.get(level - 1);
                father.setLeft(father);
            }
            node.setFather(father);
        }
        node.setIndex(++maxIndex);
        // level
        if (maxIndex > (1 << level) - 1 ){
            node.setLevel(++level);
        }else {
            node.setLevel(level);
        }
        nodes.add(node);
    }


    public static void main(String[] args) {
        CompleteBinaryTree<Integer> tree = new CompleteBinaryTree<>();
        tree.add(1);
        tree.add(2);
        tree.add(3);
        tree.add(4);
        tree.add(5);
        System.out.println();
    }

}

@Data
class BinaryNode<T> {

    public BinaryNode( T value){
        this.value = value;
    }

    private BinaryNode<T> left ;
    private BinaryNode<T> right;
    private BinaryNode<T> father;
    private int index;
    private int level;
    private T value;


    @Override
    public String toString(){
        return value.toString();
    }
}