开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【数据结构】树的遍历、森林的遍历 -> 正文阅读

[数据结构与算法]【数据结构】树的遍历、森林的遍历

💟作者简介：大家好呀！我是路遥叶子，大家可以叫我叶子哦！???? ?
📝个人主页：【路遥叶子的博客】
🏆博主信息：四季轮换叶，一路招摇胜！
??????? 专栏

?????? 【安利Java零基础】

?????? 【数据结构-Java语言描述】

🐋希望大家多多支持😘一起进步呀！~??
🌈若有帮助，还请【关注?点赞?收藏】，不行的话我再努力努力呀！💪
————————————————
?版权声明：本文由【路遥叶子】原创、在CSDN首发、需要转载请联系博主。
🍁想寻找共同成长的小伙伴，请点击【Java全栈开放社区】

🐋树的遍历

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

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

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

🌈 先根遍历

若树为非空，则
1. 访问根节点
2. 从左到右依次先根遍历根节点的每一颗子树。

先根遍历序列：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);
                }
            }
        }
    }
}

💚??💙💚???💙💚???💙💚??💙?💚??💙💚???💙💚???💙??💙💚?