二分搜尋樹周遊

前序周遊

//二分搜尋樹的前序周遊
public void preOrder() {
	preOrder(root);
}
//前序周遊以node為根的二分搜尋樹，遞歸算法
private void preOrder(Node node) {
	if(node==null)
		return;
	if(node!=null) {
		System.out.println(node.e);
		preOrder(node.left);
		preOrder(node.right);
	}
}

           

中序周遊

public void inOrder() {
	inOrder(root);
}
private void inOrder(Node node) {
	if(node==null)
		return;
	inOrder(node.left);
	System.out.println(node.e);
	inOrder(node.right);
	
}
           

後序周遊

//二分搜尋樹後序周遊
public void postOrder() {
	postOrder(root);
}
private void postOrder(Node node) {
	if(node==null)
		return;
	postOrder(node.left);
	postOrder(node.right);
	System.out.println(node.e);
}
           

main主函數測試

public static void main(String[] args) {
	BST<Integer>bst =new BST<>();
	int[] nums= {5,3,6,8,4,2};
	for(int num:nums) 
		bst.add(num);
	bst.preOrder();
	System.out.println();
	
	bst.inOrder();
	System.out.println();
	
	bst.postOrder();
	System.out.println();
//	System.out.println(bst);
}
           

深入了解二分搜尋樹周遊

第二次時記錄

第三次記錄

二分搜尋樹前序周遊非遞歸寫法

用棧 先根節點，再右孩子，再左孩子

複雜，應用不廣

//前序周遊非遞歸寫法
public void preOrderNR() {
	Stack<Node> stack=new Stack<>();
	stack.push(root);
	while(!stack.isEmpty()) {
		Node cur=stack.pop();
		System.out.println(cur.e);
		
		if(cur.right!=null)
			stack.push(cur.right);
		if(cur.left!=null)
			stack.push(cur.left);
	}
}
           

二分搜尋樹的層序周遊（廣度優先周遊）

用隊列 先根節點，再左孩子，再右孩子

意義：更快的找到某問題解決方法

常用于算法設計中——最短路徑

//二分搜尋樹的層序周遊
public void levelOrder() {
	Queue<Node> q = new LinkedList<>();
	q.add(root);
	while(!q.isEmpty()) {
	    Node cur =q.remove();
	    System.out.println(cur.e);
	    if(cur.left!=null)
	    	q.add(cur.left);
	    if(cur.right!=null)
	    	q.add(cur.right);
	}
}