C语言版：二叉树的遍历方式和逆序_后序遍历的逆序算法c语言

C语言版：数据结构中的二叉树，先序遍历，中序遍历，后序遍历，以及它们的逆序。

---

二叉树的遍历

二叉树的遍历方式：先序遍历：头左右，中序遍历：左头右， 后序遍历：左右头 的规则， 下面是本篇文章的二叉树的图。

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、栈的运用

栈的操作规则：先进后出，比如说进制转化也是栈的应用，前面文章有介绍关于进制转化，二叉树的逆序可以运用栈。

二、遍历方式

1.先序遍历

代码如下（示例）：

//正序
void perorder(RTreeNode* p)
{
	if (p != NULL)
	{
		printf("->%c", p->data);
		perorder(p->lchild);
		perorder(p->rchild);
	}//先序遍历
}

//逆序
void sperorder(RStack* S, RTreeNode* p)
{
	if (p != NULL)
	{
		push(S, p->data);//进栈
		sperorder(S, p->lchild);
		sperorder(S, p->rchild);
	}
}//树的遍历都需要进行递归，而结束递归的条件就是p指向空时候

//打印逆序的结果
void treeout(RStack p)
{
	while (!empty(&p))
	{
		printf("->%c", pop(&p));
	}
}
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

2.中序遍历

代码如下（示例）：

//正序
void perorder(RTreeNode* p)
{
	if (p != NULL)
	{
		perorder(p->lchild);
		printf("->%c", p->data);
		perorder(p->rchild);
	}//先序遍历
}

//逆序
void sperorder(RStack* S, RTreeNode* p)
{
	if (p != NULL)
	{
		sperorder(S, p->lchild);
		push(S, p->data);//进栈
		sperorder(S, p->rchild);
	}
}//树的遍历都需要进行递归，而结束递归的条件就是p指向空时候

//打印逆序的结果
void treeout(RStack p)
{
	while (!empty(&p))
	{
		printf("->%c", pop(&p));
	}
}
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

3.后序遍历

//正序
void perorder(RTreeNode* p)
{
	if (p != NULL)
	{
		perorder(p->lchild);
		perorder(p->rchild);
		printf("->%c", p->data);
	}//先序遍历
}

//逆序
void sperorder(RStack* S, RTreeNode* p)
{
	if (p != NULL)
	{
		sperorder(S, p->lchild);
		sperorder(S, p->rchild);
		push(S, p->data);//进栈
	}
}//树的遍历都需要进行递归，而结束递归的条件就是p指向空时候

//打印逆序的结果
void treeout(RStack p)
{
	while (!empty(&p))
	{
		printf("->%c", pop(&p));
	}
}
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

---

代码实现

//后续遍历的正序和逆序为例子
//
// Created by xhh on 2021/6/30.
//
#include<stdio.h>
#include<stdlib.h>
#include<process.h>
#include<string>
#define MAX 50

typedef struct TreeNode
{
    struct TreeNode* lchild, * rchild;  //左右子树指针
    char data;                  //结点内的元素
}RTreeNode;

//初始化一个树
RTreeNode* initnode(char x, RTreeNode* lchild, RTreeNode* rchild)
{
    RTreeNode* SS;
    SS = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    SS->data = x;
    SS->lchild = lchild;
    SS->rchild = rchild;
    return SS;
}

//定义一个栈
typedef struct Stack
{
    int top;                 //整形变量便于加减，移动方便
    char sa[MAX];           //栈的最大空间
}RStack;

//初始化一个栈
RStack init()
{
    RStack* SS;
    SS = (struct Stack*)malloc(sizeof(struct Stack));      //动态分配内存空间
    SS->top = 0;
    return *SS;
}

//进栈
void push(RStack *S, char x)
{
    if (S->top == MAX)
    {
        printf("the stack is full");
        exit(0);
    }
    S->sa[S->top] = x;              //top指向空栈，所以之间进入它指向的位置
    S->top++;
}

//出栈
char pop(RStack* S)
{
    if (S->top == 0)       //是否为空栈
    {
        printf("栈空了");
        exit(0);
    }

    return S->sa[--S->top];
}

//判断栈空
int empty(RStack* S)
{
    if (S->top == 0)
    {
        return 1;
    }
    return 0;
}

//清空栈元素
void clear(RStack* S)
{
    S->top = 0;
}

//生成一棵树
RTreeNode* inittree()
{
    RTreeNode* root, * b, * c, * d, * e, * f;
    d = initnode('D', NULL, NULL);
    e = initnode('E', NULL, NULL);
    f = initnode('F', NULL, NULL);
    b = initnode('B', d, NULL);
    c = initnode('C', e, f);
    root = initnode('A', b, c);       //只有唯一的跟结点，且放在最后
    return(root);
}

//正序
void perorder(RTreeNode* p)
{
    if (p != NULL)
    {
        perorder(p->lchild);
        perorder(p->rchild);
        printf("->%c", p->data);
    }//先序遍历
}

//逆序
void sperorder(RStack* S, RTreeNode* p)
{
    if (p != NULL)
    {

        sperorder(S, p->lchild);
        sperorder(S, p->rchild);
        push(S, p->data);//进栈
    }
}//树的遍历都需要进行递归，而结束递归的条件就是p指向空时候

void treeout(RStack p)
{
    while (!empty(&p))
    {
        printf("->%c", pop(&p));
    }
}

int main()
{
    RTreeNode* tree;
    tree = inittree();   //生成一颗树
    RStack SS;
    SS = init();       //生成了一个栈
    perorder(tree);
    printf("\n");
    sperorder(&SS, tree);
    treeout(SS);
    return 0;
}

后续遍历结果为：
正序：
->D->B->E->F->C->A
逆序：
->A->C->F->E->B->D
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

总结：先序，中序，后序遍历的方式只需要将printf函数和递归遍历换一下即可，逆序也是同样如此。