数据结构二叉树基础

数据结构二叉树

一、基本概念

每个结点最多有两棵子树，左子树和右子树，次序不可以颠倒。

性质：

非空二叉树的第 i 层上至多有 $2^{i-1}$ 个元素。

深度为 k 的二叉树至多有 $2^k-1$ 个结点 (k>=1)。

对任何一棵二叉树 T ，如果其终端结点数为 $n_0$ ，度为 2 的结点数为 $n_2$ ，则 $n_0=n2+1$ 。

满二叉树：所有终端都在同一层次，且非终端结点的度数为2。

在满二叉树中若其深度为 k，则其所包含的结点数必为 $2^k-1$ 。

完全二叉树：除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐，即集中在左面的位置上，不能有空位置。

具有 n 个节点的完全二叉树的深度为 $\lfloor \log _2 n \rfloor+1$ ( $\lfloor x \rfloor$ 表示不大于x的最大整数)。

如果对一棵有 n 个节点的完全二叉树（其深度为** $\lfloor \log _2 n \rfloor+1$ **）的结点按层序编号（从第 1 层到第 $\lfloor \log _2 n \rfloor+1$ 层，每层从左到右），对任一结点 i （1 <= i <= n）

有：

如果 i = 1 ，则结点 i 是二叉树的根，无双亲；如果 i > 1 ,则其双亲是结点 $\lfloor i/2 \rfloor$ 。

如果 2i > n，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子是节点 2i 。

如果 2i + 1 > n ，则结点 i 无右孩子；否则其右孩子是结点 2i + 1 。