While revising for my final, I came across binary trees (regular ones). After going through the lecture, I started to solve previous labs.

My problem here is that only 6 is inserted into the tree. What is wrong with my method?

What I'm trying to input:

    tree.insert(1); tree.insert(15); tree.insert(7);
    tree.insert(13); tree.insert(58); tree.insert(6);

The Node class:

public class Node {
    public int key;
    public Node left_child;
    public Node right_child;

    // The Constructor(s).
    public Node() {
    }

    public Node(int key) {
        this.key = key;
        left_child = null;
        right_child = null;
    }

    // The Get Methods.
    public int getKey() {
        return key;
    }

    public Node getLeft_child() {
        return left_child;
    }

    public Node getRight_child() {
        return right_child;
    }

    // The Set Methods.
    public void setKey(int key) {
        this.key = key;
    }

    public void setLeft_child(Node left_child) {
        this.left_child = left_child;
    }

    public void setRight_child(Node right_child) {
        this.right_child = right_child;
    }
}

The BinaryTree class:

public class BinaryTree {
    private Node root;

    // The Constructor Method(s)
    public BinaryTree() {
        root = null;
    }

    public boolean is_empty() {
        return (root == null);
    }

    public void insert(int k) {
        insert(root, k);
    }

    private Node insert(Node x, int k) {
        Node p = new Node(k);
        if (x == null) {
            root = p;
        }
        else {
            if (x.left_child != null) {
                insert(x.left_child, k);
            }
            else {
                insert(x.right_child, k);
            }
        }
        return x;
    }

    // Printing Method(s).
    public void print_inorder() {
        print_inorder(root);
    }

    public void print_inorder(Node node) {
        if (node == null) {
            return;
        }
        print_inorder(node.left_child);
        System.out.print(node.key   " ");
        print_inorder(node.right_child);
    }

    public void print_preorder() {
        print_preorder(root);
    }

    public void print_preorder(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.key   " ");
        print_preorder(node.left_child);
        print_preorder(node.right_child);
    }

    public void print_postorder() {
        print_postorder(root);
    }

    public void print_postorder(Node node) {
        if (node == null) {
            return;
        }
        print_postorder(node.left_child);
        print_postorder(node.right_child);
        System.out.print(node.key   " ");
    }
}

CodePudding user response：

This will have a node to the left if a number is even and a node to the right if a node is odd.

I had to change your if condition because the way it was it was never going to use the left node.

private void insert(Node x, int k) {
        Node p = new Node(k);
        if (root == null) {
            this.root = p;
            return;
        }
        if (x.getKey() - k % 2 == 0) {
            if (x.left_child == null) {
                x.left_child = p;
            } else {
                insert(x.left_child, k);
            }
        } else {
            if (x.right_child == null) {
                x.right_child = p;
            } else {
                insert(x.right_child, k);
            }
        }
    }