河北省建设网站的网站首页,高端做网站多少钱,wordpress页面多打开空白页,网站内页制作知识总览#xff1a; 树的逻辑结构#xff1a;
一个树下有多个子树#xff0c;每个树中节点的子树数量不确定#xff0c;可能某个节点的子树有2个#xff0c;另外一个节点的子树有3个#xff0c;如果把节点按照下标依次放到数组里边#xff0c;即使数组中有下标但是因为…知识总览 树的逻辑结构
一个树下有多个子树每个树中节点的子树数量不确定可能某个节点的子树有2个另外一个节点的子树有3个如果把节点按照下标依次放到数组里边即使数组中有下标但是因为每个节点的孩子数量不确定所以也不能确定节点之间的逻辑关系 树的存储1双亲表示法
用数组记录每个节点的父节点在数组中的索引位置纯顺序存储
因为在树中每个节点除了根节点之外都有唯一的父节点所以可以把各个节点放在数组中各个索引位置上另外在数组中再加一个字段表示该节点的父节点索引位置根节点没有父节点则对应的父节点索引位置设为-1如下第2张图根节点A的parent0E和F的parent1即数组中Index1即B节点
PTNode每个节点中包括data字段存储节点元素的数据int类型的parent字段存储该节点的父节点在数组中的索引,struct结构体中包含PTNode数组存储所有的节点n变量表示树中一共有多少元素
双亲表示法也可以用来表示森林森林中有多个树把每个树的根节点的父节点的索引值设为-1其他节点按层序遍历放到PTNode数组中好像是这样的。。。。。。。
优缺点
在找某个节点的父亲时直接找该节点对应的parent字段找到父节点的index位置即可可实现随机访问方便在找某个节点的孩子时只能遍历所有的节点然后找出parent字段是该节点的即找孩子时不方便适用于找父亲多找孩子少的情况如并查集 树的存储2孩子表示法 用数组记录每个节点的孩子因为树中每个节点的孩子可能是多个所以记录孩子的字段是个链表结构顺序链式存储
CTBox每个节点信息中包括data字段存储节点元素的数据和指向第一个孩子的指针firstChild指针firstChild中包括该孩子节点在数组中的索引位置指向下一个孩子的指针。struct结构体中包含CTBox数组存储所有的节点n变量表示树中一共有多少元素r记录根节点在数组中的index索引位置孩子为空的firstChild指针记为NULL
孩子表示法也可用来表示森林因为森林有多个树每个树都有一个根节点先把所有根节点放到数组中然后再层次遍历其他节点放在数组中在记录根的位置时因为有多个根节点所以需要记录多个根的位置
优缺点
在找某个节点的孩子时直接找该节点对应的firstChild字段指向的链表即可找到所有孩子节点的index位置找孩子方便在找某个节点的父亲时只能遍历所有的节点的链表然后找出firstChild指向的孩子链表中有该节点的元素对应的data即为该节点父亲即找父亲时不方便适用于找孩子多找父亲少的情况如服务流程树拨打电话普通话服务请按1,然后再问你办理业务1按#键啥的直到找到最下一层服务节点 树的存储3孩子兄弟表示法(链式存储)
纯二叉链表结构存储
类似于二叉树的二叉链表结构(data字段存储元素数据lchild指针指向左子树rchild指针指向右子树)每个节点表示时用一个data字段表示节点数据用firstChild指针指向该节点的第一个孩子(从左到右顺序)nextsibling指针指向该节点的右边的一个兄弟节点(从左到右顺序)
如下第2张图树的根节点A节点的第一个孩子从左到右是B节点则放在A节点左指针下方作为A的左子树A节点没有兄弟节点则A节点的右指针指向NULL此时已经画了A、B节点则从树的层序遍历从左到右顺序下一个处理C节点C是B的右边第一个兄弟则C放在B的右指针下方成为B的右子树处理DD是C的右边第一个兄弟则D放在C的右指针下方成为C的右子树然后处理下一层EFGHIJ按照从左到右顺序先处理EE是B的第一个左孩子则E放在B的左指针下方成为B的左孩子处理FF是E的右边第一个兄弟放在E的右指针下方成为E的右孩子再看G是C的第一个孩子则G放在C的左指针下方成为C的左孩子看H是D的第一个孩子则放在D的左指针下方成为D的左孩子I是H的右边的兄弟节点则放在I的右指针位置成为I的右孩子J是I的右边兄弟节点则J放在I的右指针下方位置成为I的右子树再处理下一层KK是E的第一个孩子则把K放在E的左指针下方成为E的左子树
看该节点的第一个孩子让该孩子成为该节点的左子树剩下的孩子依次成为兄弟节点依次放在这些节点的右指针位置
孩子兄弟表示法可以表示森林
森林有多个树每个树都有一个根节点这些根节点可以视为平级的兄弟关系从左到右让第一个树的根节点作为孩子兄弟表示法的根节点剩余根节点依次成为上一个节点的右孩子。如下最后一张图BCD是根节点从左到右顺序B是根节点C是B的右边的兄弟节点D是C右边的兄弟节点则C放在B的右指针位置成为B的右孩子D放在C的右指针位置成为C的右孩子再按层序遍历遍历剩余没处理的节点第2层的EFGHIJE是B的第一个孩子放在B的左指针下方成为B的左孩子F是E的右兄弟节点放在E的右指针下方成为E的右孩子再处理GG是C的第一个孩子放在C的左指针位置成为C的左孩子H是D的第一个孩子H放在D的左指针位置成为D的左孩子I是H的右边的兄弟节点J是I右边的兄弟节点则I放在H的右指针位置成为H的右孩子J放在I的右指针位置成为I的右孩子按层序遍历从左到右遍历第3层的KLMK是E的第一个孩子放在E的左指针位置成为E的左孩子,L是K的右边的兄弟节点则L放在K的右指针位置成为K的右孩子M是H的第一个孩子放在H的左指针位置成为H的左孩子,所有节点处理完成结束。 知识回顾 。。。。。。。。。。
