【数据结构】树的遍历、森林的遍历
【 💟作者简介:大家好呀!我是路遥叶子,大家可以叫我叶子哦!❣️
📝个人主页:【路遥叶子的博客】
🏆博主信息:四季轮换叶,一路招摇胜!
专栏【安利Java零基础】
【数据结构-Java语言描述】
🐋希望大家多多支持😘一起进步呀!~❤️
🌈若有帮助,还请【关注➕点赞➕收藏】,不行的话我再努力努力呀!💪
————————————————
⚡版权声明:本文由【路遥叶子】原创、在CSDN首发、需要转载请联系博主。
🍁想寻找共同成长的小伙伴,请点击【Java全栈开放社区】
目录
🐋树的遍历
🌈 先根遍历
🌈 后根遍历
🌈 层次遍历
🐋 森林的遍历
🌲先根遍历
🌲后根遍历
🌲层次遍历
如果文章对您有帮助,就拿起小手赶紧给博主点赞💚评论❤️收藏💙 一下吧!
想要了解更多吗?没时间解释了,快来点一点!
🐋树的遍历
树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问,即依次对树中每个结点访问一次且仅访问一次。
树可被看成是由树的根结点和根结点的所有子树所构成的森林两部分组成。
树的遍历主要有:先根遍历、后根遍历、层次遍历。
🌈 先根遍历
-
若树为非空,则
-
访问根节点
-
从左到右依次先根遍历根节点的每一颗子树。
-
先根遍历序列:ABEFCDGHIJK
//先根遍历递归算法public void preRootTraverse(CSTreeNode T) { if(T != null) { System.out.print(T.data); preRootTraverse(T.firstChild);//先根遍历树中根节点的第一个子树 preRootTraverse(T.nextsibling);//先根遍历树中根节点的其他子树 }}
🌈 后根遍历
-
若树为非空,则
-
从左到右依次后根遍历根节点的每一棵子树
-
访问根节点
-
如上图:
后根遍历序列: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中遍历:
先根遍历
后根遍历
层次遍历
🌲先根遍历
顾名思义,先根遍历就是把根节点放在最前面的遍历方法,就是根节点->第一子树森林->其他森林的顺序来进行遍历。
-
若森林不空,则可依下列次序进行遍历:
-
访问森林中第一棵树的根节点
-
先序遍历第一课树中的子树森林
-
先序遍历除去第一棵树之后剩余的树构成的森林。
-
-
也就是说:依次从左到右对森林中的每一颗树进行先根遍历。
先根遍历顺序是:ABCEDFGHIJKL
🌲后根遍历
顾名思义,后根遍历就是把根节点放在最后面的遍历方法,就是第一子树森林->其他森林->根节点的顺序来进行遍历。
-
若森林不空,则可依下列次序进行遍历:
-
后根遍历第一棵树中的子树森林
-
后根遍历除去第一棵树之后剩余的树构成的森林。
-
访问森林中第一棵树的根节点
-
-
也就是说:依次从左至右对森林中的每一棵树进行后根遍历。
后根遍历序列是:BECDAGFIKLJH
🌲层次遍历
顾名思义,层次遍历就是按照每一棵树的每一层的顺序来进行遍历。
-
若森林为非空,则按从左到右的顺序对森林中每一颗树进行层次遍历。
-
也就是说:依次从左至右对森林中的每一棵树进行层次遍历。
层次遍历序列:ABCDEFGHIJKL
💚❤️💙💚❤❤️💙💚❤️❤💙💚❤️💙❤💚❤️💙💚❤❤️💙💚❤️❤💙❤️💙💚❤
如果文章对您有帮助,就拿起小手赶紧给博主点赞💚评论❤️收藏💙 一下吧!
想要了解更多吗?没时间解释了,快来点一点!
路遥叶子的博客_CSDN博客-数据结构,安利Java零基础,spring领域博主路遥叶子擅长数据结构,安利Java零基础,spring,等方面的知识,路遥叶子关注spring,spring boot,python,架构,java,mysql领域.https://blog.csdn.net/zsy3757486?spm=1000.2115.3001.5343