遍历二叉树的非递归算法（C语言）

爱被打了一巴掌 2023-01-16 11:23 156阅读 0赞

在遍历二叉树时，使用递归简单易懂，但会耗费更多的时间以及空间，可考虑使用消除递归的方法。

一般我们用循环来代替递归，但在一些较为复杂的情况下，普通的循环已经难以支撑我们的需求。例如此种情况，我们用工作栈的方式来消除递归。

下面是非递归的中序与后序遍历。

输入时，以\#表示取消子树建立。

#include <stdio.h>
    #include <stdlib.h>
    #define StackMax 100
    
    typedef struct Node
    {
        
        char data;
        struct Node* LChild;
        struct Node* RChild;
    }BiNode, *BiTree;
    
    typedef struct
    {
        
        BiTree data[StackMax];
        int top;
    }Stack;
    
    BiTree CreateTree();          //建立二叉树
    void InitStack(Stack *S);    //栈的初始化
    int EmptyStack(Stack S);     //栈判空
    int FullStack(Stack S);      //栈判满
    void PushStack(Stack *S, BiTree T);  //入栈
    void PopStack(Stack *S, BiTree *T);  //出栈
    void GetTop(Stack S, BiTree *T);     //获取栈顶端元素
    void InPrintTree(BiTree T);  //中序遍历
    void InOrder(BiTree T);      //非递归中序遍历
    void PostPrintTree(BiTree T);//后序遍历
    void PostOrder(BiTree T);    //非递归后序遍历
    
    int main()
    {
        
        BiTree T;
        T = CreateTree();
        printf("\n中序：\n递归：  ");
        InPrintTree(T);  //递归中序
        printf("\n非递归：");
        InOrder(T);      //非递归中序
        printf("\n\n后序：\n递归：  ");
        PostPrintTree(T); //递归后序
        printf("\n非递归：");
        PostOrder(T);    //非递归后序
        return 0;
    }
    
    BiTree CreateTree()
    {
          //建立二叉树
        char c;
        c = getchar();
        BiTree T;
        if (c == '#') {
        
            return NULL;
        }
        else {
        
            T = (BiTree)malloc(sizeof(BiNode));
            T->data = c;
            T->LChild = CreateTree();
            T->RChild = CreateTree();
        }
        return T;
    }
    
    void InitStack(Stack *S)
    {
          //栈的初始化
        S->top = -1;
    }
    
    int IsEmptyStack(Stack S)
    {
          //栈判空
        if(S.top == -1) {
        
            return 1;
        }
        return 0;
    }
    
    int IsFullStack(Stack S)
    {
         //栈判满
        if (S.top == StackMax - 1) {
        
            return 1;
        }
        return 0;
    }
    
    void PushStack(Stack *S, BiTree T)
    {
          //入栈
        if (IsFullStack(*S)) {
        
            printf("ErrorFull ");
            return;
        }
        S->top++;
        S->data[S->top] = T;
    }
    
    void PopStack(Stack *S, BiTree *T)
    {
          //出栈
        if (IsEmptyStack(*S)) {
        
            printf("ErrorEmpty ");
            return;
        }
        (*T) = S->data[S->top];
        S->top--;
    }
    
    void GetTop(Stack S, BiTree *T)
    {
          //获取栈顶端元素
        if (IsEmptyStack(S)) {
        
            printf("ErrorEmpty ");
            return;
        }
        (*T) = S.data[S.top];
    }
    
    void InPrintTree(BiTree T)
    {
          //中序输出
        if (T == NULL) {
        
            return;
        }
        InPrintTree(T->LChild);
        printf("%c", T->data);
        InPrintTree(T->RChild);
    }
    
    
    void InOrder(BiTree T)
    {
          //非递归中序遍历
        Stack S;
        InitStack(&S);
        BiTree tmp;
        tmp = T;
        while (tmp != NULL || !IsEmptyStack(S)) {
        
            if (tmp != NULL) {
        
                PushStack(&S, tmp);
                tmp = tmp->LChild;
            }
            else {
        
                PopStack(&S, &tmp);
                printf("%c", tmp->data);
                tmp = tmp->RChild;
            }
        }
    }
    
    void PostPrintTree(BiTree T)
    {
          //后序输出
        if (T == NULL) {
        
            return;
        }
        PostPrintTree(T->LChild);
        PostPrintTree(T->RChild);
        printf("%c", T->data);
    }
    
    
    void PostOrder(BiTree T)
    {
          //非递归后序遍历
        Stack S;
        InitStack(&S);
        BiTree p, q;
        p = T;
        q = NULL;
        while(p != NULL || !IsEmptyStack(S)) {
        
            if (p != NULL) {
        
                PushStack(&S, p);
                p = p->LChild;
            }
            else {
        
                GetTop(S, &p);
                if (p->RChild != NULL && p->RChild != q) {
        
                    p = p->RChild;
                }
                else {
        
                    printf("%c", p->data);
                    q = p;
                    PopStack(&S, &p);
                    p = NULL;
                }
            }
        }
    }

运行截图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221022/5a36717109d24e9192baf99c03e63b1d.png