BST树的经典问题——前、中、后序遍历_bst的前序遍历算法

BST树的经典问题——前、中、后序遍历
树的前中后序遍历是三种遍历打印BST的方式。
1、前序遍历是先打印根节点开始继续向下。先打印父节点，再以前序遍历的方式遍历下面的节点

如图是一个BST树，现在当对他进行前序遍历的时候，应该打印出如下数组
58 23 12 18 35 47 82 69 74 87 95
前序遍历特点：每一次都是先对根节点进行打印，即可以判断其根节点
代码实现如下：

public void preOder() {//前序遍历
    System.out.println("递归前序遍历");//先打印根
    preOder(this.root);
    System.out.println();
}

private void preOder(BSTNode<T> root) {
    if (this.root != null) {
        System.out.println(root.getData() + " ");
        preOder(root.getLeft());
        preOder(root.getRight());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2、中序遍历
12 18 23 35 47 58 69 74 82 87 95
中序遍历的特点：将数组以升序打印

代码实现：

public void midOder() {
    System.out.println("递归中序遍历");
    midOder(this.root);
    System.out.println();
}

private void midOder(BSTNode<T> root) {//中序遍历实现接口
    if (this.root != null) {
        midOder(root.getLeft());
        System.out.println(root.getData() + " ");
        midOder(root.getRight());
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

3、后序遍历
18 12 47 35 23 74 69 95 87 82 58
代码实现：

public void lastOrder(){
    lastOrder(root);
    System.out.println();
}
private void lastOrder(BSTNode<T> root) {
    if(null != root){
        lastOrder(root.getLeft());
        lastOrder(root.getRight());
        System.out.print(root.getData() + " ");
    }
}```


1
2
3
4
5
6
7
8
9
10
11
12
13