张掖建设局网站,做的比较好的二手交易网站有哪些,建立企业网站的缺点,免费建筑图纸下载网站一.树的逻辑结构#xff1a; 二.双亲表示法(顺序存储)#xff1a; 1.树中除了根结点外每一颗树中的任意一个结点都只有一个父结点(双亲结点)#xff1b;
2.结点包括结点数据和指针#xff1b;
3.上述图片中右边的顺序存储解析#xff1a;比如A结点左边的0#xff0c;就… 一.树的逻辑结构 二.双亲表示法(顺序存储) 1.树中除了根结点外每一颗树中的任意一个结点都只有一个父结点(双亲结点)
2.结点包括结点数据和指针
3.上述图片中右边的顺序存储解析比如A结点左边的0就是在数组中的位置即第一个位置A结点右边的-1代表没有双亲即没有父结点结点C左边的2代表在数组中第3个位置右边的0就是结点C的父结点即A结点在数组中的位置其他同理
4.上述图片中的代码解析PTNode代表结点结构体里的nodes数组是PTNode型也就是结点的集合构成了树结构体PTNode里有结点的数据和指向双亲位置域的双亲指针指针是int型(不是int *)因此指向的是双亲结点在数组中的位置下标
5.基本操作
a.增加结点 上述图片增加一个结点M在结点H下顺序存储在第12个位置即数组下标为11结点M的父结点为H结点H在数组中下标为7因此结点M的结点指针parent为7 此时数组中数据元素的排列顺序表面像是层序规则排列但在插入新结点时并不需要遵守层序的规则即不需要同一层中必须先从最左边添加然后依次添加到最右边而是可以随意添加在某个结点下比如再插入一个L结点在E结点下 b.删除结点 比如删除G结点有两种方案
方案一把G结点的双亲指针改为-1(因为双亲指针的值就是对应结点的父结点在数组中的位置此时G结点不存在了即在该树中没有父结点因此双亲指针可设为-1是一个不存在的数组下标) 方案二把尾部的数据即结点L里的数据移动到G结点的位置上这样就保证数组里的每一个存储单元都是有效的(比方案一好) 注删除结点后要把结点数减一不是数组长度减一
刚才删除的G结点是叶子结点如果删除的不是叶子结点那么既然该结点被删除了那么这个结点下面连着的所有结点即以该结点为根结点的树就都被删除了如删除D结点那么结点D,H,I,J,M就都被删除了此时就涉及到查询除了根结点D外H,I,J,M在数组中的位置然后更改双亲指针进行删除
c.查询结点(查询到结点后也可以修改结点数据)
采用双亲表示法找到父结点很容易因为有双亲指针直接可以知道父结点在数组中的位置 但如果找父结点的子结点就只能从头到尾依次遍历把每一个结点的双亲指针取出来对比是否与父结点在数组中的下标相等这也就暴露出删除结点中方案一是有些低效的因为该方案中删除元素后会有双亲指针的无效数据此时遍历数组时也会把这个无效数据一起遍历降低了效率因此删除结点中方案二较好 6.回顾二叉树的顺序存储二叉树也是树也可以用双亲表示法 三.孩子表示法(顺序链式存储结合)
1.核心先利用顺序表开辟一个顺序存储空间即数组来存储各个结点里的数据每个结点包含数据域和指向第一个子结点的指针 2.代码 解析结点CTBox结构体中存储数据和第一个孩子链表struct CTNode中的各个结点其实只是保存了各个子结点的数组下标
对于上述代码呈现出的存储结构可知找子结点很方便但找双亲结点就较麻烦 四.孩子兄弟表示法(链式存储)
1.代码 解析1.*firstchild指针可看作左指针指向结点的第一个子结点(不一定叫左子结点因为可能不是二叉树但一定是第
一个结点)
*nextsibling指针可看作右指针指向结点的第一个子结点的后面结点即右兄弟结点
(左孩子不同层右兄弟同层)
(从物理上看用孩子兄弟表示法保存的树形状上和二叉树一样只不过左右指针的含义不同)
如根结点A(只有孩子没有同层的兄弟)结点A的*firstchild指针指向B结点
由于B结点的右兄弟为C结点所以结点B的 *nextsibling指针指向 C结点
由于C结点的右兄弟为D结点所以结点C的 *nextsibling指针指向D结点 同理结点B的第一个孩子为E结点那么结点B的*firstchild指针指向E结点
由于E结点的右兄弟为F结点所以结点E的 *nextsibling指针指向 F结点
结点E的第一个孩子为K结点那么结点E的*firstchild指针指向K结点
同理结点C的第一个孩子为G结点那么结点C的*firstchild指针指向G结点
同理结点D的第一个孩子为H结点那么结点D的*firstchild指针指向H结点
由于H结点的右兄弟为I结点所以结点H的 *nextsibling指针指向 I结点
由于I结点的右兄弟为J结点所以结点I的 *nextsibling指针指向 J结点 2.例如二叉树转化为树
思路要把二叉树看作是用二叉链表保存的树左边的第一个结点是孩子剩下的右边全是兄弟
首先A是根结点A结点的左边第一个结点B为左孩子可知在B的右边的结点C,F,L都是它的右兄弟所以 看以B为根结点的子树D结点是B结点的左孩子H结点连在D结点的右边所以H结点是D结点的右兄弟
同理G结点是D结点的左孩子后续同理最终如下 五.森林和二叉树的转换
本质用二叉树链表(孩子兄弟表示法)存储森林
核心可以利用二叉链表的方式来存储森林一个森林里有几个互不相交的树首先把森林里的树都转换为二叉树森林里的每一棵树在逻辑上看是平级的因此可以把这些树的根结点看作兄弟结点如果用二叉链表(孩子兄弟表示法)存储的话右指针表示兄弟关系因此可以把这些树的根结点用右指针连接起来 例题
把二叉树转换为森林
思路从根结点A出发右边的结点C,F,L都是右兄弟因此结点A,C,F,L是平级的兄弟关系
因此结点A,C,F,L就是四棵互不相交的树的根结点 对于A结点第一个孩子为B结点B结点没有右兄弟C结点已经用了这里无需处理C结点
对于B结点第一个孩子为D结点D结点没有右兄弟
对于D结点第一个孩子为G结点D结点的右兄弟为H结点因此B结点的右边连接H结点 对于C结点第一个孩子为E结点F结点已经用了这里无需处理F结点
对于E结点第一个孩子为I结点E结点的右兄弟为J因此C结点右边连接J结点 对于F结点第一个孩子为K结点L结点已经用了这里无需处理L结点
对于L结点左右没有连接任何东西所以处理完毕 六.总结
