🐋树的遍历
树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次。
树可被看成是由树的根结点和根结点的所有子树所构成的森林两部分组成。
树的遍历主要有：先根遍历、后根遍历、层次遍历。
🌈 先根遍历
若树为非空，则
访问根节点
从左到右依次先根遍历根节点的每一颗子树。
先根遍历序列：ABEFCDGHIJK
//先根遍历递归算法 public void preRootTraverse(CSTreeNode T) { if(T != null) { System.out.print(T.data); preRootTraverse(T.firstChild); //先根遍历树中根节点的第一个子树 preRootTraverse(T.nextsibling); //先根遍历树中根节点的其他子树 } }
🌈 后根遍历
- 若树为非空，则
- 从左到右依次后根遍历根节点的每一棵子树
- 访问根节点
public void postRootTraverse(CSTreeNode t) { if(T != null) { postRootTraverse(T.firstChild); //后根遍历树中根节点的第一个子树 System.out.print(T.data); //访问数的根节点 postRootTraverse(T.nextsibling); //后根遍历树中根节点的其他子树 } }
🌈 层次遍历
- 若树为非空，则从根节点开始，从上到下依次访问每一层的各个结点，在同一层中的结点，则按从左到右的顺序依次进行访问。
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
