数据结构_知识点_树的存储结构

树的存储结构

(1) 双亲表示法，每个结点设置指针域指向其双亲，根节点指针域为空或-1
（可以快速找到双亲结点，找结点的孩子结点需要遍历整个结构</br>
(2) 孩子表示法

I. 定长结点
     　即树中每个结点均按树的度k来设置指针。
    　 n个结点的树一共有n*k个指针域，而树中只有n-1条边，故树中的空指针数目为
       k*n-(n-1)=n*(k-1)+1（k越大，浪费的空间越多）。

II. 不定长结点
      即树中每个结点按本结点的度来设置指针数，并在结点中增设一个度数域degree
      指出该结点包含的指针数。
    　各结点不等长，虽然节省了空间，但是给运算带来不便，需要维护多个结点。

III. 孩子链表表示法
      为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。
      此法最佳

Paste_Image.png

(3) 孩子兄弟表示法

又称二叉树表示法，指针域分为两部分，第一个孩子结点和下一兄弟结点

Paste_Image.png

Paste_Image.png