回忆一下树的逻辑结构:

 双亲表示法(顺序存储)

 

 

 

 如果增加一个结点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)中序遍历

 

 

用孩子兄弟表示法,森林可以转换成对应的二叉树,这样就可以实现先序和中序遍历森林。

 

 

技术
今日推荐
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:[email protected]
QQ群:766591547
关注微信