数据结构历年考研真题对应知识点（二叉树的概念）
目录
【完全二叉树中结点数和叶结点数的关系（2009、2011、2018）】
5.2二叉树的概念
5.2.1二叉树的定义及其主要特征
【完全二叉树中结点数和叶结点数的关系（2009、2011、2018）】
完全二叉树。高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树，如图 5.3(b)所示。其特
点如下:
① 若 （向下取整符），则结点i为分支结点，否则为叶结点。
②叶结点只可能在层次最大的两层上出现。对于最大层次中的叶结点，都依次排列在该层最左边的位置上。
③ 若有度为1的结点，则最多只可能有一个，且该结点只有左孩子而无右孩子。
④ 按层序编号后，一旦出现某结点(编号为i)为叶结点或只有左孩子，则编号大于i的结点均为叶结点。
⑤ 若n为奇数，则每个分支结点都有左孩子和右孩子:若n为偶数，则编号最大的分支结点(编号为n/2)只有左孩子，没有右孩子，其余分支结点左、右孩子都有。
【正则k叉树树高和结点数的关系的应用（2016）】
正则二叉树。树中每个分支结点都有2个孩子，即树中只有度为0或2的结点。
5.2.2二叉树的存储结构
【特定条件下二叉树树形及占用存储空间的分析（2020）】
但对于一般的二叉树，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点，让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中。
然而，在最坏情况下，一个高度为h且只有h个结点的单支树却需要占据近 个存储单元。二叉树的顺序存储结构如图5.4所示，其中0表示并不存在的空结点。
注意：建议从数组下标1开始存储树中的结点，保证数组下标和结点编号一致。
原文地址：https://blog.csdn.net/qq_64017312/article/details/140295851
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！