二叉树遍历非递归算法

二叉树遍历非递归算法是指在不使用递归的情况下，实现对二叉树的遍历。常用的非递归算法有三种：非递归前序遍历、非递归中序遍历和非递归后序遍历。

以下是三种非递归遍历二叉树的算法：

1. 非递归前序遍历二叉树

void preOrderNRec(Tree root){
    Tree stack[MAXSIZE], node;
    int k = -1;
    if (root == NULL){
        printf("tree is empty-- \n");
        return;
    } else{
        k++; // 仿照一个栈
        stack[k] = root; // 将根节点入栈
        while (k > -1){ //出栈
            node = stack[k--];
            printf(" %c - ", node->data);
            // 先把右子树放进去，栈是先进去后出，所以下面的左子树先出
            if (node->right != NULL){
                stack[++k] = node->right;
            }
            if (node->left != NULL){
                stack[++k] = node->left;
            }
        }
    }
}

2. 非递归中序遍历二叉树

void inOrderNRec(Tree root){
    Tree stack[MAXSIZE], node;
    int k = -1;
    if (root == NULL){
        printf("tree is empty-- \n");
        return;
    } else{
        node = root;
        while (k > -1 || node != NULL){
            while (node != NULL){
                stack[++k] = node;
                node = node->left;
            }
            if (k > -1){
                node = stack[k--];
                printf(" %c - ", node->data);
                node = node->right;
            }
        }
    }
}

3. 非递归后序遍历二叉树

void postOrderNRec(Tree root){
    Tree stack[MAXSIZE], node, lastVisit;
    int k = -1;
    if (root == NULL){
        printf("tree is empty-- \n");
        return;
    } else{
        node = root;
        while (k > -1 || node != NULL){
            while (node != NULL){
                stack[++k] = node;
                node = node->left;
            }
            node = stack[k];
            if (node->right == NULL || node->right == lastVisit){
                printf(" %c - ", node->data);
                lastVisit = node;
                k--;
                node = NULL;
            } else{
                node = node->right;
            }
        }
    }
}