Java大数据平台开发 学习笔记（29）—— 二叉查找树（BST）的构建与（前序、中序、后序）遍历

一、数据结构与算法：

---

Step 1) 创建 二叉排序树节点：

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value){
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

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

Step 2) 创建 二叉排序树 添加元素方法：

    public void add(Node node){
        if(node == null){
            return;
        }
        if(node.value < this.value){
            if(this.left == null){
                this.left = node;
            }else {
                this.left.add(node);
            }
        }else {
            if(this.right == null){
                this.right = node;
            }else {
                this.right.add(node);
            }
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Step 3) 提供 二叉树节点遍历方式：

    //前序遍历
    public void preNode(){
        System.out.println(this);
        if(this.left != null){
            this.left.preNode();
        }
        if(this.right != null){
            this.right.preNode();
        }
    }

    //中序遍历
    public void infixNode(){
        if(this.left != null){
            this.left.infixNode();
        }
        System.out.println(this);
        if(this.right != null){
            this.right.infixNode();
        }
    }

    //后序遍历
    public void postNode(){
        if(this.left != null){
            this.left.postNode();
        }
        if(this.right != null){
            this.right.postNode();
        }
        System.out.println(this);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

Step 4) 构建 根节点：

class BinrySortTree {
    private Node root;

    public void add(Node node){
        if (root == null){
            root = node;
        }else {
            root.add(node);
        }
    }

    public void preOrder(){
        if(this.root != null){
            this.root.preNode();
        }else{
            System.out.println("找不到根节点，无法遍历 ！！");
        }
    }

    public void infixOrder(){
        if(this.root != null){
            this.root.infixNode();
        }else{
            System.out.println("找不到根节点，无法遍历 ！！");
        }
    }

    public void postOrder(){
        if(this.root != null){
            this.root.postNode();
        }else{
            System.out.println("找不到根节点，无法遍历 ！！");
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

Step 5) main 方法：

public static void main(String[] args) {

     int[] arr = {7, 3, 10, 12, 5, 1, 9};
     BinrySortTree binrySortTree = new BinrySortTree();
     for (int i=0; i<arr.length; i++){
         binrySortTree.add(new Node(arr[i]));
     }

     System.out.println("前序遍历数组");
     binrySortTree.preOrder();

     System.out.println("中序遍历数组");
     binrySortTree.infixOrder();

     System.out.println("后序遍历数组");
     binrySortTree.postOrder();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

• 由 ChiKong_Tam 写于 2020 年 9 月 22 日