数据结构（六）

这是数据结构的第6篇文章

hello，上次给大家讲完了栈，是不是很简单呢？栈的操作基本上变化性较少，也就是操作比较简单，最常用的栈的操作就是计算器的实现，这个计算器的具体实现还需要学习到中缀表达式转变后缀表达式再使用两个栈才能完成，有空再给大家完成一个试试！

那么今天开始讲一下树。

为什么要学习树？ 请看！！

对于向量来说，查找的过程效率极高，然而它的动态操作如：插入和删除的效率就显得特别低下，对比列表，正好相反。

也就是说，有没有一个数据结构能够综合两者的优点呢？也就是带有一定的线性特征，而又不是狭义的线性结构。

那就是Tree！

什么是树

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

每个结点有零个或多个子结点；没有父结点的结点称为根结点；没有子节点的节点称为叶子节点，每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。——百度。

有序树：若指定Ti为T的第i棵子树，ri为第i个孩子，则T称为有序树。

更好的理解，可以想像以前学过的遗传图谱，就是由两棵或者多棵树组成的森林。

这里讲一下路径，就是由一个节点到另外一个节点的路径，路径有一条条边组成，路径的长度就是经过的边数，特殊的路径即是环路，起点指向终点。如下图。

看下图，我们显而易见，从任何一个子节点到根节点的路径是唯一的。

那么如果我们考察某一节点的深度depth，就可以直接考察由该节点出发到叶子节点的路径path，于是就将路径path与深度depth结合起来了。

而从根节点到某一结点上经过的任意一结点都称为某一结点的祖先（ancestor）（祖先包括自身，真祖先不包括自己）。例如对于叶子节点J来说，A,E,C,J都是祖先，其中A、E、C称作节点J的真祖先。同样，J是A,C,E,J的后代（同理，也有真后代）。

那么有显而易见，除了根节点以外的任意一节点，他们的祖先必然是唯一的，但是后代未必唯一！

也就是说，前驱唯一，而后继不一定唯一！由于这个性质，树也就不是线性结构。

再看图二的树，整棵树的高度大于等于某一结点v的深度和高度之和。

接口

首先根节点作为整棵树的入口，便于我们对树的操作。

其次，对于任何节点，我们都需要便捷的找到他的父亲节点和最大的孩子（长子节点）。

然后，既然是有序树，那么兄弟之间就有顺序，于是要便捷的找到下一个兄弟节点。

查询操作完了后，就需要提供对树的动态修改操作，插入和删除节点。

当然也免不了对树的遍历（前序、中序、后序）。

父亲节点法

那么我们的父节点怎么表示呢？

我们可以很明确的知道，父节点要么不存在，要么只存在一个，因此，我们只需要记录好每个节点的父节点的位置就可以找到对应的父节点，其中根节点不存在父节点，因此我们会设根节点的父节点位置为-1。

如上图，R为根节点，可以在旁边的表中看到R的parent为-1，同时，对于G,H,K节点来说，他们的父亲节点都是F，所以他们的parent标记为6，也就是F的位置。

然而这种方式向上节点查找很简单，而向下查找就很困难。

孩子节点法

那么，我们能否把孩子节点放在一个数据集里呢？答案是肯定的。

如下图，我们可以分出一个children域来存放孩子节点的数据集，这样一方面可以方便孩子节点之间的有序性排列，另一方面也可以方便对孩子节点进行管理。当然，这种数据集可以使用向量，或者是链表。

然而这种方式向下查找很简单，但是向上查找就十分困难。

父亲节点+孩子节点

因此我们不难想到将他们两者的优势结合。

对同一个序列不仅存储他的parent，也保存他的children。

但是由于这里的孩子数据集不能确定它的长度，难以实现O（n）的数据集，因此我们需要找到新的办法去改进。

长子+兄弟

那么我们怎么进行改进呢？

我们可以想到，向下的查询，我们可以使用寻找长子作为纵向查找，寻找兄弟作为横向查找。

从而我们只用关心长子和兄弟即可，也就是说我们只需要对每个节点记录长子和兄弟两个索引就好了。

总结

1、今天的话呢主要是想把整体的树的思路整理一下，并不是说全是干货，不是说直接上来就介绍父子节点树，而是整理了一下思维的过程。我只能说这样学收获颇多。

2、上文中的图片均来自邓俊辉《数据结构MOOC》，有兴趣的可以自己找一下来看看。在这里也感谢邓俊辉老师，真的是强。