我无法弄清楚二叉树插入方法中的逻辑问题

Question

我尝试在 Java 中为二叉树开发一个简单的 insertOperation 我没有成功。

我的包包含三个类（Tree、Node 和 Main）怎么会有逻辑思维错误？我不需要记录不同的代码。在互联网上，有例子运行。我认为可能是运行但事实并非如此。

public class Node {

    Node left = null;
    Node right = null;
    float value = 0;

    public Node(float value) {

        this.value = value;
        left = null;
        right = null;
    }
}


import java.util.logging.Logger;

public class Tree {

    Logger log = Logger.getLogger(Tree.class.getName());

    Node root;

    public Tree() {
        root = null;
    }


    public void insert(Node node) {
    if (node == null) {
        throw new NullPointerException("Einzufügendes Objekt ist Null");
    }

    if (root == null) {
        root = node;

        log.info("root.value:" + root.value);

    } else if (root.value > node.value) {

        if (node.left == null) {

            root.left = node;
            log.info("node.left.value: " + root.left.value);
        }

        else {

            log.info("insert(root.left): " + root.left.value);
            insert(root.left);
        }

    } else {

        if (node.right == null) {

            root.right = node;
            log.info("node.right.value: " + root.right.value);
        }

        else {

            log.info("insert(node.right): " + root.right.value);

            insert(root.right);
        }
    }
}
}

预期结果是当我执行此操作时执行了我的 insertOperation 来自互联网的其他运行方法：

Juli 27, 2019 6:13:31 NACHM. Main main
INFORMATION: Rot:----------------------------
Juli 27, 2019 6:13:31 NACHM. Main main
INFORMATION: tree.root.value1.0
Juli 27, 2019 6:13:31 NACHM. Main main
INFORMATION: Linker Teilbaum:--------------------------
Juli 27, 2019 6:13:31 NACHM. Main main
INFORMATION: tree.root.left.value)-7.0
Juli 27, 2019 6:13:31 NACHM. Main main
INFORMATION: tree.root.left.left.value)-8.0
Juli 27, 2019 6:13:31 NACHM. Main main
INFORMATION: root.left.right.value-7.0
Juli 27, 2019 6:13:31 NACHM. Main main
INFORMATION: tree.root.left.right.right.value-0.4
Juli 27, 2019 6:13:31 NACHM. Main main
INFORMATION: Rechter Teilbaum:--------------------------
Juli 27, 2019 6:13:31 NACHM. Main main
INFORMATION: root.right.value2.0
Juli 27, 2019 6:13:31 NACHM. Main main
INFORMATION: root.right.right.value3.0
Juli 27, 2019 6:13:31 NACHM. Main main
INFORMATION: root.right.left.value1.0
Juli 27, 2019 6:13:31 NACHM. Main main
INFORMATION: root.right.right.right.value10.0

这是应该创建的树

     1
  /     \
-7       2

/ \ / \ -8 -7 1 3 \ \ -4 10

Answer 1

你有几个问题。

在下面的代码中查看我的评论。

            if (root.value < node.value) {
                if (node.right == null) {
                    root.right = new Node(node.value);
                    log.info("node.right.value:" + root.right.value);
                }
            } else { //<--- delete the right(}) curly brace.
                     // because your else clause is in the wrong place
                log.info("insert(node.right):" + root.right.value);
                insert(root.right);
            }
        }

正如我在评论中所说，您需要停止使用 root 进行比较。 root 不会更改以反映递归调用中的节点更改。所以你一遍又一遍地替换相同的值。

更新答案从这里开始。

这是我为使您的代码保持不变所能做的最好的事情。主要问题是您一遍又一遍地使用相同的 root 值。所以我添加了一个插入方法，它同时获取了根和节点。我不会这样做的。这就是我会做的。

首先通过 values，而不是 nodes 到插入方法。
创建一个 second insert method，其中包含 node 和 value。
如果 root 为空，则创建一个 node with the value 并赋值。
否则，递归调用 insert(node, value) 使用 left 或 right 视情况而定。如果null，创建一个有值的新节点并赋值。

这是您修改后的版本。我还添加了一个静态打印例程。

public class TreeDemo {

   public static void main(String[] args) {
      Tree t = new Tree();
      t.insert(new Node(-1));
      t.insert(new Node(5));
      t.insert(new Node(8));
      t.insert(new Node(-10));
      t.insert(new Node(4));
      t.insert(new Node(-3));
      t.insert(new Node(9));
      t.insert(new Node(12));

      print(t.root);

   }

   public static void print(Node n) {
      if (n.left != null) {
         print(n.left);
      }
      // print inorder
      System.out.println(n.value);
      if (n.right != null) {
         print(n.right);
      }
   }
}

class Node {

   Node  left  = null;
   Node  right = null;
   float value = 0;

   public Node(float value) {

      this.value = value;
      left = null;
      right = null;
   }
}

class Tree {

   Node root;

   public Tree() {
      root = null;
   }
   public void insert(Node node) {
      if (root == null) {
         root = node;
         return;
      }
      insert(root, node);
   }
   // added this method
   private void insert(Node troot, Node node) {

      if (troot.value > node.value) {
         if (troot.left == null) {
            troot.left = node;
         }
         else {
            insert(troot.left, node);
         }
      }
      else {
         if (troot.value <= node.value) {
            if (troot.right == null) {
               troot.right = node;
            }
            else {
               insert(troot.right, node);
            }
         }
      }
   }
}

我无法弄清楚二叉树插入方法中的逻辑问题

I am not able to figure out the logical problem in the insert method of binary tree

java

binary-tree