时间戳

首页 > 解决方案 > 无法在 BinaryTree 中插入值

java - 无法在 BinaryTree 中插入值

问题描述

class bTree {
    public class Node {
        Node left;
        Node right;
        int val;

        Node () {}
        Node (int val){
            this.val=val;
        }
    }

    Node root;

    public void insert(int val){
        if (root == null){
            root = new Node(val);
        } else {
            Node current = root;
            // If val less than parent node's val go left
            if (val <= root.val){
                if (root.left == null){
                    root.left = new Node(val);
                } else {
                    insert(val);
                }
            }
            // If val greater than parent node's val go right
            else {
                if (root.right == null){
                    root.right = new Node(val);
                } else {
                    insert(val);
                }
            }              // inner else ends
          }           // outer else ends
    }     // insert() ends

    public void displayTree(Node root){
   
        if (root.left != null){
            displayTree(root.left);
        }
        System.out.print(root.val + " - "); 
        if (root.right != null){
            displayTree(root.right);
        }

    }

    public static void main(String[] args) {
        bTree bt = new bTree();
        bt.insert(10);
        bt.insert(30);
        bt.insert(4);
        bt.insert(5);
        bt.displayTree(bt.root);
    }
}

我试图实现一个二叉搜索树并在其中插入值时遇到问题。我在创建 Node 主类之前已经实现了它，但现在在主类（如 LinkedList）中嵌套一个 Node 类会使它复杂化。

    public void insert(int val){
        if (root == null){
            root = new Node(val);
        } else {
            Node current = root;

在此位current中，始终获取root导致插入不超过 3 个项目的值。我知道这个问题，但无法解决。代码中的任何重新设计将不胜感激。

标签： javadata-structuresbinary-tree

解决方案

在您的代码中，您没有传递Nodeininsert()方法的引用来追踪您在当前树中的哪个节点位置。

目前，您只能插入 3 个项目，因为 3 个项目没有使用递归insert(val)，但是在 3 个项目之后，您正在使用insert调用递归，并且因为您没有传递当前节点位置，所以这个问题来了。

这是在二叉树中插入的工作示例：

class bTree {
    Node root;
    public class Node {
        Node left;
        Node right;
        int val;

        Node () {}
        Node (int val){
            this.val=val;
        }
    }

    public void insert(Node currnode, int val){
        if(currnode == null) {
            root = new Node(val);
            return;
        } 
        if(val <= currnode.val) {
            if(currnode.left == null) {
                currnode.left = new Node(val);
            } else {
                insert(currnode.left, val);
            }
            
        } else {
            if(currnode.right == null) {
                currnode.right = new Node(val);
            } else {
                insert(currnode.right, val);
            }
        }
    }

    public void displayTree(Node root){
   
        if (root.left != null){
            displayTree(root.left);
        }
        System.out.print(root.val + " - "); 
        if (root.right != null){
            displayTree(root.right);
        }
    }

    public static void main(String[] args) {
        bTree bt = new bTree();
        bt.insert(bt.root,10);
        bt.insert(bt.root,30);
        bt.insert(bt.root,4);
        bt.insert(bt.root,5);
        bt.displayTree(bt.root);
    }
}

推荐阅读