二叉树的前中后序遍历，递归和非递归方式_遍历算法流程图

作者：从前慢现在也慢 | 2024-05-26 08:07:27

踩

遍历算法流程图

数据结构系列：二叉树遍历

1. 思想介绍：

1.1递归介绍

用递归方式遍历二叉树。以递归方式对二叉树进行遍历时，算法的思路为：对整棵二叉树的遍历不断转化为对每个结点同样形式的遍历，从而实现对整棵二叉树的遍历。其思路简述如下：

(1)前序遍历
①: 访问根结点。
②: 对根结点的左子树进行前序遍历。
③: 对根结点的右子树进行前序遍历。

(2) 中序遍历
①: 对根结点的左子树进行中序遍历。
②: 访问根结点。
③: 对根结点的右子树进行中序遍历。

(3)后序遍历
①: 对根结点的左子树进行后序遍历。
②: 对根结点的右子树进行后序遍历。
③: 访问根结点。

1.2 非递归介绍

用递归方式遍历二叉树。以非递归方式对二叉树进行遍历的算法需要借助一个栈来存放访问过的结点。其思路简述如下：

(1)前序遍历
从整棵二叉树的根结点开始，对于任意结点VV，访问结点VV并将结点VV入栈，并判断结点VV的左子结点LL是否为空。若LL不为空，则将LL置为当前结点VV；若LL为空，则取出栈顶结点，并将栈顶结点的右子结点置为当前结点VV。重复上述操作，直到当前结点VV为空结点且栈为空，遍历结束。

(2)中序遍历
从整棵二叉树的根结点开始，对于任一结点VV，判断其左子结点LL是否为空。若LL不为空，则将VV入栈并将L置为当前结点VV；若LL为空，则取出栈顶结点并访问该栈顶结点，然后将其右子结点置为当前结点VV。重复上述操作，直到当前结点V为空结点且栈为空，遍历结束。

(3)后序遍历
首先将整棵二叉树的根结点入栈。取栈顶结点VV，若VV不存在左子结点和右子结点，或VV存在左子结点或右子结点，但其左子结点和右子结点都被访问过了，则访问结点VV，并将VV从栈中弹出。若非上述两种情况，则将VV的右子结点和左子结点依次入栈。重复上述操作，直到栈为空，遍历结束。

2. 算法流程图：

用递归方式对二叉树进行遍历的算法流程较为简单，流程图略。

**用非递归方式对二叉树进行先序遍历的算法流程图如图1所示。 **
在这里插入图片描述

图1: 用非递归方式对二叉树进行先序遍历的算法流程图

用非递归方式对二叉树进行中序遍历的算法流程图如图2所示。
在这里插入图片描述
图2: 用非递归方式对二叉树进行中序遍历的算法流程图

**用非递归方式对二叉树进行后序遍历的算法流程图如图3所示。 **
在这里插入图片描述
图3: 用非递归方式对二叉树进行后序遍历的算法流程图

第二步：代码演示

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define Stack_increment 20
#define Stack_Size 100  


typedef struct  Tree
{
    char data;
    struct Tree *lchild;
    struct Tree *rchild;
}Node;

Node* createBinaryTree()
{
    Node *root;
    char ch;
    scanf("%c", &ch);

    if (ch == '#')
    {
        root = NULL;
    }
    else
    {
        root = (Node *)malloc(sizeof(Node));
        root -> data = ch;
        root -> lchild = createBinaryTree();
        root -> rchild = createBinaryTree();        
    }

    return root;
}

typedef struct 
{
    int top;
    Node* arr[Stack_Size]; 
}Stacktree;

void InitStack(Stacktree *S)
{
    S->top = 0;
}

void Push(Stacktree* S, Node* x)
{
    int top1 = S -> top;
    if (x -> data == '#')
    {
        return;
    }
    else
    {
        S -> arr[top1++] = x;
        S -> top++;
    }
}

int Pop(Stacktree *S)
{
    int top = S -> top;
    if (S->top == 0)
    {
        return 0;
    }
    else
    {
        --(S->top);
        return 1;
    }
}

Node* GetTop(Stacktree *S)
{
    int top1 = S -> top;
    Node*p;
    p = S -> arr[top1--];
    return p;
}

Node* GetTop1(Stacktree *S)
{
    int top1 = S -> top;
    Node*p;
    top1--;
    p = S -> arr[top1];
    return p;
}

int IsEmpty(Stacktree *S)
{
    return(S->top == 0 ? 1 : 0);
}

void preorderRecursive(Node *p )
{
    if (p != NULL)
    {
        printf("%c ", p -> data);
        preorderRecursive(p -> lchild);
        preorderRecursive(p -> rchild);
    }
}

void inorderRecursive(Node *p )
{
    if (p != NULL)
    {
        inorderRecursive(p -> lchild);
        printf("%c ", p -> data);
        inorderRecursive(p -> rchild);
    }
}

void postorderRecursive(Node *p )
{
    if (p != NULL)
    {
        postorderRecursive(p -> lchild);
        postorderRecursive(p -> rchild);
        printf("%c ", p -> data);
    }
}

void preordernotRecursive(Node *p)
{
    if(p)
    {
        Stacktree stree ;
        InitStack(&stree);
        Node *root = p;
        while(root != NULL || !IsEmpty(&stree))
        {
            while(root != NULL)
            {
                printf("%c  ", root->data);
                Push(&stree, root);
                root = root -> lchild;
            }

            if(!IsEmpty(&stree))
            {
                Pop(&stree);
                root = GetTop(&stree);
                root = root -> rchild;
            }
        }
    }
}

void inordernotRecursive(Node *p)
{
    if(p)
    {
        Stacktree stree;
        InitStack(&stree);
        Node *root = p;
        while(root != NULL || !IsEmpty(&stree))
        {
            while(root != NULL)
            {
                Push(&stree, root);
                root = root -> lchild;
            }

            if(!IsEmpty(&stree))
            {
                Pop(&stree);
                root = GetTop(&stree);
                printf("%c  ", root -> data);
                root = root -> rchild;
            }
        }
    }
}

void postordernotRecursive(Node *p)
{
    Stacktree stree;
    InitStack(&stree);

    Node *root;    
    Node *pre = NULL;    

    Push(&stree, p);

    while (!IsEmpty(&stree))
    {
        root = GetTop1(&stree);

        if ((root -> lchild == NULL && root -> rchild == NULL) || (pre != NULL && (pre == root -> lchild || pre == root -> rchild)))
        {
            printf("%c ", root -> data);
            Pop(&stree);
            pre = root;
        }

        else
        {
            if (root -> rchild != NULL)
            {
                Push(&stree, root -> rchild);
            }

            if (root -> lchild != NULL)
            {
                Push(&stree, root -> lchild);
            }
        }

    }
}

void main()
{

    printf("请输入二叉树，'#'为空\n");   
    Node *root = createBinaryTree();

    printf("\n递归先序遍历:\n");
    preorderRecursive(root);

    printf("\n递归中序遍历:\n");
    inorderRecursive(root);

    printf("\n递归后序遍历:\n");
    postorderRecursive(root);

    printf("\n非递归先序遍历\n");
    preordernotRecursive(root);

    printf("\n非递归中序遍历\n");
    inordernotRecursive(root);

    printf("\n非递归后序遍历\n");
    postordernotRecursive(root);

    getchar();
    getchar();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244

三：程序运行展示

在这里插入图片描述
所用树形结构如为下图

转载博客地址：https://blog.csdn.net/asd20172016/article/details/80786186

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/625904