时间戳

首页 > 解决方案 > 二叉搜索树插入和打印需要第二意见

java - 二叉搜索树插入和打印需要第二意见

问题描述

我希望你今天过得很好。我需要第二个意见，用它的插入和打印方法来实现这个二叉搜索树。我知道我可以以一种可能有点令人费解的方式实现这一点，但我想知道我在哪里搞砸了。当我运行程序时，它输出以下内容：

Root value is: 3
Val inserted to left of root: 1
Val inserted at right node: 1
Root value is: 3
Val inserted at left node: 0
Root value is: 3
Val inserted to right of root: 4
Val inserted at right node: 4
Root value is: 3
Val inserted at right node: 5
0
1
1
3
4
4
5

我希望这个程序输出树 inOrder，输入为：3,1,0,4,5。

这是我现在拥有的代码，谢谢你的第二眼。

class tree {
    Node root = null;
    
    //Constructor
    tree(int value){
        root = new Node(value);
    }

    //insert
    void insertStart(int val){
        System.out.println("Root value is: "+root.value);
        //Check val against root & root has none children
        if(val < root.value && root.left == null){
            root.left = new Node(val);
            System.out.println("Val inserted to left of root: "+root.left.value);
        }

        if(val > root.value && root.right == null){
            root.right = new Node(val);
            System.out.println("Val inserted to right of root: "+root.right.value);
        }

        //Check val against root & root has two children
        if(val < root.value){
            //insertRecursion left
            insert(root.left, val);
        }else{
            //insertRecursion right
            insert(root.right, val);
        }
    }

    void insert(Node node, int val){
        //compare the node's value to val
        if(val < node.value){
            //check if left has children if yes call insert again else make new node with val
            if(node.left != null){
                insert(node.left, val);
            }else{
                node.left = new Node(val);
                System.out.println("Val inserted at left node: "+val);
            }
        }else{
            //check if right has children if yes call insert again else make new node with val
            if(node.right != null){
                insert(node.right, val);
            }else{
                node.right = new Node(val);
                System.out.println("Val inserted at right node: "+val);
            }
        }
    }

    //lookup -> return value else return null/zero/print no number here
    int lookUp(int val){
        System.out.println("Number not found");
        return 0;
    }
    //remove
    void remove(int val){

    }

    void printStart(){
        printInOrder(root);
    }

    void printInOrder(Node node){
        if(node == null){
            return;
        }   

        printInOrder(node.left);
        System.out.println(""+node.value);
        printInOrder(node.right);
    }

class Node {
    int value;
    Node left;
    Node right;
 
    Node(int value) {
        this.value = value;
        right = null;
        left = null;
    }

    }

}

public class binaryTree{
    public static void main(String[] args) {
        tree tree = new tree(3);
        tree.insertStart(1);
        tree.insertStart(0);
        tree.insertStart(4);
        tree.insertStart(5);
        tree.printStart();
        
    }
}

标签： javaalgorithmdata-structuresbinary-treebinary-search-tree

解决方案

检查注释以了解需要进行的更改。

void printPreOrder(Node node){ //rename method to printPreOrder
    if(node == null){
        return;
    }   

    System.out.println(""+node.value); //print here. If you print here it is preorder.
    printInOrder(node.left);
    //don't print here. If you print here it is inorder.
    printInOrder(node.right);
}

此外，在insertStart方法中，您应该在添加节点后返回。

    if(val < root.value && root.left == null){
        root.left = new Node(val);
        System.out.println("Val inserted to left of root: "+root.left.value);
        return; //add return here
    }

    if(val > root.value && root.right == null){
        root.right = new Node(val);
        System.out.println("Val inserted to right of root: "+root.right.value);
        return; //add return here
    }

如果你不添加上面提到的 return 语句，你会得到输出

3 1 0 1 4 4 5

代替

3 1 0 4 5

推荐阅读