数据结构基础10-二叉树的创建与三种遍历-C/C++实现

前序遍历:根左右

中序遍历:左根右

后序遍历:左右根

一.二叉树的递归遍历

1.代码如下

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
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

typedef struct Tree {
	char data;// 数据
	struct Tree* leftchild;// 左子树
	struct Tree* rightchild;// 右子树
}tree, * treelist;
// 二叉树的创建
void createTree(treelist& app) {
	char ch;
	cin >> ch;
	if (ch == '#') {
		app = NULL;
	}
	else {
		app = new Tree;
		app->data = ch;
		createTree(app->leftchild);
		createTree(app->rightchild);
	}
}
// 先序遍历
void preorder(treelist app) {
	if (app == NULL) {
		return;
	}
	else {
		cout << app->data << "---";
		preorder(app->leftchild);
		preorder(app->rightchild);
	}
}
// 中序遍历
void inorder(treelist app) {
	if (app == NULL) {
		return;
	}
	else {
		preorder(app->leftchild);
		cout << app->data << "---";
		preorder(app->rightchild);
	}
}
// 后序遍历
void postorder(treelist app) {
	if (app == NULL) {
		return;
	}
	else {
		preorder(app->leftchild);
		preorder(app->rightchild);
		cout << app->data << "---";
	}
}
int main() {
	treelist app;
	cout << "请输入二叉树的数据" << endl;
	createTree(app);
	preorder(app);
	cout << "end" << endl;
	inorder(app);
	cout << "end" << endl;
	postorder(app);
	cout << "end" << endl;
	return 0;
}

2.参考数据:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A
B
C
#
#
D
#
#
E
F
#
#
G
#
#

3.参考结果:

1
2
3
A---B---C---D---E---F---G---end
B---C---D---A---E---F---G---end
B---C---D---E---F---G---A---end

二.利用栈对二叉树的先序遍历

不使用传统的递归的方法,采用栈的写法

先序,中序遍历

1.代码如下:

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
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

typedef struct Tree {
	char data;// 数据
	struct Tree* leftchild;// 左子树
	struct Tree* rightchild;// 右子树
}tree, * treelist;
// 栈的创建
typedef struct stacknode { 
	tree* data;
	struct stacknode* next;
}node,*stack;
// 二叉树的创建
void createTree(treelist& app) {
	char ch;
	cin >> ch;
	if (ch == '#') {
		app = NULL;
	}
	else {
		app = new Tree;
		app->data = ch;
		createTree(app->leftchild);
		createTree(app->rightchild);
	}
}
// 初始化栈
void initstack(stack root) {
	root->data = NULL;
	root->next = NULL;
}
// 在栈中加入一些数据
void pushstack(stack root, tree* app) {
	node* stackapp = (node*)malloc(sizeof(node));
	stackapp->data = app;
	stackapp->next = root->next;
	root->next = stackapp;
}
// 判断栈是否为空
bool isempty(stack root) {
	if (root->next == NULL) {
		return true;
	}else {
		return false;
	}
}
// 将栈中的数据拿出来
node* popstack(stack root) {
	if (isempty(root)) {
		return NULL;
	}
	else {
		node* app = root->next;
		root->next = app->next;
		return app;
	}
}
// 先序遍历
// 基本思想很简单
void preorder(treelist app) {
	treelist APP = app;
	stack stackAPP = new node;
	initstack(stackAPP);
	while (APP || !isempty(stackAPP)) {
		if (APP) {
			cout << APP->data << "---";
			pushstack(stackAPP,APP);
			APP = APP->leftchild;
		}
		else {
			APP = popstack(stackAPP)->data;
			APP = APP->rightchild;
		}
	}
}
// 中序遍历
// 基本思想就是到左子树遍历到null的时候就出栈,打印出数据,只要为空就打印出栈中的数据
void inorder(treelist app) {
	treelist APP = app;
	stack stackAPP = new node;
	initstack(stackAPP);
	while (APP || !isempty(stackAPP)) {
		if (APP) {
			pushstack(stackAPP,APP);
			APP = APP->leftchild;
		}
		else {
			APP = popstack(stackAPP)->data;
			cout << APP->data << "---";
			APP = APP->rightchild;
		}
	}
}
int main() {
	treelist app;
	cout << "请输入二叉树的数据" << endl;
	createTree(app);
	preorder(app);
	cout << "end" << endl;
	inorder(app);
	cout << "end" << endl;
	return 0;
}

2.参考数据:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A
B
C
#
#
D
#
#
E
F
#
#
G
#
#

3.参考结果:

1
2
A---B---C---D---E---F---G---end
C---B---D---A---F---E---G---end

后序遍历

1.代码如下

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
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

typedef struct Tree {
	char data;// 数据
	struct Tree* leftchild;// 左子树
	struct Tree* rightchild;// 右子树
	bool flag;// 用来标志是否被访问过
}tree, * treelist;
// 栈的创建
typedef struct stacknode {
	tree* data;
	struct stacknode* next;
}node, * stack;
// 二叉树的创建
void createTree(treelist& app) {
	char ch;
	cin >> ch;
	if (ch == '#') {
		app = NULL;
	}
	else {
		app = new Tree;
		app->data = ch;
		app->flag = false;
		createTree(app->leftchild);
		createTree(app->rightchild);
	}
}
// 初始化栈
void initstack(stack root) {
	root->data = NULL;
	root->next = NULL;
}
// 在栈中加入一些数据
void pushstack(stack root, tree* app) {
	node* stackapp = (node*)malloc(sizeof(node));
	stackapp->data = app;
	stackapp->next = root->next;
	root->next = stackapp;
}
// 判断栈是否为空
bool isempty(stack root) {
	if (root->next == NULL) {
		return true;
	}
	else {
		return false;
	}
}
// 将栈中的数据拿出来
node* popstack(stack root) {
	if (isempty(root)) {
		return NULL;
	}
	else {
		node* app = root->next;
		root->next = app->next;
		return app;
	}
}
// 将栈中的数据拿来看一下,不是真正的拿出来
node* getstack(stack root) {
	if (isempty(root)) {
		return NULL;
	}
	else {
		node* app = root->next;
		return app;
	}
}

// 后序遍历
// 基本思想就是判断这个数据在遍历到左边最后一个数据的时候,父节点的右子树是否有,如果没有的话就直接输出,没有的话就判断右子树的......
void postorder(treelist app) {
	treelist APP = app;
	stack stackAPP = new node;
	initstack(stackAPP);
	while (APP || !isempty(stackAPP)) {
		if (APP) {
			pushstack(stackAPP, APP);
			APP = APP->leftchild;
		}else {
			treelist top = getstack(stackAPP)->data;
			if (top->rightchild && top->rightchild->flag == false) {
				top = top->rightchild;
				pushstack(stackAPP, top);
				APP = top->leftchild;
			}
			else {
				top = popstack(stackAPP)->data;
				cout << top->data << "---";
				top->flag = true;
			}
		}
	}
}
int main() {
	treelist app;
	cout << "请输入二叉树的数据" << endl;
	createTree(app);
	postorder(app);
	cout << "end" << endl;
	return 0;
}

4参考数据:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A
B
C
#
#
D
#
#
E
F
#
#
G
#
#

3参考结果:

1
C---D---B---F---G---E---A---end

三.Morris 中序遍历

思路与算法

Morris 遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为 O(1)。

Morris 遍历算法整体步骤如下（假设当前遍历到的节点为 x）：

如果 x 无左孩子，先将 x 的值加入答案数组，再访问 x 的右孩子，即 x=x.right。
如果 x 有左孩子，则找到 x 左子树上最右的节点（即左子树中序遍历的最后一个节点，x 在中序遍历中的前驱节点），我们记为 predecessor。根据 predecessor 的右孩子是否为空，进行如下操作。
如果 predecessor 的右孩子为空，则将其右孩子指向 x，然后访问 x 的左孩子，即 x=x.left。
如果 predecessor 的右孩子不为空，则此时其右孩子指向 x，说明我们已经遍历完 x 的左子树，我们将 predecessor 的右孩子置空，将 x 的值加入答案数组，然后访问 x 的右孩子，即 x=x.right。
重复上述操作，直至访问完整棵树。

其实整个过程我们就多做一步：假设当前遍历到的节点为 x，将 x 的左子树中最右边的节点的右孩子指向 x，这样在左子树遍历完成后我们通过这个指向走回了 x，且能通过这个指向知晓我们已经遍历完成了左子树，而不用再通过栈来维护，省去了栈的空间复杂度。

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
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode *predecessor = nullptr;

        while (root != nullptr) {
            if (root->left != nullptr) {
                // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                predecessor = root->left;
                while (predecessor->right != nullptr && predecessor->right != root) {
                    predecessor = predecessor->right;
                }
                
                // 让 predecessor 的右指针指向 root，继续遍历左子树
                if (predecessor->right == nullptr) {
                    predecessor->right = root;
                    root = root->left;
                }
                // 说明左子树已经访问完了，我们需要断开链接
                else {
                    res.push_back(root->val);
                    predecessor->right = nullptr;
                    root = root->right;
                }
            }
            // 如果没有左孩子，则直接访问右孩子
            else {
                res.push_back(root->val);
                root = root->right;
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度：O(n)，其中 n 为二叉树的节点个数。Morris 遍历中每个节点会被访问两次，因此总时间复杂度为 O(2n)=O(n)。

空间复杂度：O(1)。