c - 如何在不使用递归的情况下平衡二叉搜索树与数组？

Question

我的问题是:如何检查数组中的元素？如何在数组上设置循环？

这是递归代码:

Tree BuildBalancedTree(Tree T, void **array, int inf, int sup, int(*comp)(void *, void *))
{
    int mid;

    if(inf < sup)
    {
        mid = (inf + sup) / 2;

        T = insertNode_it(T, array[mid], comp);

        T = BuildBalancedTree(T, array, inf, mid, comp);
        T = BuildBalancedTree(T, array, mid + 1, sup, comp);
    }

    return T;
}

编辑: 我想我找到了解决方法:

while((Top(st) != -1) || inf <= sup){

    while(inf <= sup){
        mid = (inf + sup) / 2;
        T = insertNode_it(T, array[mid], comp);     

        /* here i'm using a stack to store the array's boundaries */
        st = push_int(st, mid + 1);
        st = push_int(st, sup);         
        sup = mid - 1;

    }

    if((sup < inf) && (Top(st) != -1)){
        sup = Top(st);
        st = pop_int(st);

        inf = Top(st);
        st = pop_int(st);
    }

}

它确实有效。 但是你认为我应该改变一些东西吗？

Answer 1

根据定义，树是一种同构数据结构。这意味着它们“重复”自己，这使得它们非常适合递归。

此外，谈到递归和归纳之间的等价性，归纳是递归的一种特殊情况，称为尾递归，其中在方法末尾只有一次递归调用。对于树来说，需要2次递归调用，这使得转换为迭代形式变得更加困难。而且，迭代形式肯定比递归形式更复杂，而且效率可能更低。

由于上面所示的原因，由于没有与在树上遍历(或执行任何操作)所需的递归等效的直接迭代，因此迭代执行此操作的一种方法是通过使用充当调用的堆栈来模拟递归“真实”递归的堆栈。