完全二叉树的度为多少?

发布网友发布时间：2023-05-25 00:07

共1个回答

热心网友时间：2023-08-30 11:01

n0＝（n＋1）/2

设：度为i的结点数为ni，由二叉树的性质可知：

n0 = n2 + 1……………………①式

n = n0 + n1 + n2……………②式

由①式可得 n2 = n0 - 1，带入②式得：

n0 = （n + 1 - n1）/ 2

由完全二叉树性质可知：

如图，当n为偶数时，n1 = 1， n0 = n / 2

如图，当n为奇数时，n1 = 0，n0 = （n + 1）/2

将两式合并，写作：n0 = ⌊（n+1）/2⌋（向下取整符号不能丢）

二叉树的存储结构

按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排列为一个线性序列。在该序列中，除第一个结点外，每个结点有且仅有一个直接前驱结点；除最后一个结点外，每个结点有且仅有一个直接后继结点。

但是，二叉树中每个结点在这个序列中的直接前驱结点和直接后继结点是什么，二叉树的存储结构中并没有反映出来，只能在对二叉树遍历的动态过程中得到这些信息。为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息，可以利用二叉树的二叉链表存储结构中的那些空指针域来指示。