將（二叉搜索樹）的遞歸插入更改爲非遞歸？

Question

我想改變我的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; 
} 

我可以改變這個代碼轉換成非遞歸？

乾杯

Answer 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 
    } 
} 

其實之前也有一些很好的例子，你可能首先要檢查這些了：

• Write a non-recursive traversal of a Binary Search Tree using constant space and O(n) run time
• Nonrecursive/Iterative Binary Search Tree in C (Homework)

Answer 2

是的，你可以定義你插入功能的非遞歸。

但是，要做到這一點，您的插入函數將不得不爲遞歸定義的BST定義順序遍歷迭代器。

我相信有一種方法可以非遞歸地定義有序遍歷，但根據實現，這可能是非常低效的。

BST本身基本上是遞歸定義的，並且遞歸地定義插入函數總是有效的。 （如果你真的需要它，我可以編寫一些僞代碼，但我認爲這樣做毫無意義，我不知道你的順序遍歷迭代器的實現細節）

請不要忘記選擇這是一個答案:-)

Answer 3

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