知否知否，如何用树保存家谱

题图.jpg

《知否知否，应是绿肥红瘦》电视里的人物实在太多，像我这种跳集、前后穿插看的，一不当心，就把“老子当成儿子”了，一时好奇，试想如何用数据结构来表示这样复杂的人物关系，先来看看盛老爷一家子：

盛府

看到这样的树状结构，很自然的想到用树来存储，每个结点用个对象来存储：

固定孩子的树.png

由于不可能为每个结点单独设计一个对象（即使设计了编程处理也十分繁琐），于是用来存储孩子的空间是用盛弘或王氏的孩子数来分配的，因为他们的孩子数最大（三个），可是如果哪个子女生了四个孩子，就得扩展每个结点的孩子数，显然这种固定分配的方式无法满足家族扩展的需要，也造成了空间的浪费，见上图中标记的“空”。
其实可以用最简单的二叉树巧妙地处理任意孩子的情况，只需要定义两个规则：

1. 左指针指向第一个孩子。

2. 右指针指向兄弟姐妹。

   
   二叉树存储

如图，实际上兄弟就类似用链表来存储，就不再受数量的限制了。
由于我们转换了思想，就可以用二叉树及两个简单的规则来表示复杂的现实关系，所以

你可以通过简单事情的互动来建立任何程度的复杂任务。
——Unix设计思想

这也正是软件开发真正迷人之处。