二叉树系列之——二叉树的递归遍历与非递归遍历

发表于 | 分类于 | | 阅读次数:

二叉树是一种非常重要的数据结构，由二叉树演变而来的树堆、红黑树、平衡树、SPlay伸展树等数据结构都在其各自适应领域有着广泛的应用。通过总结这一段时间对二叉树知识的学习，接下来将通过一系列二叉树专题的文章来进行归纳总结。
首先让我们来了解一下二叉树的遍历，二叉树有着先序、中序和后序三种遍历顺序，其中中序遍历更是可以直接将二叉树中元素以有序序列输出。因为二叉树本身就是一个递归的结构实现，所以我们可以使用递归很轻松地实现二叉树的三种遍历，同时也可以利用数据栈实现非递归的二叉树三种遍历。

建立二叉树

二叉树结构

1
2
3
4
5
6
7
8
9
10
11
typedef struct node
{
    int data;
    node *left, *right, *father;
    node(int data_) : data(data_)
    {
        left = NULL;
        right = NULL;
        father = NULL;
    }
}*Node;

这里定义了一个node结构表示二叉树中的一个结点，Node表示指向一个node结点的指针。

生成二叉树

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
Node insert(Node n, int data)
{
    if(root == NULL)
    {
        root = new node(data);
        return root;
    }
    else if(data < n->data)
    {
        if(n->left == NULL)
        {
            n->left = new node(data);
            n->left->father = n;
            return n->left;
        }
        else
            return insert(n->left, data);
    }
    else
    {
        if(n->right == NULL)
        {
            n->right = new node(data);
            n->right->father = n;
            return n->right;
        }
        else
            return insert(n->right, data);
    }
}

二叉树递归遍历

先序遍历

1
2
3
4
5
6
7
8
9
void PreOrder(Node n)
{
    if(n)
    {
        cout << n->data << " ";
        PreOrder(n->left);
        PreOrder(n->right);
    }
}

中序遍历

1
2
3
4
5
6
7
8
9
void MidOrder(Node n)
{
    if(n)
    {
        MidOrder(n->left);
        cout << n->data << " ";
        MidOrder(n->right);
    }
}

后序遍历

1
2
3
4
5
6
7
8
9
void PosrOrder(Node n)
{
    if(n)
    {
        PosrOrder(n->left);
        PosrOrder(n->right);
        cout << n->data << " ";
    }
}

由上述代码可以清楚看到，使用递归的方式进行二叉树的遍历是非常方便的，我们需要做的就是改变打印操作的位置。

二叉树非递归遍历

先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void PreOrder2()
{
    stack<Node> s;
    Node p = root;
    while(p || !s.empty())
    {
        while(p)
        {
            cout << p->data << " ";
            s.push(p);
            p = p->left;
        }
        if(!s.empty())
        {
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}
  • 从根节点开始访问打印结点数据，并将结点入栈；
  • 继续访问结点的左儿子结点，继续执行第一步打印入栈操作；
  • 如果左儿子结点为空，则进行出栈操作，将出栈结点右儿子结点入栈；
  • 直到当前结点为空并且栈为空的时候，结束遍历。

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void MidOrder2()
{
    stack<Node> s;
    Node p = root;
    while(p || !s.empty())
    {
        while(p)
        {
            s.push(p);
            p = p->left;
        }
        if(!s.empty())
        {
            p = s.top();
            s.pop();
            cout << p->data << " ";
            p = p->right;
        }
    }
}
  • 设置初始结点为根节点，依次访问其左儿子结点并依次入栈；
  • 若左儿子结点为空，则进行出栈操作，访问打印该结点数据；
  • 访问当前结点的右儿子结点，并进行第一步操作，继续访问其左儿子结点；
  • 直到当前结点为空并且栈为空，结束遍历。

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void PosrOrder2()
{
    stack<Node> s;
    Node pre, cur;
    s.push(root);
    while(!s.empty())
    {
        cur = s.top();
        if((cur->left == NULL && cur->right == NULL) || (pre && (pre == cur->left || pre == cur->right)))
        {
            cout << cur->data << " ";
            s.pop();
            pre = cur;
        }
        else
        {
            if(cur->right)
                s.push(cur->right);
            if(cur->left)
                s.push(cur->left);
        }
    }
}
  • 设置cur和pre两个结点指针，分别指向当前结点和前一个结点；
  • 如果当前结点curr没有左右儿子结点，则直接执行打印操作；
  • 或者前一结点pre是当前结点的左儿子或右儿子，也直接执行打印操作；
  • 否则，依次将当前结点的右儿子、左儿子依次入栈，先右后左保证先左后右的遍历顺序；
  • 如果栈为空则结束遍历操作；

完整代码

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
#include <iostream>
#include <stack>
using namespace std;

typedef struct node
{
    int data;
    node *left, *right, *father;
    node(int data_) : data(data_)
    {
        left = NULL;
        right = NULL;
        father = NULL;
    }
}*Node;

Node root = NULL;

Node insert(Node n, int data)
{
    if(root == NULL)
    {
        root = new node(data);
        return root;
    }
    else if(data < n->data)
    {
        if(n->left == NULL)
        {
            n->left = new node(data);
            n->left->father = n;
            return n->left;
        }
        else
            return insert(n->left, data);
    }
    else
    {
        if(n->right == NULL)
        {
            n->right = new node(data);
            n->right->father = n;
            return n->right;
        }
        else
            return insert(n->right, data);
    }
}

void PreOrder(Node n)
{
    if(n)
    {
        cout << n->data << " ";
        PreOrder(n->left);
        PreOrder(n->right);
    }
}

void MidOrder(Node n)
{
    if(n)
    {
        MidOrder(n->left);
        cout << n->data << " ";
        MidOrder(n->right);
    }
}

void PosrOrder(Node n)
{
    if(n)
    {
        PosrOrder(n->left);
        PosrOrder(n->right);
        cout << n->data << " ";
    }
}

void PreOrder2()
{
    stack<Node> s;
    Node p = root;
    while(p || !s.empty())
    {
        while(p)
        {
            cout << p->data << " ";
            s.push(p);
            p = p->left;
        }
        if(!s.empty())
        {
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}

void MidOrder2()
{
    stack<Node> s;
    Node p = root;
    while(p || !s.empty())
    {
        while(p)
        {
            s.push(p);
            p = p->left;
        }
        if(!s.empty())
        {
            p = s.top();
            s.pop();
            cout << p->data << " ";
            p = p->right;
        }
    }
}

void PosrOrder2()
{
    stack<Node> s;
    Node pre, cur;
    s.push(root);
    while(!s.empty())
    {
        cur = s.top();
        if((cur->left == NULL && cur->right == NULL) || (pre && (pre == cur->left || pre == cur->right)))
        {
            cout << cur->data << " ";
            s.pop();
            pre = cur;
        }
        else
        {
            if(cur->right)
                s.push(cur->right);
            if(cur->left)
                s.push(cur->left);
        }
    }
}

int main()
{
    int num;
    while(cin >> num)
    {
        insert(root, num);
    }
    cout << "前序遍历：" <<  endl;
    PreOrder(root);
    cout << endl;
    PreOrder2();
    cout << endl;

    cout << "中续遍历：" << endl;
    MidOrder(root);
    cout << endl;
    MidOrder2();
    cout << endl;

    cout << "后续遍历：" << endl;
    PosrOrder(root);
    cout << endl;
    PosrOrder2();
    cout << endl;

    return 0;
}
-------------本文结束感谢您的阅读-------------
0%