站长百度,游戏网站建设公司,长沙网站制作案例,如何给网站做防盗链数据结构的树存储结构 之前介绍的所有的数据结构都是线性存储结构。本章所介绍的树结构是一种非线性存储结构#xff0c;存储的是具有“一对多”关系的数据元素的集合。 (A) (B)
图 1 树的示例 图 … 数据结构的树存储结构 之前介绍的所有的数据结构都是线性存储结构。本章所介绍的树结构是一种非线性存储结构存储的是具有“一对多”关系的数据元素的集合。 (A) (B)
图 1 树的示例 图 1(A) 是使用树结构存储的集合 {A,B,C,D,E,F,G,H,I,J,K,L,M} 的示意图。对于数据 A 来说和数据 B、C、D 有关系对于数据 B 来说和 E、F 有关系。这就是“一对多”的关系。 将具有“一对多”关系的集合中的数据元素按照图 1A的形式进行存储整个存储形状在逻辑结构上看类似于实际生活中倒着的树图 1B倒过来所以称这种存储结构为“树型”存储结构。
树的结点
结点使用树结构存储的每一个数据元素都被称为“结点”。例如图 1A中数据元素 A 就是一个结点父结点双亲结点、子结点和兄弟结点对于图 1A中的结点 A、B、C、D 来说A 是 B、C、D 结点的父结点也称为“双亲结点”而 B、C、D 都是 A 结点的子结点也称“孩子结点”。对于 B、C、D 来说它们都有相同的父结点所以它们互为兄弟结点。 树根结点简称“根结点”每一个非空树都有且只有一个被称为根的结点。图 1A中结点 A 就是整棵树的根结点。
树根的判断依据为如果一个结点没有父结点那么这个结点就是整棵树的根结点。
叶子结点如果结点没有任何子结点那么此结点称为叶子结点叶结点。例如图 1A中结点 K、L、F、G、M、I、J 都是这棵树的叶子结点。
子树和空树
子树如图 1A中整棵树的根结点为结点 A而如果单看结点 B、E、F、K、L 组成的部分来说也是棵树而且节点 B 为这棵树的根结点。所以称 B、E、F、K、L 这几个结点组成的树为整棵树的子树同样结点 E、K、L 构成的也是一棵子树根结点为 E。 注意单个结点也是一棵树只不过根结点就是它本身。图 1A中结点 K、L、F 等都是树且都是整棵树的子树。 知道了子树的概念后树也可以这样定义树是由根结点和若干棵子树构成的。 空树如果集合本身为空那么构成的树就被称为空树。空树中没有结点。
补充在树结构中对于具有同一个根结点的各个子树相互之间不能有交集。例如图 1A中除了根结点 A其余元素又各自构成了三个子树根结点分别为 B、C、D这三个子树相互之间没有相同的结点。如果有就破坏了树的结构不能算做是一棵树。
结点的度和层次
对于一个结点拥有的子树数结点有多少分支称为结点的度Degree。例如图 1A中根结点 A 下分出了 3 个子树所以结点 A 的度为 3。
一棵树的度是树内各结点的度的最大值。图 1A表示的树中各个结点的度的最大值为 3所以整棵树的度的值是 3。 结点的层次从一棵树的树根开始树根所在层为第一层根的孩子结点所在的层为第二层依次类推。对于图 1A来说A 结点在第一层B、C、D 为第二层E、F、G、H、I、J 在第三层K、L、M 在第四层。
一棵树的深度高度是树中结点所在的最大的层次。图 1A树的深度为 4。
如果两个结点的父结点虽不相同但是它们的父结点处在同一层次上那么这两个结点互为堂兄弟。例如图 1A中结点 G 和 E、F、H、I、J 的父结点都在第二层所以之间为堂兄弟的关系。
有序树和无序树
如果树中结点的子树从左到右看谁在左边谁在右边是有规定的这棵树称为有序树反之称为无序树。
在有序树中一个结点最左边的子树称为第一个孩子最右边的称为最后一个孩子。
拿图 1A来说如果是其本身是一棵有序树则以结点 B 为根结点的子树为整棵树的第一个孩子以结点 D 为根结点的子树为整棵树的最后一个孩子。
森林
由 mm 0个互不相交的树组成的集合被称为森林。图 1A中分别以 B、C、D 为根结点的三棵子树就可以称为森林。 前面讲到树可以理解为是由根结点和若干子树构成的而这若干子树本身是一个森林所以树还可以理解为是由根结点和森林组成的。用一个式子表示为
Tree root,F
其中root 表示树的根结点F 表示由 mm 0棵树组成的森林。
树的表示方法
除了图 1A表示树的方法外还有其他表示方法 A B
图2 树的表示形式
图 2A是以嵌套的集合的形式表示的集合之间绝不能相交即图中任意两个圈不能相交。 图 2B使用的是凹入表示法了解即可表示方式是最长条为根结点相同长度的表示在同一层次。例如 B、C、D 长度相同都为 A 的子结点E 和 F 长度相同为 B 的子结点K 和 L 长度相同为 E 的子结点依此类推。 最常用的表示方法是使用广义表的方式。图 1A用广义表表示为
(A , ( B ( E ( K , L ) , F ) , C ( G ) , D ( H ( M ) , I , J ) ) )
总结
树型存储结构类似于家族的族谱各个结点之间也同样可能具有父子、兄弟、表兄弟的关系。本节中要重点理解树的根结点和子树的定义同时要会计算树中各个结点的度和层次以及树的深度。 什么是二叉树包含满二叉树和完全二叉树 简单地理解满足以下两个条件的树就是二叉树
本身是有序树树中包含的各个节点的度不能超过 2即只能是 0、1 或者 2 例如图 1a) 就是一棵二叉树而图 1b) 则不是。 图 1 二叉树示意图
二叉树的性质
经过前人的总结二叉树具有以下几个性质
二叉树中第 i 层最多有 2i-1 个结点。如果二叉树的深度为 K那么此二叉树最多有 2K-1 个结点。二叉树中终端结点数叶子结点数为 n0度为 2 的结点数为 n2则 n0n21。
性质 3 的计算方法为对于一个二叉树来说除了度为 0 的叶子结点和度为 2 的结点剩下的就是度为 1 的结点设为 n1那么总结点 nn0n1n2。 同时对于每一个结点来说都是由其父结点分支表示的假设树中分枝数为 B那么总结点数 nB1。而分枝数是可以通过 n1 和 n2 表示的即 Bn12*n2。所以n 用另外一种方式表示为 nn12*n21。 两种方式得到的 n 值组成一个方程组就可以得出 n0n21。 二叉树还可以继续分类衍生出满二叉树和完全二叉树。
满二叉树
如果二叉树中除了叶子结点每个结点的度都为 2则此二叉树称为满二叉树。 图 2 满二叉树示意图 如图 2 所示就是一棵满二叉树。 满二叉树除了满足普通二叉树的性质还具有以下性质
满二叉树中第 i 层的节点数为 2n-1 个。深度为 k 的满二叉树必有 2k-1 个节点 叶子数为 2k-1。满二叉树中不存在度为 1 的节点每一个分支点中都两棵深度相同的子树且叶子节点都在最底层。具有 n 个节点的满二叉树的深度为 log2(n1)。
完全二叉树
如果二叉树中除去最后一层节点为满二叉树且最后一层的结点依次从左到右分布则此二叉树被称为完全二叉树。 图 3 完全二叉树示意图 如图 3a) 所示是一棵完全二叉树图 3b) 由于最后一层的节点没有按照从左向右分布因此只能算作是普通的二叉树。 完全二叉树除了具有普通二叉树的性质它自身也具有一些独特的性质比如说n 个结点的完全二叉树的深度为 ⌊log2n⌋1。
⌊log2n⌋ 表示取小于 log2n 的最大整数。例如⌊log24⌋ 2而 ⌊log25⌋ 结果也是 2。
对于任意一个完全二叉树来说如果将含有的结点按照层次从左到右依次标号如图 3a)对于任意一个结点 i 完全二叉树还有以下几个结论成立
当 i1 时父亲结点为结点 [i/2] 。i1 时表示的是根结点无父亲结点如果 2*in总结点的个数 则结点 i 肯定没有左孩子为叶子结点否则其左孩子是结点 2*i 。如果 2*i1n 则结点 i 肯定没有右孩子否则右孩子是结点 2*i1 。 二叉树的顺序存储结构看了无师自通 二叉树的存储结构有两种分别为顺序存储和链式存储。本节先介绍二叉树的顺序存储结构。 二叉树的顺序存储指的是使用顺序表数组存储二叉树。需要注意的是顺序存储只适用于完全二叉树。换句话说只有完全二叉树才可以使用顺序表存储。因此如果我们想顺序存储普通二叉树需要提前将普通二叉树转化为完全二叉树。
有读者会说满二叉树也可以使用顺序存储。要知道满二叉树也是完全二叉树因为它满足完全二叉树的所有特征。
普通二叉树转完全二叉树的方法很简单只需给二叉树额外添加一些节点将其拼凑成完全二叉树即可。如图 1 所示 图 1 普通二叉树的转化 图 1 中左侧是普通二叉树右侧是转化后的完全满二叉树。 解决了二叉树的转化问题接下来学习如何顺序存储完全满二叉树。 完全二叉树的顺序存储仅需从根节点开始按照层次依次将树中节点存储到数组即可。 图 2 完全二叉树示意图 例如存储图 2 所示的完全二叉树其存储状态如图 3 所示 图 3 完全二叉树存储状态示意图 同样存储由普通二叉树转化来的完全二叉树也是如此。例如图 1 中普通二叉树的数组存储状态如图 4 所示 图 4 普通二叉树的存储状态 由此我们就实现了完全二叉树的顺序存储。 不仅如此从顺序表中还原完全二叉树也很简单。我们知道完全二叉树具有这样的性质将树中节点按照层次并从左到右依次标号1,2,3,...若节点 i 有左右孩子则其左孩子节点为 2*i右孩子节点为 2*i1。此性质可用于还原数组中存储的完全二叉树也就是实现由图 3 到图 2、由图 4 到图 1 的转变。 二叉树的链式存储结构C语言详解 本节我们学习二叉树的链式存储结构。 图 1 普通二叉树示意图 如图 1 所示此为一棵普通的二叉树若将其采用链式存储则只需从树的根节点开始将各个节点及其左右孩子使用链表存储即可。因此图 1 对应的链式存储结构如图 2 所示 图 2 二叉树链式存储结构示意图 由图 2 可知采用链式存储二叉树时其节点结构由 3 部分构成如图 3 所示
指向左孩子节点的指针Lchild节点存储的数据data指向右孩子节点的指针Rchild 图 3 二叉树节点结构 表示该节点结构的 C 语言代码为 typedef struct BiTNode{TElemType data;//数据域struct BiTNode *lchild,*rchild;//左右孩子指针struct BiTNode *parent;}BiTNode,*BiTree; 图 2 中的链式存储结构对应的 C 语言代码为 #include stdio.h#include stdlib.h#define TElemType inttypedef struct BiTNode{ TElemType data;//数据域 struct BiTNode *lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;void CreateBiTree(BiTree *T){ *T(BiTNode*)malloc(sizeof(BiTNode)); (*T)-data1; (*T)-lchild(BiTNode*)malloc(sizeof(BiTNode)); (*T)-lchild-data2; (*T)-rchild(BiTNode*)malloc(sizeof(BiTNode)); (*T)-rchild-data3; (*T)-rchild-lchildNULL; (*T)-rchild-rchildNULL; (*T)-lchild-lchild(BiTNode*)malloc(sizeof(BiTNode)); (*T)-lchild-lchild-data4; (*T)-lchild-rchildNULL; (*T)-lchild-lchild-lchildNULL; (*T)-lchild-lchild-rchildNULL;}int main() { BiTree Tree; CreateBiTree(Tree); printf(%d,Tree-lchild-lchild-data); return 0;}
程序输出结果
4
其实二叉树的链式存储结构远不止图 2 所示的这一种。例如在某些实际场景中可能会做 查找某节点的父节点 的操作这时可以在节点结构中再添加一个指针域用于各个节点指向其父亲节点如图 4 所示 图 4 自定义二叉树的链式存储结构
这样的链表结构通常称为三叉链表。
利用图 4 所示的三叉链表我们可以很轻松地找到各节点的父节点。因此在解决实际问题时用合适的链表结构存储二叉树可以起到事半功倍的效果。 树的双亲表示法 普通树结构的数据。 图 1 普通树存储结构 如图 1 所示这是一棵普通的树该如何存储呢通常存储具有普通树结构数据的方法有 3 种
双亲表示法孩子表示法孩子兄弟表示法 本节先来学习双亲表示法。 双亲表示法采用顺序表也就是数组存储普通树其实现的核心思想是顺序存储各个节点的同时给各节点附加一个记录其父节点位置的变量。
注意根节点没有父节点父节点又称为双亲节点因此根节点记录父节点位置的变量通常置为 -1。
例如采用双亲表示法存储图 1 中普通树其存储状态如图 2 所示 图 2 双亲表示法存储普通树示意图 树的孩子表示法 孩子表示法存储普通树采用的是 顺序表链表 的组合结构其存储过程是从树的根节点开始使用顺序表依次存储树中各个节点需要注意的是与双亲表示法不同孩子表示法会给各个节点配备一个链表用于存储各节点的孩子节点位于顺序表中的位置。
如果节点没有孩子节点叶子节点则该节点的链表为空链表。
例如使用孩子表示法存储图 1a) 中的普通树则最终存储状态如图 1b) 所示 图 1 孩子表示法存储普通树示意图 图 1 所示转化为 C 语言代码为 #includestdio.h#includestdlib.h#define MAX_SIZE 20#define TElemType char//孩子表示法typedef struct CTNode { int child;//链表中每个结点存储的不是数据本身而是数据在数组中存储的位置下标 struct CTNode * next;}ChildPtr;typedef struct { TElemType data;//结点的数据类型 ChildPtr* firstchild;//孩子链表的头指针}CTBox;typedef struct { CTBox nodes[MAX_SIZE];//存储结点的数组 int n, r;//结点数量和树根的位置}CTree;//孩子表示法存储普通树CTree initTree(CTree tree) { printf(输入节点数量\n); scanf(%d, (tree.n)); for (int i 0; i tree.n; i) { printf(输入第 %d 个节点的值\n, i 1); getchar(); scanf(%c, (tree.nodes[i].data)); tree.nodes[i].firstchild (ChildPtr*)malloc(sizeof(ChildPtr)); tree.nodes[i].firstchild-next NULL; printf(输入节点 %c 的孩子节点数量\n, tree.nodes[i].data); int Num; scanf(%d, Num); if (Num ! 0) { ChildPtr * p tree.nodes[i].firstchild; for (int j 0; j Num; j) { ChildPtr * newEle (ChildPtr*)malloc(sizeof(ChildPtr)); newEle-next NULL; printf(输入第 %d 个孩子节点在顺序表中的位置, j 1); scanf(%d, (newEle-child)); p-next newEle; p p-next; } } } return tree;}void findKids(CTree tree, char a) { int hasKids 0; for (int i 0; i tree.n; i) { if (tree.nodes[i].data a) { ChildPtr * p tree.nodes[i].firstchild-next; while (p) { hasKids 1; printf(%c , tree.nodes[p-child].data); p p-next; } break; } } if (hasKids 0) { printf(此节点为叶子节点); }}int main(){ CTree tree; for (int i 0; i MAX_SIZE; i) { tree.nodes[i].firstchild NULL; } tree initTree(tree); //默认数根节点位于数组notes[0]处 tree.r 0; printf(找出节点 F 的所有孩子节点); findKids(tree, F); return 0;}
程序运行结果为
输入节点数量 10 输入第 1 个节点的值 R 输入节点 R 的孩子节点数量 3 输入第 1 个孩子节点在顺序表中的位置1 输入第 2 个孩子节点在顺序表中的位置2 输入第 3 个孩子节点在顺序表中的位置3 输入第 2 个节点的值 A 输入节点 A 的孩子节点数量 2 输入第 1 个孩子节点在顺序表中的位置4 输入第 2 个孩子节点在顺序表中的位置5 输入第 3 个节点的值 B 输入节点 B 的孩子节点数量 0 输入第 4 个节点的值 C 输入节点 C 的孩子节点数量 1 输入第 1 个孩子节点在顺序表中的位置6 输入第 5 个节点的值 D 输入节点 D 的孩子节点数量 0 输入第 6 个节点的值 E 输入节点 E 的孩子节点数量 0 输入第 7 个节点的值 F 输入节点 F 的孩子节点数量 3 输入第 1 个孩子节点在顺序表中的位置7 输入第 2 个孩子节点在顺序表中的位置8 输入第 3 个孩子节点在顺序表中的位置9 输入第 8 个节点的值 G 输入节点 G 的孩子节点数量 0 输入第 9 个节点的值 H 输入节点 H 的孩子节点数量 0 输入第 10 个节点的值 K 输入节点 K 的孩子节点数量 0 找出节点 F 的所有孩子节点G H K
使用孩子表示法存储的树结构正好和双亲表示法相反适用于查找某结点的孩子结点不适用于查找其父结点。 其实我们还可以将双亲表示法和孩子表示法合二为一那么图 1a) 中普通树的存储效果如图 2所示 图 2 双亲孩子表示法 使用图 2 结构存储普通树既能快速找到指定节点的父节点又能快速找到指定节点的孩子节点。该结构的实现方法很简单只需整合这两节的代码即可因此不再赘述。 树的孩子兄弟表示法
一种常用方法——孩子兄弟表示法。 图 1 普通树示意图 树结构中位于同一层的节点之间互为兄弟节点。例如图 1 的普通树中节点 A、B 和 C 互为兄弟节点而节点 D、E 和 F 也互为兄弟节点。 孩子兄弟表示法采用的是链式存储结构其存储树的实现思想是从树的根节点开始依次用链表存储各个节点的孩子节点和兄弟节点。 因此该链表中的节点应包含以下 3 部分内容如图 2 所示
节点的值指向孩子节点的指针指向兄弟节点的指针 图 2 节点结构示意图 用 C 语言代码表示节点结构为 #define ElemType chartypedef struct CSNode{ElemType data;struct CSNode * firstchild,*nextsibling;}CSNode,*CSTree; 以图 1 为例使用孩子兄弟表示法进行存储的结果如图 3 所示: 图 3 孩子兄弟表示法示意图 由图 3 可以看到节点 R 无兄弟节点其孩子节点是 A节点 A 的兄弟节点分别是 B 和 C其孩子节点为 D依次类推。 实现图 3 中的 C 语言实现代码也很简单根据图中链表的结构即可轻松完成链表的创建和使用因此不再给出具体代码。 接下来观察图 1 和图 3。图 1 为原普通树图 3 是由图 1 经过孩子兄弟表示法转化而来的一棵树确切地说图 3 是一棵二叉树。因此可以得出这样一个结论即通过孩子兄弟表示法任意一棵普通树都可以相应转化为一棵二叉树换句话说任意一棵普通树都有唯一的一棵二叉树于其对应。 因此孩子兄弟表示法可以作为将普通树转化为二叉树的最有效方法通常又被称为二叉树表示法或二叉链表表示法。
