【CPP】各种各样的树（1）——二叉森林树

不知不觉过去了这么久，不能再摸了，学校的课程已经到达图的部分了，树的总结再怎么拖也要来写了。

树，一种相当重要的数据结构，由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

这种数据结构可以很方便的进行简单的排序和查找（二叉搜索树），且由于计算机以二进制为底层的原因，将树写为每个结点只有两个分支的二叉树可以达成很多高效的操作如压缩数据（赫夫曼树），为了更高的搜索效率写成的平衡二叉树（红黑树，AVL树），为了方便在树中插入删除写成的树（线索二叉树），各种各样的树各放异彩，学会了就是大圣上树，不会就成了老歪脖子树，还是学会为好。

那么在所有树开始前，决定先来介绍一种比较广泛的树，儿子兄弟表示法的普通树。这种树实际上也是一种二叉树，但是由于它在概念上并不是二叉的，所以决定先来介绍这种树。

先上声明：

主要是要实现儿子与兄弟的分别插入和删除，这样写的树实际上操作并不方便，查找时效率也不高，而且有很多限制，所以其实并不实用，在这只做一个简单的介绍。这种树简单地说就是每个结点都有两个指针的交叉链表，两个指针其中一个指向树的儿子（层次更深的子树）另一个固定指向子树的兄弟（也就是层次相同的子树），如果转换到二叉树中就是左子树为儿子右子树为兄弟了，不过这都是后话。

再上实现：

插入删除部分事实上类似于普通的链表的插入删除，要注意如果删除了某个儿子会导致那个儿子连带那个儿子的兄弟全部被删除，删除某个兄弟会导致那个兄弟对应的儿子被删除。真是残酷的数据结构啊（笑）。

然后是Find函数，由于这个树并不是搜索树，所以为了找到某个元素我们需要遍历一整颗树才能做到。这个Find函数是递归函数，递归地不断寻找，这种写法效率很不如非递归写法，但是好处是更容易阅读，由于这种树本身效率就低下，再使用递归搜索也无伤大雅了（没错我不喜欢这份代码）。

Display函数也是递归式工作，在这里递归地遍历整棵树其实是个不错的选择。

getSize函数是遍历了整棵树来获取了全部元素的总数量。

树有个特别的概念：高度（深度），指从某结点开始，到它的叶子结点（没有后续的结点）为止所经过的度（树枝）数。在有些概念中深度专指从根节点开始计算。高度将在后来要说的AVL树中使用到。

运行结果：

这个系列可能会很长，毕竟要说到的东西还蛮多的，代码暂时先不给出，因为目前存了大概1200行的代码，都是要说到的树的各种实现。自己试试看实现一下为好，大概那份代码大概会不断更新直至感觉这个系列可以暂告一段落再发出，这个系列也可能不会随便结束。树真是一个很深的坑等着人们来跳，但是看着古往今来的大牛们研究出来的种种神奇的树也是一种享受不是吗？