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

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 mainINFORMATION: Rot:----------------------------Juli 27, 2019 6:13:31 NACHM. Main mainINFORMATION: tree.root.value1.0Juli 27, 2019 6:13:31 NACHM. Main mainINFORMATION: Linker Teilbaum:--------------------------Juli 27, 2019 6:13:31 NACHM. Main mainINFORMATION: tree.root.left.value)-7.0Juli 27, 2019 6:13:31 NACHM. Main mainINFORMATION: tree.root.left.left.value)-8.0Juli 27, 2019 6:13:31 NACHM. Main mainINFORMATION: root.left.right.value-7.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 值。所以我添加了一个插入方法，它同时获取了根和节点。我不会这样做的。这就是我会做的。

1. 首先通过values，而不是nodes插入方法。

2. 制作一个second insert method需要 anode和的 a value。

3. 如果 theroot为 null，则创建 anode with the value并分配它。

4. insert(node, value)否则，根据需要递归调用using 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);

            }

         }

      }

   }

}