COMPX201-Assignment-2/StrBST.java at main · LittleVigney/COMPX201-Assignment-2 · GitHub

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
public class StrBST {
    Node root;

    public StrBST(){
        this.root = null;
    }

    public boolean empty(){
        return this.root == null;
    }

    public void insert(String goal){
        root = insertR(this.root, goal);
    }

    public Node insertR(Node currentRoot, String goal){
        // root is empty, add it here
        if (currentRoot== null){
            currentRoot= new Node(goal);
        }

        // goal is smaller than root
        if (goal.compareTo(currentRoot.value) < 0){
            currentRoot.left = insertR(currentRoot.left, goal);
        }

        // goal is greater than root
        if (goal.compareTo(currentRoot.value) > 0){
            currentRoot.right = insertR(currentRoot.right, goal);
        }

        return currentRoot;
    }

    public boolean search(String goal){
        return searchR(root, goal);
    }

    private boolean searchR(Node currentRoot, String goal){
        boolean res = false;

        if (currentRoot == null){
            return false;
        }
        else if (goal.compareTo(currentRoot.value) == 0){
            return true;
        }
        else if (goal.compareTo(currentRoot.value) < 0){
            res = searchR(currentRoot.left, goal);
        }
        else if (goal.compareTo(currentRoot.value) > 0){
            res = searchR(currentRoot.right, goal);
        }

        return res;
    }

    public void print(){
        printR(this.root);
    }

    private void printR(Node currentRoot){
        // reach null node or tree is empty
        if (currentRoot == null){
            return;
        }

        // print current node
        System.out.print("Root: " + currentRoot.value);

        // print left child
        if (currentRoot.left == null){
            System.out.print("| Left: null. ");
        }
        else{
            System.out.print("| Left: " + currentRoot.left.value + ". ");
        }

        // print right child
        if (currentRoot.right == null){
            System.out.print("| Right: null. ");
        }
        else{
            System.out.print("| Right: " + currentRoot.right.value + ". ");
        }

        System.out.println();

        // print left subtree
        printR(currentRoot.left);

        // print right subtree
        printR(currentRoot.right);
    }

    public void remove(String goal){
        root = removeR(this.root, goal);
    }

    public Node removeR(Node currentRoot, String goal){
        // if reach null node
        if (currentRoot == null){
            System.out.println("Goal is not in tree. Remove failed.");
            return null;
        }

        // if goal is smaller than currentRoot, enter left subtree
        if (goal.compareTo(currentRoot.value) < 0){
            currentRoot.left = removeR(currentRoot.left, goal);
        }
        // if goal is greater than currentRoot, enter right subtree
        else if (goal.compareTo(currentRoot.value) > 0){
            currentRoot.right = removeR(currentRoot.right, goal);
        }
        // if goal is found
        else if (goal.compareTo(currentRoot.value) == 0) {
            // if goal is leaf node
            if (currentRoot.left == null && currentRoot.right == null){
                currentRoot = null;
            }
            // if goal has one child
            else if (currentRoot.left == null && currentRoot.right != null){
                return currentRoot.right;
            }
            else if (currentRoot.left != null && currentRoot.right == null){
                return currentRoot.left;
            }
            // if goal has two child
            else if (currentRoot.left != null && currentRoot.right != null){
                // find the left most node of current root's right subtree
                Node newRoot = findLeftMost(currentRoot.right);

                // replace and remove the left most node
                currentRoot.value = newRoot.value;

                currentRoot.right = removeR(currentRoot.right, newRoot.value);
            }
        }

        return currentRoot;
    }

    // find the left most node
    public Node findLeftMost(Node goal){
        Node currentRoot = goal;

        while (currentRoot.left != null){
            currentRoot = currentRoot.left;
        }

        return currentRoot;
    }
}