二叉树的非递归遍历 c语言

二叉树的非递归遍历可以使用栈来实现。具体实现方法如下：

1. 非递归先序遍历

先将根节点入栈，然后循环执行以下操作：

- 弹出栈顶元素并访问；
- 如果该元素有右子树，则将右子树入栈；
- 如果该元素有左子树，则将左子树入栈。

代码如下：

void PreOrder(BiTree T) {
    if (T == NULL) {
        return;
    }
    Stack s;
    InitStack(&s);
    Push(&s, T);
    while (!IsEmpty(s)) {
        BiTree p = Pop(&s);
        printf("%c ", p->data);
        if (p->rchild != NULL) {
            Push(&s, p->rchild);
        }
        if (p->lchild != NULL) {
            Push(&s, p->lchild);
        }
    }
}

2. 非递归中序遍历

先将根节点入栈，然后循环执行以下操作：

- 如果该元素有左子树，则将左子树入栈；
- 如果该元素没有左子树，则弹出栈顶元素并访问；
- 如果该元素有右子树，则将右子树入栈。

代码如下：

void InOrder(BiTree T) {
    if (T == NULL) {
        return;
    }
    Stack s;
    InitStack(&s);
    BiTree p = T;
    while (p != NULL || !IsEmpty(s)) {
        if (p != NULL) {
            Push(&s, p);
            p = p->lchild;
        } else {
            p = Pop(&s);
            printf("%c ", p->data);
            p = p->rchild;
        }
    }
}

3. 非递归后序遍历

先将根节点入栈，然后循环执行以下操作：

- 如果该元素有左子树，则将左子树入栈；
- 如果该元素有右子树，则将右子树入栈；
- 如果该元素没有左右子树或者左右子树都已经被访问过了，则弹出栈顶元素并访问。

代码如下：

void PostOrder(BiTree T) {
    if (T == NULL) {
        return;
    }
    Stack s;
    InitStack(&s);
    BiTree p = T;
    BiTree lastVisit = NULL;
    while (p != NULL || !IsEmpty(s)) {
        if (p != NULL) {
            Push(&s, p);
            p = p->lchild;
        } else {
            BiTree peek = GetTop(s);
            if (peek->rchild != NULL && lastVisit != peek->rchild) {
                p = peek->rchild;
            } else {
                printf("%c ", peek->data);
                lastVisit = Pop(&s);
            }
        }
    }
}