用于制作二叉树的递归算法的迭代版本

Question

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

这是某种伪Python......

算法返回对树根的引用

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 的函数调用堆栈快一点，但增加的速度和深度可能不值得付出如此复杂的代价。 这里的典型示例是斐波那契数列：

# 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

现在，您的情况比这要困难得多：一个简单的累加器将难以用指向需要生成子树的指针来表达部分构建的树。 你需要一个zipper——用非真正功能性的语言来实现并不容易，比如Python。

Answer 2

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

Answer 3

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

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

Answer 4

根据您如何定义“迭代”，还有前面的答案未提及的另一个解决方案。 如果“迭代”仅意味着“不受堆栈溢出异常影响”（但“允许使用‘let rec’”），那么在支持尾部调用的语言中，您可以使用延续（而不是“显式”堆”）。 下面的 F# 代码说明了这一点。 它与您原来的问题类似，因为它从数组中构建了 BST。 如果数组随机打乱，则树相对平衡，并且递归版本不会创建太深的堆栈。 但是关闭洗牌，树就会变得不平衡，递归版本堆栈溢出，而迭代与延续版本则愉快地继续前进。

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