树常用的三种存储方式

文章插图
树的存储形式有父表示、子表示和子兄弟表示。
亲代表示的特点:因为根节点没有亲代，所以根节点的位置域是-1 。根据一个节点的父指针，很容易找到它的父节点。所用的时间复杂度为O(1)，直到父节点为-1，就意味着找到了树节点的根。缺点:如果想找到子节点，需要遍历整个结构。
子表示的定义:排列每个节点的子节点，以单链表为存储结构，则n个节点有n个子链表。如果是叶节点，这个单链表就是空。然后N个头和指针组成一个线性表，存储在顺序存储结构的一维数组中。
父子表示的定义:对于子表示，要找到某个节点的子节点或者某个节点的兄弟节点，只需要找到这个节点的子节点的单链表。但是要找到一个节点的父节点就没那么方便了。因此，我们可以将父表示和子表示结合起来，形成父子表示。

【树常用的三种存储方式】以上解释了树木常用的三种存储方式。本文到此结束，希望对大家有所帮助。