树状结构的二元树(Binary tree)

2026年09月27日 22:47

有1个网友回答

网友（1）：

二元树(Binary tree)：二元树里每一节点的最大分支度为2。如下右(a)、(b)、(c)。
图(a)称做左斜树(left skew tree)，每一节点的右子树皆为空集合。
图(c)称为满枝二元树(fully binary tree)，含有节点数共为2k-1。
图(b)称为完整二元树(complete binary tree)，节点排列顺序同满枝二元树，但节点数小于2k-1 。
二元哪种的第i阶最多有2i-1个节点。
如果有一n个节点的完整二元树，以循序的方式编号，如上图(c)。则任何一个节点i，1 ≤ i ≤ n，具有以下的特性：
若i = 1，则i为根节点，没有父节点。而i ≠ 1，其父节点为ëi/2û(表小于i/2的最大整数)。
若2i ≤ n，则i的左子节点在2i。但若2i > n，则i没有左子节点。
若2i+1 ≤ n，则i的右子节点在2i+1。但若2i+1 > n，则i没有右子节点。
节点i在第[log2 ]+1阶。