二叉树的遍历

本文涵盖二叉树的创建、先序、中序、后续（前三种分别给出递归与非递归算法）层序遍历。

#include <iostream>
#include <stack>
#include <queue>

using namespace std;
#define MAX_SIZE 100

typedef struct TreeNode
{
    int data;
    TreeNode *lchild, *rchild;
} TreeNode, *pTreeNode;

void create(pTreeNode &T, int *arr, int i)
{
    if (arr[i - 1] != 0)
    {
        T = new TreeNode();
        T->data = arr[i - 1];

        create(T->lchild, arr, 2 * i);       // 递归创建左子树
        create(T->rchild, arr, (2 * i) + 1); // 递归创建右子树
    }
    else // 当输入的数据为0，本程序代表为空结点
    {
        T = nullptr;
    }
}

// 递归先序遍历（根、左、右）
void PreOrder(pTreeNode tree)
{
    if (tree)
    {
        cout << tree->data << " ";
        PreOrder(tree->lchild);
        PreOrder(tree->rchild);
    }
}

// 非递归先序遍历
void PreOrder2(pTreeNode tree)
{
    stack<pTreeNode> st;
    pTreeNode p = tree;
    while (p || !st.empty()) // 栈不为空或者p不为空
    {
        if (p) // p不为空，则继续寻找左孩子，并将其入栈
        {
            cout << p->data << " ";
            st.push(p);
            p = p->lchild;
        }
        else
        {
            p = st.top()->rchild;
            st.pop();
        }
    }
}

// 递归中序遍历（左、根、右）
void InOrder(pTreeNode tree)
{
    if (tree)
    {
        InOrder(tree->lchild);
        cout << tree->data << " ";
        InOrder(tree->rchild);
    }
}

// 非递归中序遍历，用栈实现，建议手动模拟
void InOrder2(pTreeNode tree)
{
    stack<pTreeNode> st;
    pTreeNode p = tree;
    while (p || !st.empty()) // 栈不为空或者p不为空
    {
        if (p) // 如果p不为空，说明树上还有结点，将其存入栈中
        {
            st.push(p);
            p = p->lchild;
        }
        else
        {
            cout << st.top()->data << " "; // 访问栈顶元素
            p = st.top()->rchild;          // p指向右孩子
            st.pop();
        }
    }
}

// 递归后序遍历（左、右、根）
void PostOrder(pTreeNode tree)
{
    if (tree)
    {
        PostOrder(tree->lchild);
        PostOrder(tree->rchild);
        cout << tree->data << " ";
    }
}

// 非递归后续遍历
void PostOrder2(pTreeNode tree)
{
    stack<pTreeNode> st;
    pTreeNode p = tree;
    pTreeNode visited = nullptr; // 设置是否访问过结点标志位
    while (p || !st.empty())     // 如果p不为空，且栈不空
    {
        if (p) // p不为空，入栈，访问左孩子
        {
            st.push(p);
            p = p->lchild;
        }
        // 当前结点没有左孩子
        else
        {
            p = st.top(); // 获取当前栈顶结点
            // 如果该结点有右孩子，且该右孩子没有被访问过，那么将右孩子入栈
            if (p->rchild && p->rchild != visited)
            {
                p = p->rchild;
                st.push(p);
                p = p->lchild; // 访问当前结点的左孩子
            }
            // 如果该栈顶结点没有右孩子，或者有右孩子但已经被访问过（出栈当前子树的根节点），那么出栈
            else
            {
                visited = st.top(); // 设置该右孩子已经被访问过
                cout << visited->data << " ";
                st.pop();
                p = nullptr; // 结点已经出栈，置空（不置空会导致，出栈节点后，又回到外层if将其重新入栈）
            }
        }
    }
}
// 层序遍历
void LevelOrder(pTreeNode tree)
{
    queue<pTreeNode> qu;
    pTreeNode p = tree;
    qu.push(p); // 根节点入队
    while (!qu.empty())
    {
        cout << qu.front()->data << " "; // 输出队头
        if (qu.front()->lchild)          // 输出队头如果有左孩子，入队
        {
            qu.push(qu.front()->lchild);
        }
        if (qu.front()->rchild) // 输出队头如果有右孩子，入队
        {
            qu.push(qu.front()->rchild);
        }
        qu.pop();
    }
}

int main(int argc, char **argv)
{
    int arr[MAX_SIZE] = {1, 5, 2, 0, 6, 9, 7};
    pTreeNode tree;
    create(tree, arr, 1);
    cout << "PreOrder" << endl;
    PreOrder(tree);
    cout << endl;
    PreOrder2(tree);
    cout << endl;

    cout << "InOrder" << endl;
    InOrder(tree);
    cout << endl;
    InOrder2(tree);
    cout << endl;

    cout << "PostOrder" << endl;
    PostOrder(tree);
    cout << endl;
    PostOrder2(tree);
    cout << endl;

    cout << "LevelOrder" << endl;
    LevelOrder(tree);
    cout << endl;
    return 0;
}
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

本人能力有限，如有错误，望不吝指正；原创不易，欢迎转载，转载请注明出处