[{"createTime":1735734952000,"id":1,"img":"hwy_ms_500_252.jpeg","link":"https://activity.huaweicloud.com/cps.html?fromacct=261f35b6-af54-4511-a2ca-910fa15905d1&utm_source=V1g3MDY4NTY=&utm_medium=cps&utm_campaign=201905","name":"华为云秒杀","status":9,"txt":"华为云38元秒杀","type":1,"updateTime":1735747411000,"userId":3},{"createTime":1736173885000,"id":2,"img":"txy_480_300.png","link":"https://cloud.tencent.com/act/cps/redirect?redirect=1077&cps_key=edb15096bfff75effaaa8c8bb66138bd&from=console","name":"腾讯云秒杀","status":9,"txt":"腾讯云限量秒杀","type":1,"updateTime":1736173885000,"userId":3},{"createTime":1736177492000,"id":3,"img":"aly_251_140.png","link":"https://www.aliyun.com/minisite/goods?userCode=pwp8kmv3","memo":"","name":"阿里云","status":9,"txt":"阿里云2折起","type":1,"updateTime":1736177492000,"userId":3},{"createTime":1735660800000,"id":4,"img":"vultr_560_300.png","link":"https://www.vultr.com/?ref=9603742-8H","name":"Vultr","status":9,"txt":"Vultr送$100","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":5,"img":"jdy_663_320.jpg","link":"https://3.cn/2ay1-e5t","name":"京东云","status":9,"txt":"京东云特惠专区","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":6,"img":"new_ads.png","link":"https://www.iodraw.com/ads","name":"发布广告","status":9,"txt":"发布广告","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":7,"img":"yun_910_50.png","link":"https://activity.huaweicloud.com/discount_area_v5/index.html?fromacct=261f35b6-af54-4511-a2ca-910fa15905d1&utm_source=aXhpYW95YW5nOA===&utm_medium=cps&utm_campaign=201905","name":"底部","status":9,"txt":"高性能云服务器2折起","type":2,"updateTime":1735660800000,"userId":3}]
回忆一下树的逻辑结构:
双亲表示法(顺序存储)
如果增加一个结点M,L。毋须按照逻辑上的次序存储。
如果是删除元素:
方案一:比如说删除元素为G,设置其双亲结点为-1。
方案二:
把尾部的结点提上来。
还需要改变数值让结点数减1。
还要删除以他为根节点的子孙节点。
来回顾一下二叉树的顺序存储:
可以根据结点编号不仅反映了存储位置,也隐含了结点之间的逻辑关系。
下面来讲解树的孩子表示法
下面就是孩子兄弟表示法(链式存储)
一个数据域,两个指针
其实是跟二叉树的链式存储时一样的
只是名称有所不同
就得到了孩子兄弟法得到了树
是不是二叉树和树就可以相互转化了。
接下来看森林和二叉树的相互转换:
再把二叉树转换为森林:
5.4.2树和森林的遍历
树的遍历
1)树的先根遍历
那么对这颗树进行先根遍历的话那么顺序是这样的:
先是ABCD
然后A(BEF)(CG)(DHIJ)
最后A(B(EK)F)(CG)(DHIJ)
伪代码实现:
树和二叉树的转换
二叉树的先序遍历序列和树的先根遍历序列相同
2)树的后根遍历
先依次对每棵子树进行后根遍历,最后在访问根节点。
遍历序列如下:
先往下往左走
对二叉树的中序遍历序列是相同的。
3)树的层次遍历
最后在队列中的元素依次出队。
先根遍历和后根遍历需要往深处走,所以我们称之为深度优先遍历。
层序遍历我们称之为广度优先遍历。
下面我们再来看对森林的遍历
1)先序遍历
森林是m(m>=0)棵互不相交的树的集合。每棵树去掉根节点之后,其各个子树又组成森林。
也可以先把森林转换成与之对应的二叉树:
效果等同于依次对二叉树的先序遍历
2)中序遍历
用孩子兄弟表示法,森林可以转换成对应的二叉树,这样就可以实现先序和中序遍历森林。