完全二叉树用什么数据结构实现最合适,为什么?

qfwu · 2018-4-30 01:58:04

一般的二叉树用带有两个指向自身结构类型变量的指针的多个结构体组成最合适。
如果该二叉树不会变化，可以用数组实现，每个数组元素表示一个节点，因为是完全的，所以长度一定是2的n次方-1，n为树的深度，也可以很方便地算出某个元素与树根节点、父节点等的关系，因此不用指针反而可以减少存储开销及查询效率。

liucong07170 · 2018-4-30 01:58:05

数组。完全二叉树按照从上到下，从左到右为每个叶子编码则n个节点分别是1,2,3，4。。。。n
然后 n的父节点是n/2，n的做孩子是2*n n的右孩子是2*n+1假设孩子都存在，所以可以很方便的算各种东西，用数组储存节省空间，而且便于操作。

likai19920612 · 2018-4-30 01:58:06

用数组就行

富国基金基金 · 2018-4-30 01:58:07

首先明确，所谓『完全二叉树』，是指『每一层符合2^n个结点的树』，从对称性看它十分对称。既然这么对称，那也就意味着它很容易被干扰而变得不再对称！所以我们看到的满二叉树通常是根据特定数据集合构造出来的静态查找树，也就是薯片它一旦被构造出来就基本上定型不变了（如果要变也是等到时机成熟，一动一大把……接着构造一棵新的完全二叉树）——
所以，我建议你使用顺序存储，也就是用数组。=======================================
『静态』的查找树，它们的唯一使命就是『查找』。

完全二叉树用什么数据结构实现最合适,为什么?

4 个回复

浏览过的版块