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

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 不会更改以反射(reflect)递归调用中的节点更改。所以你不断地一遍又一遍地替换相同的值。

更新答案从这里开始。

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

1. 首先将值(而不是节点)传递给插入方法。
2. 创建一个第二个插入方法，它接受一个节点和值。
3. 如果root 为 null，则创建一个具有该值的节点 并为其分配值。
4. 否则，根据需要使用 left 或 right 递归调用 insert(node, value)。如果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);
            }
         }
      }
   }
}