英文:
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'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);
}
}
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 <= 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);
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论