在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;
     } 

然而，当我遍历树时，我得到的答案是错误的。下面是遍历函数(preorder):

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

下面是Node类的定义:

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

如果我理解正确的话，你想用"层"来填充你的二叉树。例如，只有当深度3是"全二叉树"时，你才想把一些东西放入深度4。

那么问题是基于dfs的插入算法的整个逻辑。换句话说，它在一边越来越深地插入元素，而不是在两边都构建完整的二叉树。

如果你仔细观察你的插入算法，你会发现一旦你跳过"右"子树，你将永远不会返回到它-即使"左"子树已经是一个完整的二叉树。这就导致树在左边长得越来越深，而在右边却长不了。

用编程语言说话。你该怎么做:

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

，但你不能这样做(开始插入node.left)。如果节点。Left有子节点和节点。对没有孩子吗?即使你应该在node.right插入，你也会尝试向左侧插入。

所以你真正需要做的是基于bfs的插入。这意味着你将遍历树来"分层"插入。队列应该是你的新朋友:-)(不是堆栈/递归):

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);
     }
}

Answer 2

您的方法返回给定节点，但您的方法必须返回插入节点，即节点。