二叉树遍历的非递归实现

一、递归的定义及特点

递归是指某个函数直接或间接的调用自身。问题的求解过程就是划分成许多相同性质的子问题的求解，而小问题的求解过程可以很容易的求出。递归问题的关键是如何将原问题划分成子问题。递归实现时必须要找到递归出口，即递归终止的条件。

递归程序结构清晰、思路明了。但是递归的执行过程却很让人费解，递归程序的调试也很不方便。由于递归调用是对函数自身的调用，在一次调用没有结束之前又开始了另外一次调用，按照作用域的规定，函数在执行终止之前是不能收回所占用的空间，必须保存下来，这也就意味着每一次的调用都要把分配的相应空间保存起来。为了更好管理这些空间，系统内部设置一个栈，用于存放每次函数调用与返回所需的各种数据，其中主要包括函数的调用结束的返回地址，返回值，参数和局部变量等。反复的进栈和出栈导致了递归程序效率很低。

二、递归转非递归的实现

简单递归一般就是根据递归式来找出递推公式，使用循环的方法来实现。

复杂递归一般就是模拟系统处理递归的机制，使用栈来保存回朔点来求解。下面通过树形结构遍历的非递归实现来举例说明。

三、树形结构的先序、中序、后序非递归实现

void preorder(bitree *r)
        {
                sqstack *s;
                bitree *p;

                p = r;

                if (r == NULL)
                return;

                s = stack_create();
                if (s == NULL)
                return;

                while (p || !stack_empty(s))
                {
                        while (p)
                        {
                                printf("%d ", p->data);
                                push(s, p);
                                p = p->left;
                        }
                        if (!stack_empty(s))
                        {
                                p = pop(s);
                                p = p->right;
                        }
                }
        }

        void inorder(bitree *r)
        {
                sqstack *s;
                bitree *p;

                p = r;

                if (r == NULL)
                return;

                s = stack_create();
                if (s == NULL)
                return;

                while (p || !stack_empty(s))
                {
                        while (p)
                        {
                                push(s, p);
                                p = p->left;
                        }
                        if (!stack_empty(s))
                        {
                                p = pop(s);
                                printf("%d ", p->data);
                                p = p->right;
                        }
                }
        }

        void postorder(bitree *r)
        {
                sqstack *s;
                bitree *pre = NULL, *cur;

                if (r == NULL)
                return;

                s = stack_create();
                if (s == NULL)
                return;

                push(s, r);

                while (!stack_empty(s))
                {
                        cur = top(s);

                        if ((cur->left == NULL && cur->right == NULL) ||
                        (pre != NULL && (pre == cur->left || pre == cur->right)))
                        {
                                printf("%d ", cur->data);
                                pop(s);
                                pre = cur;
                        }
                        else
                        {
                                if (cur->right != NULL)
                                push(s, cur->right);
                                if (cur->left != NULL)
                                push(s, cur->left);
                        }
                }
        }