二叉树的遍历(递归,迭代,Morris遍历)

二叉树的遍历:

先序,中序,后序;

二叉树的遍历有三种常见的方法,

最简单的实现就是递归调用,

另外就是飞递归的迭代调用,

最后还有O(1)空间的morris遍历;

二叉树的结构定义:

1 struct TreeNode {
2 int val;
3 TreeNode *left;
4 TreeNode *right;
5 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
6 };

1.先序遍历:

递归:

复制代码
1 void preOrderRecursive(TreeNode *root) {
2 if (!root)
3 return;
4 cout << root->val << ” “;
5 preOrderRecursive(root->left);
6 preOrderRecursive(root->right);
7 }
复制代码
迭代:

迭代要用到栈来保存父亲结点,

先序遍历,所有访问过的结点都先输出,

先遍历当前结点和当前结点的左子树,一直到左子树的最左边的结点,

遍历过的这些结点都入栈,左孩子为空时,栈顶元素设为当前结点,出栈,

然后把当前结点设为该节点的右孩子,循环一直到当前结点为空且栈也为空。

复制代码
1 void preOrderIterative(TreeNode *root) {
2 if (!root)
3 return;
4 stack<TreeNode*> stk;
5 TreeNode *cur = root;
6 while (cur || !stk.empty()) {
7 while (cur) {
8 cout << cur->val << ” “;
9 stk.push(cur);
10 cur = cur->left;
11 }
12 if (!stk.empty()) {
13 cur = stk.top();
14 stk.pop();
15 cur = cur->right;
16 }
17 }
18 }
19 /*
20 * 模拟递归
21 * */
22 void preOrderIterative1(TreeNode *root) {
23 if (!root)
24 return;
25 stack<TreeNode*> stk;
26 stk.push(root);
27 while (!stk.empty()) {
28 TreeNode* tp = stk.top();
29 stk.pop();
30 cout << tp->val << ” “;
31 if (tp->right)
32 stk.push(tp->right);
33 if (tp->left)
34 stk.push(tp->left);
35 }
36 }
复制代码

Morris方法:

1.当前结点的左孩子为空,输出当前结点,并设置当前结点的右孩子为当前结点;

2.当前结点的左孩子不为空:

a.找到当前结点中序遍历的前驱结点,即为该节点的左孩子的最右边的结点,前驱结点的右孩子为空,则设置前驱结点的右孩子为当前结点,并输出当前结点,设当前结点的左孩子为当前结点;

b.前驱结点的右孩子为当前结点,则恢复前驱结点的右孩子为NULL,设当前结点的右孩子为当前结点;

复制代码
1 void preOrderMorris(TreeNode *root) {
2 if (!root)
3 return;
4 TreeNode* cur = root;
5 TreeNode* pre = NULL;
6 while (cur) {
7 if (cur->left == NULL) {
8 cout << cur->val << ” “;
9 cur = cur->right;
10 }
11 else {
12 pre = cur->left;
13 while (pre->right != NULL && pre->right != cur)
14 pre = pre->right;
15 if (pre->right == NULL) {
16 cout << cur->val << ” “;
17 pre->right = cur;
18 cur = cur->left;
19 }
20 else {
21 pre->right = NULL;
22 cur = cur->right;
23 }
24 }
25 }
26 }
复制代码

2.中序遍历:

递归:

复制代码
1 void inOrderRecursive(TreeNode *root) {
2 if (!root)
3 return;
4 inOrderRecursive(root->left);
5 cout << root->val << ” “;
6 inOrderRecursive(root->right);
7 }
复制代码
迭代:

1.如果当前结点的左孩子不为空,则把当前结点的左孩子入栈,知道当前结点的左孩子为空;

2.如果栈不为空,则出栈,栈顶元素为当前结点,输出当前结点,并把当前结点的右孩子设为当前结点;

重复1,2直到当前结点为NULL且栈也为空;

复制代码
1 void inOrderIterative(TreeNode *root) {
2 if (!root)
3 return;
4 stack<TreeNode*> stk;
5 TreeNode *cur = root;
6 while (cur || !stk.empty()) {
7 while (cur) {
8 stk.push(cur);
9 cur = cur->left;
10 }
11 if (!stk.empty()) {
12 cur = stk.top();
13 stk.pop();
14 cout << cur->val << ” “;
15 cur = cur->right;
16 }
17 }
18 }
复制代码

Morris方法:

和先序遍历的过程类似,只不过输出结点的位置不一样,中序遍历是在2.b中,也就是前驱结点的右孩子为当前结点时,即当前结点的左子树都已经遍历完成时,输出当前结点;

复制代码
1 void inOrderMorris(TreeNode *root) {
2 if (!root)
3 return;
4 TreeNode* cur = root;
5 TreeNode* pre = NULL;
6 while (cur) {
7 if (cur->left == NULL) {
8 cout << cur->val << ” “;
9 cur = cur->right;
10 }
11 else {
12 pre = cur->left;
13 while (pre->right != NULL && pre->right != cur)
14 pre = pre->right;
15 if (pre->right == NULL) {
16 pre->right = cur;
17 cur = cur->left;
18 }
19 else {
20 cout << cur->val << ” “;
21 pre->right = NULL;
22 cur = cur->right;
23 }
24 }
25 }
26 }
复制代码

3.后序遍历:

递归:

复制代码
1 void postOrderRecursive(TreeNode *root) {
2 if (!root)
3 return;
4 postOrderRecursive(root->left);
5 postOrderRecursive(root->right);
6 cout << root->val << ” “;
7 }
复制代码
迭代:

后序遍历比先序、中序都要复杂,

第一种迭代方法,可以用两个栈来模拟递归的遍历;

栈1初始化时把根节点入栈,

1.栈1出栈,把出栈的元素加入栈2,然后把该元素的左孩子(如果不为空),右孩子(如果不为空)加入栈1,知道栈1为空;

2.栈2出栈直到空,每次出栈时输出栈顶元素;

通过两个栈,保证了栈2中的元素顺序,

第二种迭代方法,

用一个结点保存访问过的最后一个结点pre,如果pre为栈顶元素的右孩子,则说明栈顶元素的右子树已经遍历过了,直接输出栈顶元素,并把当前结点设为NULL,并更新pre为出栈的元素;

1.如果当前结点存在,则一直向左遍历,入栈遍历的元素,直到结点为空;

2.栈不为空时,出栈,当前结点为栈顶元素,

如果当前结点的右孩子不为空且不为pre,说明当前结点的右子树没有遍历过,设置当前结点为该节点的右孩子,

如果右孩子为空或者为pre,直接输出当前结点,更新pre为当前结点,并设当前结点为NULL,

重复1,2直到当前结点为NULL并且栈为空;

复制代码
1 void postOrderIterative(TreeNode *root) {
2 if (!root)
3 return;
4 stack<TreeNode*> stk;
5 TreeNode *cur = root;
6 TreeNode *pre = NULL;
7 while (cur || !stk.empty()) {
8 while (cur) {
9 stk.push(cur);
10 cur = cur->left;
11 }
12 if (!stk.empty()) {
13 cur = stk.top();
14 if (cur->right != NULL && cur->right != pre) {
15 cur = cur->right;
16 }
17 else {
18 cout << cur->val << ” “;
19 pre = cur;
20 stk.pop();
21 cur = NULL;
22 }
23 }
24 }
25 }
26 /*
27 * 双栈法
28 */
29 void postOrderIterative1(TreeNode *root) {
30 if (!root)
31 return;
32 stack<TreeNode*> stk1, stk2;
33 TreeNode *cur;
34 stk1.push(root);
35 while (!stk1.empty()) {
36 cur = stk1.top();
37 stk1.pop();
38 stk2.push(cur);
39 if (cur->left)
40 stk1.push(cur->left);
41 if (cur->right)
42 stk1.push(cur->right);
43 }
44 while (!stk2.empty()) {
45 cout << stk2.top()->val << ” “;
46 stk2.pop();
47 }
48 }
复制代码

Morris方法:

morris方法的后序遍历较为复杂,因为需要逆序输出右孩子到父亲结点;

遍历过程与先序与中序类似,

当前驱结点的右孩子为当前结点时,左子树已经遍历完成,逆序输出当前结点的左孩子到前驱结点;

类似于链表的反转,不过反转输出之后,记得要反转回来。

复制代码
1 void reverse(TreeNode *begin, TreeNode *end) {
2 if (begin == end)
3 return;
4 TreeNode *pre = begin;
5 TreeNode *cur = begin->right;
6 TreeNode *next;
7 while (pre != end) {
8 temp = cur->right;
9 cur->right = pre;
10 pre = cur;
11 cur = temp;
12 }
13 }
14
15 void traversalReversal(TreeNode *begin, TreeNode *end) {
16 reverse(begin, end);
17 TreeNode *it = end;
18 while (true) {
19 cout << it->val << ” “;
20 if (it == begin)
21 break;
22 it = it->right;
23 }
24 reverse(end, begin);
25 }
26
27 void postOrderMorris(TreeNode *root) {
28 if (!root)
29 return;
30 TreeNode dump(0);
31 dump.left = root;
32 TreeNode *cur = &dump;
33 TreeNode *pre = NULL;
34 while (cur) {
35 if (cur->left == NULL) {
36 cur = cur->right;
37 }
38 else {
39 pre = cur->left;
40 while (pre->right != NULL && pre->right != cur)
41 pre = pre->right;
42 if (pre->right == NULL) {
43 pre->right = cur;
44 cur = cur->left;
45 }
46 else {
47 traversalReverse(cur->left, pre);
48 pre->right = NULL;
49 cur = cur->right;
50 }
51 }
52 }
53 }
复制代码

标签