【数据结构】树的遍历、森林的遍历

简介: 【数据结构】树的遍历、森林的遍历

🐋树的遍历


树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问,即依次对树中每个结点访问一次且仅访问一次。


树可被看成是由树的根结点和根结点的所有子树所构成的森林两部分组成。


树的遍历主要有:先根遍历、后根遍历、层次遍历。


🌈 先根遍历


若树为非空,则


访问根节点


从左到右依次先根遍历根节点的每一颗子树。


6f90de5a579b45d39ebc8e3d2b3478c2.png


先根遍历序列:ABEFCDGHIJK

//先根遍历递归算法
public void preRootTraverse(CSTreeNode T) {
    if(T != null) {
        System.out.print(T.data);
        preRootTraverse(T.firstChild);  //先根遍历树中根节点的第一个子树
        preRootTraverse(T.nextsibling); //先根遍历树中根节点的其他子树
    }
}

🌈 后根遍历

  • 若树为非空,则
  1. 从左到右依次后根遍历根节点的每一棵子树
  2. 访问根节点

如上图:

后根遍历序列:EFBCIJKHGDA

public void postRootTraverse(CSTreeNode t) {
    if(T != null) {
        postRootTraverse(T.firstChild);   //后根遍历树中根节点的第一个子树
        System.out.print(T.data);     //访问数的根节点
        postRootTraverse(T.nextsibling);  //后根遍历树中根节点的其他子树
    }
}

🌈 层次遍历

  • 若树为非空,则从根节点开始,从上到下依次访问每一层的各个结点,在同一层中的结点,则按从左到右的顺序依次进行访问。

层次遍历序列:ABCDEFGHIJK

public void levelTraverse(CSTreeNode T) {
    if(T != null) {
        LinkQueue L = new LinkQueue();    //构建队列
        L.offer(T);             //根节点入队列
        while(!L.isEmpty()) {     //队列不为空,处理根结点和左孩子
            for(T = L.poll() ; T != null ; T = T.nextsibling) {//依次处理兄弟(右子树)
                System.out.print(T.data + " ");
                if(T.firstChild != null) {  //第一个孩子结点非空入队列
                    L.offer(T.firstchild);
                }
            }
        }
    }
}

🐋 森林的遍历


森林由3部分组成:


森林中第一棵树的根节点


森林中第一棵树的子树森林


森林中其他树构成的森林。


森林的3中遍历:


先根遍历


后根遍历


层次遍历


🌲先根遍历


顾名思义,先根遍历就是把根节点放在最前面的遍历方法,就是根节点->第一子树森林->其他森林的顺序来进行遍历。


若森林不空,则可依下列次序进行遍历:


访问森林中第一棵树的根节点


先序遍历第一课树中的子树森林


先序遍历除去第一棵树之后剩余的树构成的森林。


也就是说:依次从左到右对森林中的每一颗树进行先根遍历。


2a11e7950ed246798c672a565f7cc428.png


先根遍历顺序是:ABCEDFGHIJKL


🌲后根遍历


顾名思义,后根遍历就是把根节点放在最后面的遍历方法,就是第一子树森林->其他森林->根节点的顺序来进行遍历。


若森林不空,则可依下列次序进行遍历:


后根遍历第一棵树中的子树森林


后根遍历除去第一棵树之后剩余的树构成的森林。


访问森林中第一棵树的根节点


也就是说:依次从左至右对森林中的每一棵树进行后根遍历。


2827b46860864b4588ed09d5553e43fd.png


后根遍历序列是:BECDAGFIKLJH


🌲层次遍历


顾名思义,层次遍历就是按照每一棵树的每一层的顺序来进行遍历。


若森林为非空,则按从左到右的顺序对森林中每一颗树进行层次遍历。


也就是说:依次从左至右对森林中的每一棵树进行层次遍历。


15e8a57969814e1882de2438e8d2d92c.png


层次遍历序列:ABCDEFGHIJKL


相关文章
|
1月前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
85 64
|
1天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
30 16
|
24天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
16 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
21天前
|
Java C++
【数据结构】探索红黑树的奥秘:自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理,介绍其五大原则,并通过图解和代码示例展示其内部机制。同时,对比红黑树与二叉查找树的性能差异,帮助读者更好地理解这两种数据结构的特点和应用场景。
23 0
|
24天前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
20 0
|
26天前
05(数据结构考研)树相关操作代码
05(数据结构考研)树相关操作代码
27 0
|
27天前
|
存储 算法 Java
数据结构和算法--分段树
数据结构和算法--分段树
12 0
|
29天前
【数据结构】翻转、平衡、对称二叉树,最大深度、判断两棵树是否相等、另一棵树的子树
【数据结构】翻转、平衡、对称二叉树,最大深度、判断两棵树是否相等、另一棵树的子树
28 0
|
2天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
38 9