我在java中使用链表创建了一个二进制树，它根据树的高度插入值，即高度是偶数还是奇数。我写了一个代码，最初没有临时节点来将值插入根节点和其他左子树或右子树节点。但当我显示这个树时，输出并没有根节点，就好像它被覆盖了一样
下面是我的初始程序代码。专注于public void insert_node()功能。
import java.util.Scanner;
public class binary_tree {
private TreeNode root;
private int height = 0;
public static class TreeNode {
private int data;
private TreeNode left;
private TreeNode right;
public TreeNode(int user_input) {
this.data = user_input;
}
}
public void insertNode(TreeNode newnode) { // HERE....I have used only root.
if (root == null) {
root = newnode;
height += 1;
return;
}
if (height % 2 != 0) {
System.out.println(height);
while (root.left != null) {
root = root.left;
}
root.left = newnode;
height += 1;
return;
}
while (root.right != null) {
root = root.right;
}
root.right = newnode;
height += 1;
}
public void display(TreeNode rootnode) {
TreeNode temp = rootnode;
if (temp == null)
System.out.println("Tree Empty !!!");
else {
System.out.println("press 1 for LEFT SUBTREE npress 2 for RIGHT SUBTREE.");
Scanner sc = new Scanner(System.in);
int ch = sc.nextInt();
while (temp != null) {
System.out.println(temp.data + " $");
if (ch == 1)
temp = temp.left;
else
temp = temp.right;
}
}
System.out.println("Height of the tree = " + height);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
binary_tree bt = new binary_tree();
TreeNode newNode = new TreeNode(50);
bt.insertNode(newNode);
TreeNode newNode2 = new TreeNode(10);
bt.insertNode(newNode2);
TreeNode newNode3 = new TreeNode(100);
bt.insertNode(newNode3);
TreeNode newNode4 = new TreeNode(5);
bt.insertNode(newNode4);
TreeNode newNode5 = new TreeNode(1000);
bt.insertNode(newNode5);
bt.display(bt.root);
}
}
输出
press 1 for LEFT SUBTREE
press 2 for RIGHT SUBTREE.
3
10 $
1000 $
Height of the tree = 5
您可以在上面的代码中看到，缺少50 $，它本应是根节点。现在，如果我使用一个临时节点，在我的情况下是current_node，那么这个根节点以某种方式维持。请参阅下面代码中的。
import java.util.Scanner;
public class binary_tree {
private TreeNode root;
private int height = 0;
public static class TreeNode {
private int data;
private TreeNode left;
private TreeNode right;
public TreeNode(int user_input) {
this.data = user_input;
}
}
public void insertNode(TreeNode newnode) {
TreeNode current_node = root; //THIS IS THE TEMPORARY NODE
if (current_node == null) {
root = newnode;
height += 1;
return;
}
if (height % 2 != 0) {
System.out.println(height);
while (current_node.left != null) {
current_node = current_node.left;
}
current_node.left = newnode;
height += 1;
return;
}
while (current_node.right != null) {
current_node = current_node.right;
}
current_node.right = newnode;
height += 1;
}
public void display(TreeNode rootnode) {
TreeNode temp = rootnode;
if (temp == null)
System.out.println("Tree Empty !!!");
else {
System.out.println("press 1 for LEFT SUBTREE npress 2 for RIGHT SUBTREE.");
Scanner sc = new Scanner(System.in);
int ch = sc.nextInt();
while (temp != null) {
System.out.println(temp.data + " $");
if (ch == 1)
temp = temp.left;
else
temp = temp.right;
}
}
System.out.println("Height of the tree = " + height);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
binary_tree bt = new binary_tree();
TreeNode newNode = new TreeNode(50);
bt.insertNode(newNode);
TreeNode newNode2 = new TreeNode(10);
bt.insertNode(newNode2);
TreeNode newNode3 = new TreeNode(100);
bt.insertNode(newNode3);
TreeNode newNode4 = new TreeNode(5);
bt.insertNode(newNode4);
TreeNode newNode5 = new TreeNode(1000);
bt.insertNode(newNode5);
bt.display(bt.root);
}
}
输出
press 1 for LEFT SUBTREE
press 2 for RIGHT SUBTREE.
3
50 $
100 $
1000 $
Height of the tree = 5
有谁能告诉我这里发生了什么？current_node有什么不同？
为什么在链表中的节点中插入值时需要临时节点？
因为您正在遍历此处的树叶：
while (current_node.left != null) {
current_node = current_node.left;
}
current_node.left = newnode;
height += 1;
在这几行代码中，您试图找到最左边的叶子，以便插入newnode，对吗？你想使用一个变量来跟踪你当前所在的节点；向左走"；通过执行CCD_ 6。
您可以使用root来跟踪您所在的位置，但root已经有了一个目的——记录树的根！如果你做了root = root.left;，你就把原来根的左节点变成了新根！假设你的树是：
50
/
10 100
执行root = root.left会删除大部分内容：
10
这是有问题的，因为这意味着你的树本质上是"树"；忘记"；大约是树的一部分。从技术上讲，50和100节点仍然存在，50仍然连接到10，但您的binary_tree对象不再可以访问它。它唯一的访问点是root，您现在已经将其设置为节点10。
程序中实际发生的情况是：它正确地插入了50、10和100，然后在添加5时，尝试遍历左子树。这使得根"；10〃；，加5等于：
10
/
5
然后它正确地添加1000：
10
/
5 1000
因此它打印10和1000。
使用全新的变量可以解决这个问题，因为全新的变量与root无关。