在 Java 中的二叉树中插入元素

Question

我写了一段代码，可以在 java 中的二叉树中插入一个元素。以下是执行相同操作的函数：

 public void insert(int data)
    {
        root = insert(root, data);

    }

    private Node insert(Node node, int data)
     {
         if (node == null)
             node = new Node(data);
         else
         {
             if (node.getRight() == null)
                 node.right = insert(node.right, data);
             else
                 node.left = insert(node.left, data);             
         }
         return node;
     }

但是当我遍历这棵树时，我得到的答案是错误的。以下是遍历函数（预序）：

public void preorder()
     {
         preorder(root);
     }
     private void preorder(Node r)
     {
         if (r != null)
         {
             System.out.print(r.getData() +" ");
             preorder(r.getLeft());             
             preorder(r.getRight());
         }
     }

好的，这里是节点的定义 class:

public class Node {

    public int data;
    public Node left, right;

    /*  Constructor  */
    public Node() {
        left = null;
        right = null;
        data = 0;
    }
    /*  Constructor  */

    public Node(int d, Node l, Node r) {
        data = d;
        left = l;
        right = r;
    }

    //Constructor
    public Node(int d) {
        data = d;
    }

    /*  Function to set link to next Node  */

    public void setLeft(Node l) {
        left = l;
    }
    /*  Function to set link to previous Node  */

    public void setRight(Node r) {
        right = r;
    }
    /*  Function to set data to current Node  */

    public void setData(int d) {
        data = d;
    }
    /*  Function to get link to next node  */

    public Node getLeft() {
        return left;
    }
    /*  Function to get link to previous node  */

    public Node getRight() {
        return right;
    }
    /*  Function to get data from current Node  */

    public int getData() {
        return data;
    }
}

我已经多次重新检查遍历算法，它运行良好。我相信问题出在插入算法中。有什么建议吗？

Answer 1

您的方法 returns 给定节点，但您的方法必须 return 插入节点，即 node.right 或 node.left

Answer 2

如果我没理解错的话，你想在 "layers" 中填充你的二叉树。例如。仅当深度 3 为 "full binary tree".

时，你才想将某些内容放入深度 4

那么问题出在您的插入算法的整个逻辑上，即 DFS-based。换句话说，它在一侧越来越深地插入元素，而不是在两侧构建完整的二叉树。

如果仔细观察插入算法，您会发现一旦跳过 "right" 子树，就永远不会 return 到它 - 即使 "left" 子树已经满了二叉树。这导致树在左侧越来越深，但在右侧却没有生长。

用编程语言说话。你这样做：

(node.right != null) && (node.left != null) => insert (node.left)

但你不能这样做（开始插入 node.left）。如果 node.left 有两个 children 而 node.right 没有 children 怎么办？即使您应该在 node.right.

中插入，您也会尝试向左插入

所以你真正需要做的是插入BFS-based。这意味着您将遍历树以进行插入 "in layers"。队列应该是你的新朋友：-)（不是 stack/recursion）：

public void insert(int data) {
     if (root == null) {
         root = new Node(data);
         return;
     }

     Queue<Node> nodesToProcess = new LinkedList<>();
     nodesToProcess.add(root);

     while (true) {
         Node actualNode = nodesToProcess.poll();

         // Left child has precedence over right one
         if (actualNode.left == null) {
             actualNode.left = new Node(data);
             return;
         }
         if (actualNode.right == null) {
             actualNode.right = new Node(data);
             return;
         }

         // I have both children set, I will process them later if needed
         nodesToProcess.add(actualNode.left);
         nodesToProcess.add(actualNode.right);
     }
}

在 Java 中的二叉树中插入元素

Inserting Elements in Binary Tree in Java

java

algorithm

binary-tree

insertion