二分搜索樹的后續(xù)遍歷
- 先遍歷
node的左子樹贷揽，再遍歷node的右子樹美澳，最后遍歷node竞阐；對node的遍歷在左右子樹之后获洲，所謂后續(xù)遍歷阱表； - 對左右子樹的遍歷也是后續(xù)遍歷；
-
規(guī)模更小的同一個問題是：后序遍歷
node的左子樹贡珊，后序遍歷node的右子樹最爬； -
不能再縮小的基本問題是：對
node的處理；- 如果
node == null门岔，無可遍歷爱致； - 如果
node != null，在遍歷完node的左子樹和右子樹之后寒随，遍歷node糠悯；
- 如果
注意：不能再小的基本問題的代碼不一定就在方法的最前幾行，也可能夾雜在規(guī)模更小的問題的代碼（遞歸調(diào)用）的后面妻往；
// 二分搜索樹的后序遍歷
public void postOrder(){
postOrder(root);
}
// 后序遍歷以node為根的二分搜索樹, 遞歸算法
private void postOrder(Node node){
if(node == null)
return;
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}
測試代碼
public class 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);
/////////////////
// 5 //
// / \ //
// 3 6 //
// / \ \ //
// 2 4 8 //
/////////////////
bst.postOrder();
System.out.println();
}
}
輸出：
2
4
3
8
6
5
