0

我正在尝试将 BST 的递归插入方法更改为非递归（可能是 While 循环）更改的原因是因为我想看看它是否可能。

下面是插入代码：

public void insert(String value)
{
    //The node is stored in the root
    root = insert(value,root);
}


private Character insert(String value,Character current)
{   
    if(current == null)
    {
        //Add the root if the tree empty 
     current = new Character(value);
    }
    else
        //If the value that we want to insert < root value, then keep going to left till 
        //it's empty then inserted at left end. Done by recursion 
        if(value.compareTo(current.getElement())<=-1)
        {
            current.setLeft(insert(value,current.getLeft()));
        }
        else
            //If the value that we want to insert > root value, then keep going to right till 
            //it's empty then inserted at right end. Done by recursion 
            if(value.compareTo(current.getElement())>=1)
            {
                current.setRight(insert(value,current.getRight()));
            }
            else
            {
                //Else, the number we want to insert in already in the tree
                System.out.println("Duplicate numbers inserted" + current.getElement());
            }
    //returning the node tree so that we store it in the root 
    return current;
}

我可以将此代码更改为非递归吗？

干杯

4

3 回答 3

1

是的，您可以非递归地定义您的插入函数。

但是，要做到这一点，您的插入函数必须为 BST 定义按顺序遍历迭代器，该迭代器是递归定义的。

我相信有一种方法可以非递归地定义按顺序遍历，但是根据实现，这可能非常低效。

BST 本身基本上是递归定义的，递归定义插入函数总是很有效的。（如果你真的需要我可以写一些伪代码，但我认为它有点没有意义，我不知道你的中序遍历迭代器的实现细节）

请不要忘记选择这个作为答案:-)

于 2013-04-20T07:37:34.447 回答
1

是的，但是您需要稍微更改数据结构才能使其正常工作。节点必须知道它的左孩子和右孩子。

该算法如下所示：

current = root;
while(current != null){
   if(value.compareTo(current.getElement())<=-1)
   {
        current = current.left_child;
   }else if(value.compareTo(current.getElement())>=1){
        current = current.right_child;
   }else{
        // Duplication
   }
}

其实之前有一些很好的例子，你可能想先检查一下：

于 2013-04-20T07:41:15.960 回答
0

使用 while 循环插入

public Node insert(Node root,int n) {
  while (true) {
    if (root.data>n) {
      if (root.left==null) {
          root.left= new Node(n);
          return (root.left);
      }

      root=root.left;
    }
    else if (root.data<n) {
      if (root.right == null) {
          root.right= new Node(n);
      }
    }
  }
}
于 2017-08-27T16:35:49.883 回答