数据结构历年考研真题对应知识点（二叉树的概念）

最编程 2024-07-10 10:43:38

...

5.2二叉树的概念

5.2.1二叉树的定义及其主要特征

【完全二叉树中结点数和叶结点数的关系（2009、2011、2018）】

【正则k叉树树高和结点数的关系的应用（2016）】

5.2.2二叉树的存储结构

【特定条件下二叉树树形及占用存储空间的分析（2020）】

5.2二叉树的概念

完全二叉树。高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树，如图 5.3(b)所示。其特
点如下:

① 若 $i\leqslant \left \lfloor n /2 \right \rfloor$ （向下取整符），则结点i为分支结点，否则为叶结点。

②叶结点只可能在层次最大的两层上出现。对于最大层次中的叶结点，都依次排列在该层最左边的位置上。

③ 若有度为1的结点，则最多只可能有一个，且该结点只有左孩子而无右孩子。

④ 按层序编号后，一旦出现某结点(编号为i)为叶结点或只有左孩子，则编号大于i的结点均为叶结点。

⑤ 若n为奇数，则每个分支结点都有左孩子和右孩子:若n为偶数，则编号最大的分支结点(编号为n/2)只有左孩子，没有右孩子，其余分支结点左、右孩子都有。

正则二叉树。树中每个分支结点都有2个孩子，即树中只有度为0或2的结点。

但对于一般的二叉树，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点，让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中。

然而，在最坏情况下，一个高度为h且只有h个结点的单支树却需要占据近 $2^{h}-1$ 个存储单元。二叉树的顺序存储结构如图5.4所示，其中0表示并不存在的空结点。

注意：建议从数组下标1开始存储树中的结点，保证数组下标和结点编号一致。