二叉树 二叉排序树的创建_pta程序填空5-2创建二叉排序树

思路：
将某个数作为根节点，比根大的放在根节点的右子叶，比根大的放在根节点的右子叶，每一个叶节点作为新的根节点进行递归，就会得到按照数大小排列的树

• 创建一个节点类，节点类三个属性，一个整型的value属性，用来保存数据，一个左节点，一个右节点

class TreeNode {
    int value;

    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
    }
}
1
2
3
4
5
6
7
8
9
10

• 创建树类，输有两个属性，一个根节点，一个size用来记录节点个数

class Tree {

    private TreeNode root;

    private int size;
    }
1
2
3
4
5
6

• 树有三个方法，添加,遍历输出，查看节点个数
• 首先创建add方法，先判断根节点是否为空，如果根节点为空，将添加的新节点作为根节点

    public void add(int val) {

        TreeNode newNode = new TreeNode(val);
        if (root == null) {

            root = newNode;

        } else {

            insert();

        }
     


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

• 如果根节点不为空，进行叶节点的插入，创建insert方法
• insert中有两个节点参数，子树的根和新插入的节点，将子根节点与新节点进行比较，如果新节点小于子根节点，看左子叶是否为空，如果左子叶为空，新节点作为左子叶节点，左子叶不为空，左子叶作为字根节点递归执行insert方法；如果如果新节点大于等于子根节点，看右子叶是否为空，如果右子叶为空，新节点作为右子叶节点，右子叶不为空，右子叶作为字根节点递归执行insert方法

private void insert(TreeNode childRoot, TreeNode newNode) {

       
        if (newNode.value < childRoot.value) {

            if (childRoot.left == null) {

                childRoot.left = newNode;

            } else {

                insert(childRoot.left, newNode);

            }

        } else {

            if (childRoot.right == null) {


                childRoot.right = newNode;


            } else {

                insert(childRoot.right, newNode);

            }


        }


    }
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

• 在add方法中使用insert插入每个子节点

 public void add(int val) {

        TreeNode newNode = new TreeNode(val);
        if (root == null) {

            root = newNode;

        } else {

            insert(root, newNode);

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

• 创建遍历节点方法，判断根节点是否为空，如果为直接返回空；如果根节点左节点不为空，递归遍历左子叶为根的树，如果根节点右节点不为空，递归遍历右子叶为根的树，直到遍历到最左（右）边的节点为空，输出父节点的value值

     private void getTree(TreeNode childRoot) {
        if (childRoot == null) {
            return;
        }
        if (childRoot.left != null) {
            view(childRoot.left);
        }
        System.out.println(childRoot.value);
        if (childRoot.right != null) {
            view(childRoot.right);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

全部代码如下：

class TreeNode {
    int value;

    TreeNode left;
    TreeNode right;

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

class Tree {

    private TreeNode root;

    private int size;

    private void insert(TreeNode childRoot, TreeNode newNode) {

       
        if (newNode.value < childRoot.value) {

            if (childRoot.left == null) {

                childRoot.left = newNode;

            } else {

                insert(childRoot.left, newNode);

            }

        } else {

            if (childRoot.right == null) {


                childRoot.right = newNode;


            } else {

                insert(childRoot.right, newNode);

            }


        }


    }

    public void add(int val) {

        TreeNode newNode = new TreeNode(val);
        if (root == null) {

            root = newNode;

        } else {

            insert(root, newNode);

        }
        size++;


    }

    public int getSize() {

        return size;

    }

     private void getTree(TreeNode childRoot) {
        if (childRoot == null) {
            return;
        }
        if (childRoot.left != null) {
            view(childRoot.left);
        }
        System.out.println(childRoot.value);
        if (childRoot.right != null) {
            view(childRoot.right);
        }
    }
        


    }

    public void getNode() {

        getTree(root);

    }


}

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

class TreeTest {

    public static void main(String[] args) {
        Tree tree = new Tree();
        tree.add(7);
        tree.add(9);
        tree.add(9);
        tree.add(13);
        tree.add(57);
        tree.add(67);
        tree.add(89);
        tree.add(89);
        tree.add(12);
        tree.add(5);
        tree.add(5);
        tree.add(4);
        tree.add(4);
        tree.add(57);

        System.out.println("tree.size() = " + tree.getSize());

        tree.getNode();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24