文章目录
1、树的遍历分类2、树的遍历
2.1、定义节点3、深度优先（DFS）
3.1、前序遍历3.2、中序遍历3.3、后序遍历4、广度优先（BFS）
4.1、层次遍历5、完整代码：
1、树的遍历分类
树的遍历分为两类：
深度优先（DFS）
前序遍历中序遍历后序遍历广度优先（BFS）
层次遍历
2、树的遍历
2.1、定义节点
public class TreeNode {
String value = null; // 根节点
TreeNode leftChildren = null; // 左子节点
TreeNode rightChildren = null; // 右子节点
public TreeNode(String value, TreeNode leftChildren, TreeNode rightChildren) {
this.value = value;
this.leftChildren = leftChildren;
this.rightChildren = rightChildren;
}
public TreeNode(String value) {
this.value = value;
}
public void setValue(String value) {
this.value = value;
}
public void setLeftChildren(TreeNode leftChildren) {
this.leftChildren = leftChildren;
}
public void setRightChildren(TreeNode rightChildren) {
this.rightChildren = rightChildren;
}
public String getValue() {
return value;
}
public TreeNode getLeftChildren() {
return leftChildren;
}
public TreeNode getRightChildren() {
return rightChildren;
}
}
3、深度优先（DFS）
3.1、前序遍历
思路：先根节点->左子树->右子树；
二叉树如下图：
public class TreeSearch {
public TreeNode getTargetTree() {
// 叶子节点
TreeNode G = new TreeNode("G");
TreeNode D = new TreeNode("D");
TreeNode E = new TreeNode("E", G, null);
TreeNode B = new TreeNode("B", D, E);
TreeNode H = new TreeNode("H");
TreeNode I = new TreeNode("I");
TreeNode F = new TreeNode("F", H, I);
TreeNode C = new TreeNode("C", null, F);
// 构造根节点
TreeNode root = new TreeNode("A", B, C);
return root;
}
/**
* 前序遍历 先根节点->左子树->右子树；
*/
public void preOrderVisitTreeNode(TreeNode node) {
if (null != node) {
System.out.print(node.value);
if (null != node.getLeftChildren()) {
preOrderVisitTreeNode(node.getLeftChildren());
}
if (null != node.getRightChildren()) {
preOrderVisitTreeNode(node.getRightChildren());
}
}
}
public static void main(String[] args) {
TreeTest treeSearch = new TreeTest();
TreeNode tree = treeSearch.getTargetTree();
System.out.print("前序遍历:");
treeSearch.preOrderVisitTreeNode(tree);
System.out.println("");
}
}
运行结果：
先序遍历:ABDEGCFHI
3.2、中序遍历
思路：先左子树->根节点->右子树；
/**
* 中序遍历 先左子树->根节点->右子树；
*/
public void inorderVisitTreeNode(TreeNode node) {
if (null != node) {
if (null != node.getLeftChildren()) {
inorderVisitTreeNode(node.getLeftChildren());
}
System.out.print(node.value);
if (null != node.getRightChildren()) {
inorderVisitTreeNode(node.getRightChildren());
}
}
}
public static void main(String[] args) {
TreeTest treeSearch = new TreeTest();
TreeNode tree = treeSearch.getTargetTree();
System.out.print("中序遍历:");
treeSearch.inorderVisitTreeNode(tree);
System.out.println("");
}
运行结果：
中序遍历:DBGEACHFI
1
3.3、后序遍历
思路：先左子树->右子树->根节点；
/**
* 后序遍历 先左子树->右子树->根节点；
*/
public void postOrderVisitTreeNode(TreeNode node) {
if (null != node) {
if (null != node.getLeftChildren()) {
postOrderVisitTreeNode(node.getLeftChildren());
}
if (null != node.getRightChildren()) {
postOrderVisitTreeNode(node.getRightChildren());
}
System.out.print(node.value);
}
}
public static void main(String[] args) {
TreeTest treeSearch = new TreeTest();
TreeNode tree= treeSearch.getTargetTree();
System.out.print("后序遍历:");
treeSearch.postOrderVisitTreeNode(tree);
System.out.println("");
}
运行结果：
后序遍历:DGEBHIFCA
1
4、广度优先（BFS）
4.1、层次遍历
思路：先根节点，然后第二层，第三层，依次往下走，（同层节点从左往右输出）;
运行结果：
层序遍历:ABCDEFGHI
层序遍历二叉树，是非递归的队列实现的，就是利用队列的先进先出（FIFO）实现的。
5、完整代码：
public class TreeNode {
String value = null; // 根节点
TreeNode leftChildren = null; // 左子节点
TreeNode rightChildren = null; // 右子节点
public TreeNode(String value, TreeNode leftChildren, TreeNode rightChildren) {
this.value = value;
this.leftChildren = leftChildren;
this.rightChildren = rightChildren;
}
public TreeNode(String value) {
this.value = value;
}
public void setValue(String value) {
this.value = value;
}
public void setLeftChildren(TreeNode leftChildren) {
this.leftChildren = leftChildren;
}
public void setRightChildren(TreeNode rightChildren) {
this.rightChildren = rightChildren;
}
public String getValue() {
return value;
}
public TreeNode getLeftChildren() {
return leftChildren;
}
public TreeNode getRightChildren() {
return rightChildren;
}
}
public class TreeTest {
public TreeNode getTargetTree() {
// 叶子节点
TreeNode G = new TreeNode("G");
TreeNode D = new TreeNode("D");
TreeNode E = new TreeNode("E", G, null);
TreeNode B = new TreeNode("B", D, E);
TreeNode H = new TreeNode("H");
TreeNode I = new TreeNode("I");
TreeNode F = new TreeNode("F", H, I);
TreeNode C = new TreeNode("C", null, F);
// 构造根节点
TreeNode root = new TreeNode("A", B, C);
return root;
}
/**
* 前序遍历 先根节点->左子树->右子树；
*/
public void preOrderVisitTreeNode(TreeNode node) {
if (null != node) {
System.out.print(node.value);
if (null != node.getLeftChildren()) {
preOrderVisitTreeNode(node.getLeftChildren());
}
if (null != node.getRightChildren()) {
preOrderVisitTreeNode(node.getRightChildren());
}
}
}
/**
* 中序遍历 先左子树->根节点->右子树；
*/
public void inorderVisitTreeNode(TreeNode node) {
if (null != node) {
if (null != node.getLeftChildren()) {
inorderVisitTreeNode(node.getLeftChildren());
}
System.out.print(node.value);
if (null != node.getRightChildren()) {
inorderVisitTreeNode(node.getRightChildren());
}
}
}
/**
* 后序遍历 先左子树->右子树->根节点；
*/
public void postOrderVisitTreeNode(TreeNode node) {
if (null != node) {
if (null != node.getLeftChildren()) {
postOrderVisitTreeNode(node.getLeftChildren());
}
if (null != node.getRightChildren()) {
postOrderVisitTreeNode(node.getRightChildren());
}
System.out.print(node.value);
}
}
/**
* 层次遍历
*/
public void levelOrderVisitTreeNode(TreeNode node) {
if (null != node) {
LinkedList
list.add(node);
TreeNode currentNode;
while (!list.isEmpty()) {
currentNode = list.poll();
System.out.print(currentNode.value);
if (null != currentNode.getLeftChildren()) {
list.add(currentNode.getLeftChildren());
}
if (null != currentNode.getRightChildren()) {
list.add(currentNode.getRightChildren());
}
}
}
}
public static void main(String[] args) {
TreeTest treeSearch = new TreeTest();
TreeNode tree = treeSearch.getTargetTree();
System.out.print("前序遍历:");
treeSearch.preOrderVisitTreeNode(tree);
System.out.println("");
System.out.print("中序遍历:");
treeSearch.inorderVisitTreeNode(tree);
System.out.println("");
System.out.print("后序遍历:");
treeSearch.postOrderVisitTreeNode(tree);
System.out.println("");
System.out.print("层次遍历:");
treeSearch.levelOrderVisitTreeNode(tree);
}
}
运行结果：
前序遍历:ABDEGCFHI
中序遍历:DBGEACHFI
后序遍历:DGEBHIFCA
层次遍历:ABCDEFGHI