为什么我们在链表中的一个节点中插入值时需要一个临时节点？

Question

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

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有什么不同？

Answer 1

为什么我们在链表中的一个节点中插入值时需要一个临时节点？

因为您正在遍历树的叶子：

while (current_node.left != null) {
    current_node = current_node.left;
}
current_node.left = newnode;
height += 1;

在这几行代码中，您试图找到最左边的叶子，以便插入newnode，对吗？您希望使用一个变量来跟踪当前处于哪个节点上，并通过执行somevariable=somevariable.left；来“向左”。

    50
   /  \
  10  100

    10

在您的程序中实际发生的情况是：它正确地插入50、10和100，然后在添加5时，尝试向下遍历左边的子树。这使得根为“10”，加上5就变成了：

    10
   /
  5

然后正确地添加1000：

    10
   /  \
  5   1000

因此它打印10和1000。

使用全新的变量解决了这个问题，因为全新的变量与root无关。