数据结构 —— 二叉树的4种遍历，java代码实现

文章目录

- 1、树的遍历分类
- 2、树的遍历
- - 2.1、定义节点
- 3、深度优先（DFS）
- - 3.1、前序遍历
  - 3.2、中序遍历
  - 3.3、后序遍历
- 4、广度优先（BFS）
- - 4.1、层次遍历
- 5、完整代码：

1、树的遍历分类

树的遍历分为两类：

深度优先（DFS）
- 前序遍历
- 中序遍历
- 后序遍历
广度优先（BFS）
- 层次遍历

2、树的遍历

2.1、定义节点

//节点数据结构
class TreeNode {
	
	String value = null;
	TreeNode leftchildren = null;
	TreeNode rightchildre = null;

	public TreeNode(String value, TreeNode leftchildren, TreeNode rightchildre) {
		this.value = value;
		this.leftchildren = leftchildren;
		this.rightchildre = rightchildre;
	}

	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 setRightchildre(TreeNode rightchildre) {
		this.rightchildre = rightchildre;
	}

	public String getValue() {
		return value;
	}

	public TreeNode getLeftchildren() {
		return leftchildren;
	}

	public TreeNode getRightchildre() {
		return rightchildre;
	}
}

3、深度优先（DFS）

3.1、前序遍历

思路：先根节点->左子树->右子树；

二叉树如下图：

数据结构 —— 二叉树的4种遍历，java代码实现

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 preorderVistTreeNode(TreeNode node) {
		if (null != node) {
            
			System.out.print(node.value);
            
			if (null != node.leftchildren) {
				preorderVistTreeNode(node.leftchildren);
			}
			if (null != node.rightchildre) {
				preorderVistTreeNode(node.rightchildre);
			}
		}
	}


	public static void main(String[] args) {
		
		TreeSearch treeSearch = new TreeSearch();
		TreeNode tree = treeSearch.getTargetTree();

		System.out.print("前序遍历:");
		treeSearch.preorderVistTreeNode(tree);
		System.out.println("");		
	}
}

运行结果：

先序遍历:ABDEGCFHI

3.2、中序遍历

思路：先左子树->根节点->右子树；

数据结构 —— 二叉树的4种遍历，java代码实现

/**
	 *  中序遍历
	 */
    public void inorderVistTreeNode(TreeNode node){
        if(null != node){
            if(null != node.leftchildren){
                inorderVistTreeNode(node.leftchildren);
            }
            
            System.out.print(node.value);
            
            if(null != node.rightchildre){
                inorderVistTreeNode(node.rightchildre);
            }
        }
    }

    public static void main(String[] args) {
       TreeSearch treeSearch = new TreeSearch();
       TreeNode tree= treeSearch.getTargetTree();
       
       System.out.print("中序遍历:");
       treeSearch.inorderVistTreeNode(tree);
       System.out.println("");
    }

运行结果：

中序遍历:DBGEACHFI

3.3、后序遍历

思路：先左子树->右子树->根节点；

数据结构 —— 二叉树的4种遍历，java代码实现

/**
	 *  后序遍历
	 */
    public void postorderVistTreeNode(TreeNode node){
        if(null != node){
            if(null != node.leftchildren){
                postorderVistTreeNode(node.leftchildren);
            }
            if(null != node.rightchildre){
                postorderVistTreeNode(node.rightchildre);
            }
            
            System.out.print(node.value);
            
        }
    }

    public static void main(String[] args) {
       TreeSearch treeSearch = new TreeSearch();
       TreeNode tree= treeSearch.getTargetTree();
       
       System.out.print("后序遍历:");
       treeSearch.postorderVistTreeNode(tree);
       System.out.println("");
    }

运行结果：

后序遍历:DGEBHIFCA

4、广度优先（BFS）

4.1、层次遍历

思路：先根节点，然后第二层，第三层，依次往下走，（同层节点从左往右输出）;

数据结构 —— 二叉树的4种遍历，java代码实现

/**
	 * 层次遍历
	 */
	public void levelorderVistTreeNode(TreeNode node) {
		if (null != node) {
			LinkedList<TreeNode> list = new LinkedList<TreeNode>();
			list.add(node);
			TreeNode currentNode;
			
			while (!list.isEmpty()) {
				currentNode = list.poll(); //获取并移除此列表的头
				
				System.out.print(currentNode.value);
				
				if (null != currentNode.leftchildren) {
					list.add(currentNode.leftchildren);
				}
				if (null != currentNode.rightchildre) {
					list.add(currentNode.rightchildre);
				}
			}
		}
	}

    public static void main(String[] args) {
       TreeSearch treeSearch = new TreeSearch();
       TreeNode tree= treeSearch.getTargetTree();
       
       System.out.print("层次遍历:");
       treeSearch.levelorderVistTreeNode(tree);
       System.out.println("");
    }

运行结果：

层序遍历:ABCDEFGHI

层序遍历二叉树，是非递归的队列实现的，就是利用队列的先进先出（FIFO）实现的。

5、完整代码：

package treenode3;

import java.util.LinkedList;

//节点数据结构
class TreeNode {
	
	String value = null;
	TreeNode leftchildren = null;
	TreeNode rightchildre = null;

	public TreeNode(String value, TreeNode leftchildren, TreeNode rightchildre) {
		this.value = value;
		this.leftchildren = leftchildren;
		this.rightchildre = rightchildre;
	}

	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 setRightchildre(TreeNode rightchildre) {
		this.rightchildre = rightchildre;
	}

	public String getValue() {
		return value;
	}

	public TreeNode getLeftchildren() {
		return leftchildren;
	}

	public TreeNode getRightchildre() {
		return rightchildre;
	}
}



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 preorderVistTreeNode(TreeNode node) {
		if (null != node) {
			
			System.out.print(node.value);
			
			if (null != node.leftchildren) {
				preorderVistTreeNode(node.leftchildren);
			}
			if (null != node.rightchildre) {
				preorderVistTreeNode(node.rightchildre);
			}
		}
	}

	/**
	 *  中序遍历
	 */
	public void inorderVistTreeNode(TreeNode node) {
		if (null != node) {
			if (null != node.leftchildren) {
				inorderVistTreeNode(node.leftchildren);
			}
			
			System.out.print(node.value);
			
			if (null != node.rightchildre) {
				inorderVistTreeNode(node.rightchildre);
			}
		}
	}

	/**
	 *  后序遍历
	 */
	public void postorderVistTreeNode(TreeNode node) {
		if (null != node) {
			if (null != node.leftchildren) {
				postorderVistTreeNode(node.leftchildren);
			}
			if (null != node.rightchildre) {
				postorderVistTreeNode(node.rightchildre);
			}
			
			System.out.print(node.value);
		}
	}

	/**
	 * 层次遍历
	 */
	public void levelorderVistTreeNode(TreeNode node) {
		if (null != node) {
			LinkedList<TreeNode> list = new LinkedList<TreeNode>();
			list.add(node);
			TreeNode currentNode;
			while (!list.isEmpty()) {
				
				currentNode = list.poll();
				
				System.out.print(currentNode.value);
				
				if (null != currentNode.leftchildren) {
					list.add(currentNode.leftchildren);
				}
				if (null != currentNode.rightchildre) {
					list.add(currentNode.rightchildre);
				}
			}
		}
	}

	public static void main(String[] args) {
		
		TreeSearch treeSearch = new TreeSearch();
		TreeNode tree = treeSearch.getTargetTree();

		System.out.print("前序遍历:");
		treeSearch.preorderVistTreeNode(tree);
		System.out.println("");

		System.out.print("中序遍历:");
		treeSearch.inorderVistTreeNode(tree);
		System.out.println("");

		System.out.print("后序遍历:");
		treeSearch.postorderVistTreeNode(tree);
		System.out.println("");
		
		System.out.print("层次遍历:");
		treeSearch.levelorderVistTreeNode(tree);
	}
}

运行结果：

前序遍历:ABDEGCFHI
中序遍历:DBGEACHFI
后序遍历:DGEBHIFCA
层次遍历:ABCDEFGHI

文章参考：https://blog.51cto.com/4837471/2327322

数据结构 —— 二叉树的4种遍历，java代码实现

文章目录

1、树的遍历分类

2、树的遍历

2.1、定义节点

3、深度优先（DFS）

3.1、前序遍历

3.2、中序遍历

3.3、后序遍历

4、广度优先（BFS）

4.1、层次遍历

5、完整代码：

继续阅读

树的基本概念(定义、基本术语、性质)

GSL--GNU Scientific Library

D5|哈希表，善用数据结构

如何成为一名.net 工程师?

BMP文件结构及图像每行字节计算方法

D. Ehab the Xorcist(构造+思维)

查找算法之二分查找查找算法之二分查找

JAVA高效编程指南

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【数据结构】医院选址

[转]ISUP信令的IAM消息详细内容

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器