树的存储形式有哪几种

好酷屋

发布于2023-04-11

标签:结点表示法双亲孩子单链更多>

好酷屋教程网小编为您收集和整理了树的存储形式有哪几种的相关教程：品牌型号：lenovoThinkPadX250系统：Windows11软件版本

品牌型号：lenovo ThinkPad X250系统：Windows 11软件版本:

树的存储形式有双亲表示法、孩子表示法、孩子兄弟表示法。

双亲表示法的特点：由于根结点是没有双亲的，约定根结点的位置位置域为-1。根据结点的parent指针很容易找到它的双亲结点。所用时间复杂度为O(1)，直到parent为-1时，表示找到了树结点的根。缺点：如果要找到孩子结点，需要遍历整个结构才行。

孩子表示法定义：把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。

双亲孩子表示法定义：对于孩子表示法，查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。但是当要寻找某个结点的双亲时，就不是那么方便了。所以可以将双亲表示法和孩子表示法结合，形成双亲孩子表示法。

以上就是好酷屋教程网小编为您收集和整理的结点,双亲,位置,孩子,复杂度相关内容，如果对您有帮助，请帮忙分享这篇文章^_^

本文来源： https://www.haoku5.com/shuma/6435000d98233a5d4801ea4a.html

相关推荐