Java基础 - 二叉树的遍历之深度优先遍历（递归遍历）

package com.yc.test; import java.util.ArrayList; import java.util.List; import com.yc.tree.ThreeLinkBinTree; import com.yc.tree.ThreeLinkBinTree.Node; /** * * @author wb * *遍历二叉树指的是按某种规律依次访问二叉树的每个节点，对二叉树的遍历过程就是将非线性结构的二叉树中的节点排列成线性序列的过程。 *如果采用顺序结构来保存二叉树，程序遍历二叉树将非常容易，无需进行任何思考，直接遍历底层数组即可。如果采用链表来保存二叉树的节点，则有以下两种遍历方式： * 深度优先遍历：这种遍历算法将先访问到树中最深层次的节点。 * 广度优先遍历：这种遍历算法将逐层访问每层的节点，先访问根节点，然后访问第二层的节点……以此类推。因此广度优先遍历又被称为按层遍历。 * *对于深度优先遍历算法而言，他可分为以下三种： *（1）先序遍历二叉树 *（2）中序遍历二叉树 *（3）后序遍历二叉树 * *如果L、D、R表示左子树、根、右子树，习惯上总是先遍历左子树，后遍历右子树，根据遍历根节点的顺序不同，上面三种方法可以表示如下： *DLR:先序遍历 *LDR:中序遍历 *LRD:后序遍历 * * ***************************************************************** * * 深度遍历的先序遍历、中序遍历、后序遍历这三种遍历方式的名称都是针对根节点（D）而言的。 * * *先处理根节点（D）时就称为先序遍历，其次处理根节点（D）是就称为中序遍历；最后处理根节点（D） * * *时就称为后序遍历。 * * ***************************************************************** * *因为二叉树的定义本身就具有“递归性”，所以深度优先遍历时能非常方便地利用递归来遍历每个节点：一棵非空二叉树由树根、 *左子树和右子树组成，依次遍历这三部分，就可以遍历整个二叉树。 * *下面以三叉链表结构的二叉树为例实现这三种遍历： */ public class DFS { @SuppressWarnings({ "rawtypes", "unused", "unchecked" }) public static void main(String[] args) { ThreeLinkBinTree<String> tree = new ThreeLinkBinTree<String>("A"); Node n2_l = tree.addAndReturn(tree.root(), "+", true); Node n2_r = tree.addAndReturn(tree.root(), "B", false); Node n3_n2_l = tree.addAndReturn(n2_l, "*", true); Node n3_n2_r = tree.addAndReturn(n2_l, "D", false); Node n4_n3_n2_l = tree.addAndReturn(n3_n2_l, "/", true); Node n4_n3_n2_r = tree.addAndReturn(n3_n2_l, "%", false); Node n5_n4_n3_n2_l = tree.addAndReturn(n4_n3_n2_r, "E", true); Node n5_n4_n3_n2_r = tree.addAndReturn(n4_n3_n2_r, "F", false); /** * 此时二叉树的情况为： * A * │ │ * + ←┘ └→ B * │ │ * * ←┘ └→ D * │ │ * / ←┘ └→ % * │ │ * E ←┘ └→ F * */ //先序遍历结果 System.out.println( "先序遍历结果:" + cDLR(tree) ); //中序遍历结果 System.out.println( "中序遍历结果:" + cLDR(tree) ); //后序遍历结果 System.out.println( "后序遍历结果:" + cLRD(tree) ); } //先序遍历 public static List<Node> cDLR(ThreeLinkBinTree<String> tree){ return dLR(tree.root()); } private static List<Node> dLR(Node node){ List<Node> nodes = new ArrayList<Node>(); nodes.add(node); if(node.getLeft() != null){ nodes.addAll(dLR(node.getLeft())); } if(node.getRight() != null){ nodes.addAll(dLR(node.getRight())); } return nodes; } //中序遍历 public static List<Node> cLDR(ThreeLinkBinTree<String> tree){ return lDR(tree.root()); } private static List<Node> lDR(Node node){ List<Node> nodes = new ArrayList<Node>(); if(node.getLeft() != null){ nodes.addAll(dLR(node.getLeft())); } nodes.add(node); if(node.getRight() != null){ nodes.addAll(dLR(node.getRight())); } return nodes; } //后序遍历 public static List<Node> cLRD(ThreeLinkBinTree<String> tree){ return lRD(tree.root()); } private static List<Node> lRD(Node node){ List<Node> nodes = new ArrayList<Node>(); if(node.getLeft() != null){ nodes.addAll(dLR(node.getLeft())); } if(node.getRight() != null){ nodes.addAll(dLR(node.getRight())); } nodes.add(node); return nodes; } }

测试结果为：

先序遍历结果:[A, +, *, /, %, E, F, D, B] 中序遍历结果:[+, *, /, %, E, F, D, A, B] 后序遍历结果:[+, *, /, %, E, F, D, B, A]