資料結構 —— 二叉樹的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、前序周遊

思路：先根節點->左子樹->右子樹；

二叉樹如下圖：

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、中序周遊

思路：先左子樹->根節點->右子樹；

/**
	 *  中序周遊
	 */
    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、後序周遊

思路：先左子樹->右子樹->根節點；

/**
	 *  後序周遊
	 */
    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、層次周遊

思路：先根節點，然後第二層，第三層，依次往下走，（同層節點從左往右輸出）;

/**
	 * 層次周遊
	 */
	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