Java/Groovy二叉树插入

Question

我正试图写一个二叉树递归插入，但在过去的几个小时里我一无所获。我要么收到stackoverflow错误，要么没有插入所有项目

我想在我的树中插入以下值：

binaryTree.addNodeRecursion(new MNode(50, "fourth"))
binaryTree.addNodeRecursion(new MNode(25, "third"))
binaryTree.addNodeRecursion(new MNode(15, "second"))
binaryTree.addNodeRecursion(new MNode(10, "first"))
binaryTree.addNodeRecursion(new MNode(75, "fifth"))
binaryTree.addNodeRecursion(new MNode(85, "sixth"))

我希望在不将根作为参数传递的情况下执行此操作。因此，我的代码如下所示：

   public void addNodeRecursion(MNode newNode){

        if(root == null) {
            root = newNode
        }else{
            addRecurs(newNode); //this is the recursive function, it should not return a node object
        }
    }

注意，我说的不是二叉搜索树，而是二叉树，其中元素顺序不相关。我关心如何插入元素。我想插入它们，如下所示：

1 Step: 
            50

2 Step:
            50
           /
          25

3 Step:
            50
           /  \
          25  15

4 Step:
            50
           /  \
          25  15
         /
        10

5 Step:
            50
           /  \
          25  15
         /  \
        10  75

6 Step: (now notice that I am going back to the sibling of the current parent)

             50
           /   \
          25    15
         /  \   /
        10  75 85

下面是我的addRecurs函数：

private void addRecurs(MNode newNode) {

    if(newNode == null) { return };

    if(root.leftNode == null){ //Step 2 if the left node is null assign it
        root.leftNode = newNode 
    }else{ //Else that means the right Node is null
        root.rightNode = newNode // Step 3 set the right node
        root = root.leftNode // the the parent to the left node
        addRecurs(newNode) // repeat
    }

};

它不起作用

在不跟踪父变量或将其存储在变量中的情况下，是否可以完成此操作

Answer 1

我建议你用一种类似于aHeap的方式把你的树往后退。基本上是基于数组的树结构，您似乎不需要排序部分，因此它非常简单。为了得到更好的答案，我们需要更多的信息

Answer 2

你的问题是关于here的答案

static void addNode(node n)
{
    if(root==null)
    {
        root = n;
    }
    else
    {
        node tmp = root; // save the current root
        if(root.getValue()>n.getValue())
        {
            root = root.leftLink;
            addNode(n);
        }
        else if(root.getValue()<n.getValue())
        {
            root = root.rightLink;
            addNode(n);
        }
        root = tmp; // put the root back to its original value
    }
    return;
}