【实验目的】

使学生深入了解并掌握非线性数据结构的特点，掌握创建二叉树二叉链表存储结构的方法；同时深刻理解二叉树的各遍历过程。

【实验内容】

  1. 问题描述：很多涉及二叉树操作的算法都是以二叉树遍历为基础的。本实验要求编写程序，对一棵给定的二叉树进行先、中、后三种次序的遍历。
  2. 基本要求：以二叉链表为存储结构，实现二叉树的先、中、后三种次序的递归遍历。
  3. 实现提示：
    （１）设二叉树的结点不超过30个，每个结点的数据均为字符，这样可用先序遍历序列作为输入，顺序创建二叉树链表存储结构。
    （２）也可利用完全二叉树在顺序存储中的特性，创建二叉树的存储结构，此时，二叉树中结点数据的类型不受限制。
  4. 选作内容：
    （1）以二叉链表为存储结构，实现二叉树的先、中、后三种次序的非递归遍历。
    （2）借助队列，实现二叉树的层序遍历。
    （3）按凹入表或树形打印所遍历的二叉树。

【实验代码】

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
#include <iostream>
#include <stack>
#include <Queue>

using namespace std;

/*
 * 前序遍历数据
 * AB#D##C##
 * ABDG##H###CE#I##F##
 * ABDH#K###E##CFI###G#J##
*/
typedef struct BiNode {
    char data;
    BiNode *lChild, *rChild;
} BiNode, *BiTree;

void CreateTree(BiTree &T); // 创建二叉树
void PreOrderTraverse(BiTree T); //前序遍历
void InOrderTraverse(BiTree T); // 中序遍历
void PostOrderTraverse(BiTree T); // 后序遍历
void nonRecursivePre(BiTree T); //非递归前序遍历
void nonRecursiveIn(BiTree T); //非递归中序遍历
void nonRecursivePost(BiTree T); //非递归后序遍历
void levelOrderTraverse(BiTree T); // 层序遍历
void printT(BiTree T, int n); //凹入表打印树结构


int main() {
    BiTree T;
    cout << "创建二叉树，请输入前序遍历的树的数据：" << endl;
    CreateTree(T);

    cout << "\n前序遍历：" << endl;
    PreOrderTraverse(T);
    cout << "\n中序遍历：" << endl;
    InOrderTraverse(T);
    cout << "\n后序遍历：" << endl;
    PostOrderTraverse(T);

    cout << "\n非递归前序遍历：" << endl;
    nonRecursivePre(T);
    cout << "\n非递归中序遍历：" << endl;
    nonRecursiveIn(T);
    cout << "\n非递归后序遍历：" << endl;
    nonRecursivePost(T);

    cout << "\n层序遍历：" << endl;
    levelOrderTraverse(T);

    cout << "\n凹入表输出：" << endl;
    printT(T, 0);

    return 0;
}

void CreateTree(BiTree &T) // 创建二叉树
{
    char ch;
    cin >> ch;
    if (ch == '#') {
        T = NULL;
    } else {
        T = new BiNode;
        if (!T) {
            exit(-1);
        }

        T->data = ch;
        CreateTree(T->lChild);
        CreateTree(T->rChild);
    }
}

void PreOrderTraverse(BiTree T) //前序遍历
{
    if (T == NULL) {
        return;
    }

    cout << T->data;
    PreOrderTraverse(T->lChild);
    PreOrderTraverse(T->rChild);
}

void InOrderTraverse(BiTree T) // 中序遍历
{
    if (T == NULL) {
        return;
    }

    InOrderTraverse(T->lChild);
    cout << T->data;
    InOrderTraverse(T->rChild);
}

void PostOrderTraverse(BiTree T) // 后序遍历
{
    if (T == NULL) {
        return;
    }

    PostOrderTraverse(T->lChild);
    PostOrderTraverse(T->rChild);
    cout << T->data;
}

void nonRecursivePre(BiTree T) //非递归前序遍历
{
    if (T == NULL) {
        return;
    }
    BiNode *p = T;
    stack<BiNode *> s;

    while (!s.empty() || p) {
        while (p) // 当p不为空时，一边打印，一边往左走
        {
            cout << p->data;
            s.push(p);
            p = p->lChild;
        }

        if (!s.empty()) //p为空，说明此时的子树的根节点和左子树都遍历完了，进入右子树
        {
            p = s.top();
            s.pop();
            p = p->rChild;
        }
    }
}

void nonRecursiveIn(BiTree T) //非递归中序遍历
{
    if (T == NULL) {
        return;
    }
    BiNode *p = T;
    stack<BiNode *> s;

    while (!s.empty() || p) {
        while (p) // 当p不为空时，一边入栈，一边往左走
        {
            s.push(p);
            p = p->lChild;
        }

        if (!s.empty()) //p为空，说明此时左子树都遍历完了，走到了左边的最下端，需要出栈，进入右子树
        {
            p = s.top();
            s.pop();
            cout << p->data;
            p = p->rChild; //进入右子树，开始新遍历，一开始继续往左走
        }
    }
}

void nonRecursivePost(BiTree T) //非递归后序遍历
{
    if (T == NULL) {
        return;
    }
    stack<BiNode *> s;

    BiNode *pCur, *pLastVisit; //pCur为当前访问的结点，pLastVisit为上一个访问的结点
    pCur = T;
    pLastVisit = NULL;

    while (pCur) // 先入栈，到树的最左端
    {
        s.push(pCur);
        //pLastVisit = pCur;
        pCur = pCur->lChild;
    }

    //走到此处，pCur为空，到了树的最左端
    while (!s.empty()) {
        pCur = s.top();
        s.pop();

        if (pCur->rChild == NULL || pCur->rChild == pLastVisit) // 打印结点的前提是此结点无右子树或右子树已经被访问过了
        {
            cout << pCur->data;
            pLastVisit = pCur;
        } else //if (pCur->lChild == pLastVisit)
            /*
             * 若左子树被访问完，右边不符合上面的要求，则需要进入右子树，再开始遍历，记得一定不能有这个else-if的条件
            */
        {
            s.push(pCur);
            //pLastVisit = pCur;
            pCur = pCur->rChild;

            while (pCur) {
                s.push(pCur);
                //pLastVisit = pCur;
                pCur = pCur->lChild;
            }
        }
    }
}

void levelOrderTraverse(BiTree T) // 层序遍历
{
    queue<BiNode *> q;
    if (T) {
        q.push(T);
    }

    while (!q.empty()) {
        BiNode *p = q.front();
        cout << p->data;
        q.pop();
        if (p->lChild) {
            q.push(p->lChild);
        }
        if (p->rChild) {
            q.push(p->rChild);
        }
    }
}

void printT(BiTree T, int n) //凹入表打印树结构
{
    if (T) {
        printT(T->rChild, n + 1);
        for (int i = 0; i < n; i++) {
            cout << "   ";
        }
        if (n >= 0) {
            cout << T->data << endl;
        }
        printT(T->lChild, n + 1);
    }
}