无法在二叉树中插入数值。

huangapple go评论62阅读模式
英文:

Couldn't insert values in 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 <= root.val){
                if (root.left == null){
                    root.left = new Node(val);
                } else {
                    root.left.insert(val);
                }
            }
            // 如果值大于父节点的值,向右插入
            else {
                if (root.right == null){
                    root.right = new Node(val);
                } else {
                    root.right.insert(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(10);
        bt.insert(30);
        bt.insert(4);
        bt.insert(5);
        bt.displayTree(bt.root);
    }
}
英文:
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&#39;s val go left
if (val &lt;= root.val){
if (root.left == null){
root.left = new Node(val);
} else {
insert(val);
}
}
// If val greater than parent node&#39;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 + &quot; - &quot;);	
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);
}
}

I was trying to implement a binary search tree and came across a problem inserting values in it. I have implemented it before making a Node main class but now nesting a Node class inside of a main class (like a LinkedList) is complicating it.

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

Here in this bit current is always getting value of root which causes not more than 3 items to be inserted. I am aware of this problem but couldn't get around it. Any redesign in the code would be greatly appreciated.

答案1

得分: 1

你的代码中,在insert()方法中没有传递Node的引用,无法追踪当前树中的节点位置。

目前只能插入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);
    }
}
英文:

In your code you are not passing the reference of Node in insert() method to trace down at which node position you are in the current tree.

Currently you are able to insert only 3 items because for 3 items no recursion of insert(val) is getting used, but after 3 items you are using recursion of insert call and since in that you are not passing current node position this issue is coming.

Here is the working example of insertion in binary tree :

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 &lt;= 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 + &quot; - &quot;); 
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);
}
}

huangapple
  • 本文由 发表于 2020年9月25日 15:26:01
  • 转载请务必保留本文链接:https://go.coder-hub.com/64059686.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定