树

树在逻辑上是一对多的关系，是一种非线性结构。
树：是n（n>=0）个有限结点的集合。n=0时称为空树。在任意一棵非空树中：（1）有且只有一个特定的称为根（Root）的结点；（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、T3、……、Tm，其中每一个集合本身又是一棵树，并称为根的子树（SubTree）。如图：

结点的分类

结点拥有的子树数称为节点的度（Degree 意思就是和节点有直接连线的结点有几个，度就是几）。度为0的结点称为叶节点（Leaf）或终端节点；度不为0的结点称为非终端节点或者分支结点。除根节点外，分支结点也称为内部结点，树的度是树内各结点的度的最大值。

结点间的关系

结点的子树的根称为该结点的孩子（child），相应的，该结点称为孩子结点的双亲结点（Parent）。

注1：孩子结点和双亲结点这种结点间的关系是针对结点之间有直接连线的结点而言的。

同一个双亲的孩子之间互称兄弟（Sibling），结点的祖先是从根节点是从根节点该结点所经分支上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。

结点的层次

结点的层次从根开始定义，根为第一层，根的孩子为第二层，孙子为第三层，以此类推。对某几个结点，如果其双亲在同一层，那么这些结点（双亲不同）互为堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度。

如果将树中结点的各子树看成从左到右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

森林（Forest）是m（m>=0）棵互不相交的树的集合。

树的存储结构

顺序存储结构和链式存储结构。

注1：从开始学习数据结构开始，就讲过存储结构只分顺序存储和链式存储两种。实际上，任何一种数据结构都可以采用这两种存储方式实现存储，关键就在于如何设计结点，正确的结点设计能够使我们用任意一种存储结构将数据结构在内存中表示出来。具体采用哪种存储结构：主要考虑这种存储结构下是否可以方便的实现我们所要求的运算，数据结构间的运算一般来说是逻辑上的运算，即算法，而非实际意义上的算数运算，但是如果要重载运算符，最好不要去违背运算符的约定俗成的含义，一定要那么做也要给出说明，以及预期的运算结果（就是示例）。什么叫方便呢？我觉得分三个方面，一是考虑在这种存储结构下，是否会造成空间上的浪费；二是考虑在此存储结构下，对大数据量、数据量变化较大时的支持；三是考虑在此种存储结构下，算法的效率问题（即算法的时间复杂度）。另外，我们不能把思维局限在选择使用单一的存储结构来表示一个数据结构，在内存中表示树的时候我们将会有所体会。

注2：任何数据结构都应该提供的基本操作，按实现的难易程度来区分：
– 构造这个数据结构
存储结构是在微观上表示如何在计算机内存中表示这个数据结构，而构造数据结构，则是在逻辑层面上表示数据结构的实现细节。
– 插入
插入操作是整个数据结构中最重要的运算，它实际上体现的是如何在当前存储结构下在逻辑层面正确的体现数据元素与数据元素之间的逻辑关系（线性和非线性），其关键之处在于如何使指针或者游标正确的移动，当然还需要考虑怎么排除特殊结点的异化，这方面头结点就是很好的例子。
– 删除
删除操作排第三，是因为我们必须要考虑怎样在做完删除操作之后依然保证数据结构的正确性。
（这时我们可能需要考虑一些特殊情况，比如特殊结点，尾结点、头结点，数据结构中无数据）
– 查找
以线性表为例吧，查找操作都需要从头指针开始，顺序向下查找，查找本身不会改变数据结构，所以唯一需要注意的点就是什么时候表示数据结构的结束（例如，链表的尾结点指针域值为nullptr）。
– 清除元素
清除的含义不是销毁数据结构，而是删除当前实例（对象）中存储的元素，在清楚操作执行完后，数据结构无需再次构造依然可以正确执行它所支持的所有操作，清楚操作，本质上来说是和查找有相似之处的，唯一不同的是它会清空数据结构中存储的数据元素，让一切回归起点。
– 析构
析构才是真正的销毁数据结构，为了保证异常安全，最好的做法是在构造对象时即构造出这个数据结构的实例，在析构时销毁。析构函数是最简单的，因为，对有些数据结构执行完清除操作后，只需执行一两步操作就能释放资源了（对链式存储结构）。

注3：在编码实现时需要主要的点：
-确保指针的每一次移动都是正确的
– 注意数据结构的终止条件（这一点对理解递归同样重要，当然，在理解递归时还需要理清楚函数的调用链以及它是如何返回到上一层调用的）

注4：数据结构和类的区别
数据结构是指在数据元素之间满足一种或多种关系的数据元素的集合（这里的数据元素它们并不在一个类里面，你可以用数学上的集合去理解这个关系）。数据元素之间的逻辑关系只有线性和非线性两种，也就是说这个集合中的数据之间的关系都是可以描述清楚的，而不是模棱两可的，这是它和类的另一个区别，另外，从本质上来说类和数据结构是也是不同的，从某种意义上来说，数据结构是类的一个子集，数据结构可以用类来表示，但是并不是所有的类都是数据结构。所以它们根本是两个概念。

树的存储结构——-双亲表示法

抛开具体的存储结构说说思想：
双亲表示法的想法来源是：每个孩子都知道自己的父母是谁，所以在设计结点的时候，结点数据结构显然要包含两部分的内容，数据域+指针域，其中指针指向双亲结点，如果采用顺序存储结构，那么指针域中存储的就是双亲结点在数组中的位置，因为根节点没有双亲结点，所以指针域的值为-1,（链式结构就是空指针了）。当然你还可以在这个结点里加是上一个表示右兄弟域来表示兄弟关系（右兄弟域中存储，当前结点的右兄弟，如果右兄弟不存在那么值为-1或者空指针）

树的存储结构——孩子表示法

双亲都会知道自己的孩子是谁。所以每个结点都有多个指针域，其中每个指针指向一棵子树的根节点，我们把这种方法叫做多重链表表示法。多重链表的方法，可以是指针域的数目为树的度，那么这种表示法的问题就在于，当结点的度相差很大是会浪费空间。实现多重链表表示法的另一种方案是，在每个结点中增加一个位置用来存储度，那么每个结点的度是几，这个结点就有几个指针域。但是因为每个结点的度是不同的，维护度就会带来运算上的时间开销。

实现多重链表的第三种方案，也是比较好的一种，就是孩子表示法：把每个结点的孩子结点排列起来，以单链表作存储结构，则n个节点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组里。对这种表示方案有两种结点，一个是孩子链表的孩子结点：包括数据域和指针域，数据域用来存储某个结点想的一个孩子在表头数组中的下标，指针域则存储指向某结点下一个孩子在表头数组中的下标。另一个结点结构是表头数组的结点，包含两部分，一是数据域，存储某结点的数据信息，另一个是头指针域，存储该结点的孩子链表的头指针。这种方法的缺陷是，如果要知道某个结点的双亲结点是谁，需要遍历整棵树。解决方法是，表头结点增设一个域表明当前结点的双亲结点在头数组中的下标。这叫双亲孩子表示法。

树的存储结构——孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的，所以，可以设置两个指针，分别指向该结点的第一个孩子和此节点的右兄弟。当然还可以再增设一个指针域，指向当前结点的双亲结点。孩子兄弟表示法的优势在于，它能把一棵复杂的树变成二叉树，那么我们就可以利用二叉树的性质和算法来处理这棵树了。