概述

• 树的最大度为2；
• 分左右子树；

特殊二叉树

斜树

• 左斜树：所有结点都只有左子树的二叉树
• 右斜树：所有结点都只有右子树的二叉树

满二叉树

• 所有结点的度为 2
• 所有叶子结点都在同一层

完全二叉树

有 n 个结点的二叉树，对树中结点按从上至下、从左到右顺序进行编号，编号为 i (1< = i < = n) 结点与满二叉树中 编号为 i 结点在二叉树中位置相同

n 个结点的完全二叉树的结点父子关系：

• 非根结点（序号 i > 1）的父结点的序号是 i/2
• 结点（序号为 i）的左孩子结点的序号是 2i。若 2i >= n，则没有左孩子。如 i 为 6 的结点，就符合没有左孩子。
• 结点（序号为 i）的右孩子结点的序号是 2i + 1。若 2i + 1 >= n，则没有右孩子。如 i 为 6 的结点，就符合没有右孩子。

  二叉树的性质

  
• 一个二叉树第 i 层的最大结点数为： $$2^{i-1}$$，$$i \geq1$$
• 深度为 K 的二叉树有最大结点总数为：$$2^{k}-1$$，$$k \geq1$$
• 对任何非空二叉树 T，若 $$n{0}$$ 表示叶结点的个数，$$n{1}$$ 是度为 1 的非叶结点个数，$$n_{2}$$ 是度为 2 的非叶结点个数，那么满足关系 : $$n_0=n_2+1$$
  • $$n_{0} = 4$$ （D、J、K、H）
  • $$n_{2} = 3$$ （A、B、E）
  • $$n_0=n_2+1$$

二叉树的存储结构

顺序存储结构

顺序存储，也就是数组存储。这种存储方式，在完全二叉树下，不会浪费空间，但是在一般二叉树下会造成大量的空间浪费。

链表存储

链式存储，方便新增，删除操作，不浪费空间；结构为数据域+左孩子指针+右孩子指针 （二叉链表）。

代码

public class BinaryTreeNode {
    private int data;
    private BinaryTreeNode left;
    private BinaryTreeNode right;

    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }

    public BinaryTreeNode getLeft() {
        return left;
    }
    public void setLeft(BinaryTreeNode left) {
        this.left = left;
    }

    public BinaryTreeNode getRight() {
        return right;
    }
    public void setRight(BinaryTreeNode right) {
        this.right = right;
    }
}