递归算法的迭代版本，以制作二叉树

Question

鉴于此算法，我想知道是否存在迭代版本。另外，我想知道迭代版本是否可以更快。

这种伪蟒...

算法返回对树根的引用

make_tree(array a)
  if len(a) == 0
        return None;

  node = pick a random point from the array
  calculate distances of the point against the others
  calculate median of such distances
  node.left = make_tree(subset of the array, such that the distance of points is lower to the median of distances)
  node.right = make_tree(subset, such the distance is greater or equal to the median)
  return node

Answer 1

只有一个递归调用的递归函数通常可以转换为尾递归函数而不需要太多努力，然后将它转换为迭代函数是微不足道的。这里的规范示例是阶乘：

# naïve recursion
def fac(n):
    if n <= 1:
        return 1
    else:
        return n * fac(n - 1)

# tail-recursive with accumulator
def fac(n):
    def fac_helper(m, k):
        if m <= 1:
            return k
        else:
            return fac_helper(m - 1, m * k)
    return fac_helper(n, 1)

# iterative with accumulator
def fac(n):
    k = 1
    while n > 1:
        n, k = n - 1, n * k
    return k

但是，这里的情况涉及两个递归调用，除非你重新编写算法，否则你需要保持堆栈。管理自己的堆栈可能比使用Python的函数调用堆栈快一些，但增加的速度和深度可能不值得复杂。这里的典型例子是Fibonacci序列：

# naïve recursion
def fib(n):
    if n <= 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

# tail-recursive with accumulator and stack
def fib(n):
    def fib_helper(m, k, stack):
        if m <= 1:
            if stack:
                m = stack.pop()
                return fib_helper(m, k + 1, stack)
            else:
                return k + 1
        else:
            stack.append(m - 2)
            return fib_helper(m - 1, k, stack)
    return fib_helper(n, 0, [])

# iterative with accumulator and stack
def fib(n):
    k, stack = 0, []
    while 1:
        if n <= 1:
            k = k + 1
            if stack:
                n = stack.pop()
            else:
                break
        else:
            stack.append(n - 2)
            n = n - 1
    return k

现在，你的情况要比这更难：一个简单的累加器将难以表达一个部分构建的树，其中指针指向需要生成子树的位置。你需要一个拉链 - 不容易用非实用的语言来实现蟒。

Answer 2

制作迭代版本只是使用自己的堆栈而不是普通的语言调用堆栈。我怀疑迭代版本会更快，因为普通的调用堆栈是为此目的而优化的。

Answer 3

您获得的数据是随机的，因此树可以是任意二叉树。对于这种情况，您可以使用线程二叉树，它可以遍历和构建，无需递归，也无需堆栈。节点具有标志，该标志指示链接是否是到另一节点的链接或如何到达“下一节点”。

来自 http://en.wikipedia.org/wiki/Threaded_binary_tree

Answer 4

取决于您如何定义“迭代”，还有前面答案未提及的另一种解决方案。如果是“迭代的”仅仅意味着“不受堆栈溢出异常的影响”。 （但是“允许使用'let rec'”），然后在支持尾调用的语言中，您可以使用continuation（而不是“显式堆栈”）编写版本。下面的F＃代码说明了这一点。它类似于您的原始问题，因为它从数组中构建BST。如果数组随机混洗，则树相对平衡，递归版本不会创建太深的堆栈。但是关闭shuffling，树变得不平衡，递归版本堆栈溢出，而迭代继续版本继续愉快。

#light 
open System

let printResults = false
let MAX = 20000
let shuffleIt = true

// handy helper function
let rng = new Random(0)
let shuffle (arr : array<'a>) = // '
    let n = arr.Length
    for x in 1..n do
        let i = n-x
        let j = rng.Next(i+1)
        let tmp = arr.[i]
        arr.[i] <- arr.[j]
        arr.[j] <- tmp

// Same random array
let sampleArray = Array.init MAX (fun x -> x) 
if shuffleIt then
    shuffle sampleArray

if printResults then
    printfn "Sample array is %A" sampleArray

// Tree type
type Tree =
    | Node of int * Tree * Tree
    | Leaf

// MakeTree1 is recursive
let rec MakeTree1 (arr : array<int>) lo hi =  // [lo,hi)
    if lo = hi then
        Leaf
    else
        let pivot = arr.[lo]
        // partition
        let mutable storeIndex = lo + 1
        for i in lo + 1 .. hi - 1 do
            if arr.[i] < pivot then
                let tmp = arr.[i]
                arr.[i] <- arr.[storeIndex]
                arr.[storeIndex] <- tmp 
                storeIndex <- storeIndex + 1
        Node(pivot, MakeTree1 arr (lo+1) storeIndex, MakeTree1 arr storeIndex hi)

// MakeTree2 has all tail calls (uses continuations rather than a stack, see
// http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!171.entry 
// for more explanation)
let MakeTree2 (arr : array<int>) lo hi =  // [lo,hi)
    let rec MakeTree2Helper (arr : array<int>) lo hi k =
        if lo = hi then
            k Leaf
        else
            let pivot = arr.[lo]
            // partition
            let storeIndex = ref(lo + 1)
            for i in lo + 1 .. hi - 1 do
                if arr.[i] < pivot then
                    let tmp = arr.[i]
                    arr.[i] <- arr.[!storeIndex]
                    arr.[!storeIndex] <- tmp 
                    storeIndex := !storeIndex + 1
            MakeTree2Helper arr (lo+1) !storeIndex (fun lacc ->
                MakeTree2Helper arr !storeIndex hi (fun racc ->
                    k (Node(pivot,lacc,racc))))
    MakeTree2Helper arr lo hi (fun x -> x)

// MakeTree2 never stack overflows
printfn "calling MakeTree2..."
let tree2 = MakeTree2 sampleArray 0 MAX
if printResults then
    printfn "MakeTree2 yields"
    printfn "%A" tree2

// MakeTree1 might stack overflow
printfn "calling MakeTree1..."
let tree1 = MakeTree1 sampleArray 0 MAX
if printResults then
    printfn "MakeTree1 yields"
    printfn "%A" tree1

printfn "Trees are equal: %A" (tree1 = tree2)

Answer 5

是的，可以迭代进行任何递归算法。隐式地，当您创建递归算法时，每次调用都会将先前的调用放入堆栈中。你想要做的是将隐式调用堆栈变为显式调用堆栈。迭代版本不一定会更快，但您不必担心堆栈溢出。 （在我的回答中，我是否获得了使用网站名称的徽章？

Answer 6

虽然在一般意义上确实直接将递归算法转换为迭代算法需要显式堆栈，但是有一个特定的算法子集，它们以迭代形式直接呈现（不需要堆栈） 。这些渲染可能没有相同的性能保证（迭代功能列表与递归解构），但它们确实存在。

Answer 7

这是基于堆栈的迭代解决方案（Java）：

public static Tree builtBSTFromSortedArray(int[] inputArray){

    Stack toBeDone=new Stack("sub trees to be created under these nodes");

    //initialize start and end 
    int start=0;
    int end=inputArray.length-1;

    //keep memoy of the position (in the array) of the previously created node
    int previous_end=end;
    int previous_start=start;

    //Create the result tree 
    Node root=new Node(inputArray[(start+end)/2]);
    Tree result=new Tree(root);
    while(root!=null){
        System.out.println("Current root="+root.data);

        //calculate last middle (last node position using the last start and last end)
        int last_mid=(previous_start+previous_end)/2;

        //*********** add left node to the previously created node ***********
        //calculate new start and new end positions
        //end is the previous index position minus 1
        end=last_mid-1; 
        //start will not change for left nodes generation
        start=previous_start; 
        //check if the index exists in the array and add the left node
        if (end>=start){
            root.left=new Node(inputArray[((start+end)/2)]);
            System.out.println("\tCurrent root.left="+root.left.data);
        }
        else
            root.left=null;
        //save previous_end value (to be used in right node creation)
        int previous_end_bck=previous_end;
        //update previous end
        previous_end=end;

        //*********** add right node to the previously created node ***********
        //get the initial value (inside the current iteration) of previous end
        end=previous_end_bck;
        //start is the previous index position plus one
        start=last_mid+1;
        //check if the index exists in the array and add the right node
        if (start<=end){
            root.right=new Node(inputArray[((start+end)/2)]);
            System.out.println("\tCurrent root.right="+root.right.data);
            //save the created node and its index position (start & end) in the array to toBeDone stack
            toBeDone.push(root.right);
            toBeDone.push(new Node(start));
            toBeDone.push(new Node(end));   
        }

        //*********** update the value of root ***********
        if (root.left!=null){
            root=root.left; 
        }
        else{
            if (toBeDone.top!=null) previous_end=toBeDone.pop().data;
            if (toBeDone.top!=null) previous_start=toBeDone.pop().data;
            root=toBeDone.pop();    
        }
    }
    return result;  
}