概述

• 树的最大度为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$$

二叉树的构建

和链表一样，我们嵌套定义一个私有类 Node 来表示二叉树上的每一个结点，每个结点都含有数据域+左孩子指针+右孩子指针，以链式方式构建二叉树。

代码

private class Node {
    Item item;
    Node left;
    Node right;
}

构造二叉树

Node root = new Node();
root.item = 'A';

Node second = new Node();
second.item = 'B';

Node third = new Node();
third.item = 'C';

root.left = second;
root.right = third;