树的广度优先遍历和深度优先遍历

引言

• 本文介绍了树的广度优先和深度优先遍历，并给出程序。

原理

• 广度优先遍历（BFT breadth-first traversal）：广度优先遍历是连通图的一种遍历策略，它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。树的广度优先遍历是指优先遍历完某一层的所有节点，然后再依次向下层遍历。
• 深度优先遍历（DFT depth-first traversal）：树的深度优先遍历是指首先遍历树的某个分支上的所有节点，在遍历另一个分支的节点，对于节点中的分支也这样处理。
• 广度优先和深度优先各有其侧重点，在不同的情境下可以选择使用。
• 本文不讨论广度优先和深度优先的适用场景，只给出两者的具体实现java代码，以供参考。

代码

package test;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

public class Test {

	//树的节点的定义
	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
	
	//构建树
	public static TreeNode BinaryTree(int[] array) {
		return makeBinaryTreeByArray(array, 1);
	}

	public static TreeNode makeBinaryTreeByArray(int[] array, int index) {
		if (index < array.length) {
			int value = array[index];
			if (value != 0) {
				TreeNode t = new TreeNode(value);
				array[index] = 0;
				t.left = makeBinaryTreeByArray(array, index * 2);
				t.right = makeBinaryTreeByArray(array, index * 2 + 1);
				return t;
			}
		}
		return null;
	}

	public static void levelOrderTraversal(TreeNode root) {
		// 用队列
		if (root == null) {
			return;
		}

		Queue<TreeNode> q1 = new ArrayDeque<>();
		q1.add(root);
		while (!q1.isEmpty()) {
			TreeNode tmp = q1.poll();
			System.out.print(tmp.val+" ");
			if (tmp.left != null) {
				q1.add(tmp.left);
			}

			if (tmp.right != null) {
				q1.add(tmp.right);
			}
		}
	}
	
	public static void depthOrderTraversal(TreeNode root){
		// 用栈
		if(root==null){
			return;
		}
		
		Stack<TreeNode> s = new Stack<>();
		s.push(root);
		while(!s.isEmpty()){
			TreeNode tmp = s.pop();
			System.out.print(tmp.val+" ");
			if(tmp.right!=null){
				s.push(tmp.right);
			}
			
			if(tmp.left!=null){
				s.push(tmp.left);
			}
		}
	}

	 /**       *                  13      *                 /  \      *               65    5      *              /  \    \      *             97  25   37      *            /    /\   /      *           22   4 28 32      */  
     *                  13 
     *                 /  \ 
     *               65    5 
     *              /  \    \ 
     *             97  25   37 
     *            /    /\   / 
     *           22   4 28 32 
     */
	public static void main(String[] args) {
		int[] arr = {0,13,65,5,97,25,0,37,22,0,4,28,0,0,32,0};
		TreeNode root = BinaryTree(arr);
		levelOrderTraversal(root);  //13 65 5 97 25 37 22 4 28 32 
		System.out.print("\n");
		depthOrderTraversal(root);  //13 65 97 22 25 4 28 5 37 32 
	}
}