【数据结构】树：非二叉树（普通树）与森林的遍历

比眉伴天荒 2021-12-04 00:55 490阅读 0赞

#笔记整理

树的定义参照前文：
二叉树、遍历二叉树与线索二叉树等树的定义与解析、二叉树遍历实现

非二叉树与森林的遍历

树的遍历（两种）

1） 先根遍历
若树非空，则遍历方法为：
①访问根结点。
②从左到右， 依次先根遍历根结点的每一棵子树。
等同于转换的二叉树进行先序遍历
在这里插入图片描述
2）后根遍历
若树非空， 则遍历方法为：
①从左到右， 依次后根遍历根结点的每一棵子树。
②访问根结点。
等同于转换的二叉树进行中序遍历。
在这里插入图片描述

在这里插入图片描述

森林的遍历（2种）

1） 先序遍历
若森林非空， 则遍历方法为：
①访问森林中第一棵树的根结点。
②先序遍历第一棵树的根结点的子树森林。
③先序遍历除去第一棵树之后剩余的树构成的森林。
等同于转换的二叉树进行先序遍历
在这里插入图片描述

2） 中序遍历
若森林非空， 则遍历方法为：
①中序遍历森林中第一棵树的根结点的子树森林。
②访问第一棵树的根结点。
③中序遍历除去第一棵树之后剩余的树构成的森林。
等同于转换的二叉树进行中序遍历
在这里插入图片描述

在这里插入图片描述

由遍历确定树和森林

①给定树的先根遍历序列和后根遍历序列可唯一画出一棵树。
②给定森林的先序遍历序列和中序遍历序列可唯一确定一森林。

由遍历确定二叉树

①任何n(n≥0)个不同结点的二叉树,都可由它的中序序列和先序序列唯一地确定。
②任何n(n＞0)个不同结点的二叉树,都可由它的中序序列和后序序列唯一地确定。
在这里插入图片描述
在这里插入图片描述

森林转换为二叉树

森林也可以方便地用孩子兄弟链表表示。森林转换为二叉树的方法如下：
（1）将森林中的每棵树转换成相应的二叉树。
（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子， 当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。
在这里插入图片描述

二叉树还原为树或森林

将一棵二叉树还原为树或森林，具体方法如下：
（1） 若某结点是其双亲的左孩子，则把该结点的右孩子、 右孩子的右孩子……都与该结点的双亲结点用线连起来。
（2） 删掉原二叉树中所有双亲结点与右孩子结点的连线。
（3） 整理由（1）、（2）两步所得到的树或森林， 使之结构层次分明。
在这里插入图片描述

部分内容来源：

  1. 《数据结构（C语言版）》——严蔚敏
  2. 《数据结构》课堂教学ppt —— 刘立芳
  3. 《数据结构算法与解析（STL版）》 —— 高一凡

发表评论

表情：
评论列表 （有 0 条评论，490人围观）

还没有评论，来说两句吧...

相关阅读

    相关 树 森林 二叉树 遍历

    所谓遍历(Traversal)，是指沿着某条搜索路线，依次对树（或图）中每个节点均做一次访问。 访问结点所做的操作依赖于具体的应用问题， 具体的访问操作可能是检查节点的值、

    悠悠悠悠/ 0 赞/ 130 阅读

    相关 数据结构——树——二叉树遍历

    遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质

    r囧r小猫r囧r小猫/ 0 赞/ 412 阅读