Mythal is on the way

去年在面试MS的时候本问到了一个如何把每个child node添加一个right-sibling指针的题目，当时用层遍历写出来了，后来上网搜发现了一种left-child, right-sibling tree，但是一直不明白为什么会有这种数据结构。

最近在读算法导论Elementary Data Structures这一章的时候，发现了一节专门讲这个问题：

一半的二叉树的node结构是

Parent
Left Child    Right Child

但是如果我们要每一个node有n的children，那这个表示结果效率就很低了。

首先不清出道题有多少个children，即使知道了做大children的数目n，不能保证每个node都有n个children，所以再用上述的表达方式就很浪费空间。这就是left-child, right-sibling tree存在的意思。

先上一个left-child, right-sibling tree的图

从图中，每个node现在只有3个指针

1. left-sibling的指针
2. most left child的指针
3. 指向parent的指针

这样对于一个有n个children的树的结构就能很好的表示出来了。