线性四叉树数据结构（数据结构二叉树）

树的定义

树是由n（n≥0）个结点组成的有限集合（记为T）。

如果n=0，它是一棵空树，这是树的特例。

如果n>0，这n个结点中存在（有仅存在）一个结点作为树的根结点（root），其余结点可分为m（m≥0）个互不相交的有限集T1、T2、…、Tm，其中每个子集本身又是一棵符合本定义的树，称为根结点的子树。

树是一种非线性数据结构，具有以下特点：

每一结点可以有零个或多个后继结点，但有且只有一个前驱结点（根结点除外）。

数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。

抽象数据类型树的描述

树的逻辑结构表示方法

树形表示法。这是树的最基本的表示，使用一棵倒置的树表示树结构，非常直观和形象。

文氏图表示法。使用集合以及集合的包含关系描述树结构。

凹入表示法。使用线段的伸缩关系描述树结构。

括号表示法。将树的根结点写在括号的左边，除根结点之外的其余结点写在括号中并用逗号分隔。

列表表示法。 "[根结点，子树1，子树2，…，子树m]"。

树的基本术语

结点的度。树中每个结点具有的子树数或者后继结点数称为该结点的度。

树的度。树中所有结点的度的最大值称之为树的度。

分支结点。度大于0的结点称为分支结点或非终端结点。度为1的结点称为单分支结点，度为2的结点称为双分支结点，依次类推。

叶子结点（或叶结点）。度为零的结点称为叶子结点或终端结点。

孩子结点。一个结点的后继称之为该结点的孩子结点。

双亲结点（或父亲结点）。一个结点称为其后继结点的双亲结点。

子孙结点。一个结点的子树中除该结点外的所有结点称之为该结点的子孙结点。

祖先结点。从树根结点到达某个结点的路径上通过的所有结点称为该结点的祖先结点（不含该结点自身）。

兄弟结点。具有同一双亲的结点互相称之为兄弟结点。

结点层次。树具有一种层次结构，根结点为第一层，其孩子结点为第二层，如此类推得到每个结点的层次。

树的高度。树中结点的最大层次称为树的高度或深度。

森林。零棵或多棵互不相交的树的集合称为森林。

树的性质

性质1： 树中的结点数等于所有结点的度数加1。

性质2：度为m的树中第i层上至多有mi-1个结点，这里应有i≥1。

数学归纳法证明

当一棵m次树的第i层有mi-1个结点（i≥1）时，称该层是满的，若一棵m次树的所有叶子结点在同一层，并且每一层都是满的，称为满m次树。显然，满m次树是所有相同高度的m次树中结点总数最多的树。

也可以说，对于n个结点，构造的m次树为满m次树或者接近满m次树，此时树的高度最小。

若一棵三次树中度为3的结点为2个，度为2的结点为1个，度为1的结点为2个，则该三次树中总的结点个数和度为0的结点个数分别是多少？

树的基本运算

树的运算主要分为三大类：

查找满足某种特定关系的结点，如寻找当前结点的双亲结点等；

插入或删除某个结点，如在树的当前结点上插入一个新结点或删除当前结点的第i个孩子结点等；

遍历树中每个结点。

树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。

有以下3种遍历方法：

先根遍历

若树不空，则先访问根结点，然后依次先根遍历各棵子树。

后根遍历

若树不空，则先依次后根遍历各棵子树，然后访问根结点。

层次遍历

若树不空，则自上而下自左至右访问树中每个结点。

注意：先根和后根遍历算法都是递归的。

树的存储结构

双亲存储结构

这种存储结构是一种顺序存储结构，用一组连续空间存储树的所有结点，同时在每个结点中附设一个伪指针指示其双亲结点的位置。

双亲存储结构

利用了每个结点（根结点除外）只有唯一双亲的性质。

这种存储结构中，求某个结点的双亲结点十分容易，但求某个结点的孩子结点时需要遍历整个结构。

例子：若一棵树采用双亲存储结构t存储，设计一个算法求指定索引是i的结点的层次。

孩子链存储结构

个结点包含结点值和所有孩子结点指针，可按一个结点的度设计结点的孩子结点指针个数

孩子链存储结构

优点是查找某结点的孩子结点十分方便。

缺点是查找某结点的双亲结点比较费时。

若一棵树采用孩子链存储结构t存储，设计一个算法求其高度

解：一棵树的高度为根的所有子树高度的最大值加1。求整棵树的高度为"大问题"，求每棵子树高度为"小问题"。设f(t)为求树t的高度，对应的递归模型如下：

长子兄弟链存储结构

长子兄弟链存储结构是为每个结点设计三个域：一个数据元素域，一个指向该结点的长子的指针域，一个指向该结点的下一个兄弟结点指针域。

长子兄弟链存储结构

优点是查找某结点的孩子结点十分方便。

缺点是查找某结点的双亲结点比较费时。

若一棵树采用长子兄弟链存储结构t存储，设计一个算法求其高度。

解：一棵树的高度为根的所有子树高度的最大值加1。求整棵树的高度为"大问题"，求每棵子树高度为"小问题"。设f(t)为求树t的高度，对应的递归模型如下：

列表存储结构

将树的列表表示（树的逻辑表示法之一）直接采用Python中的列表数据类型表示，称为树的列表存储结构。

若一棵树采用列表存储结构t存储，设计一个算法求其高度。 解：一棵树的高度为根的所有子树高度的最大值加1。求整棵树的高度为"大问题"，求每棵子树高度为"小问题"。设f(t)为求树t的高度，对应的递归模型如下：

,