二叉树的遍历(递归,迭代,Morris遍历)
二叉树的遍历:
先序,中序,后序;
二叉树的遍历有三种常见的方法,
最简单的实现就是递归调用,
另外就是飞递归的迭代调用,
最后还有O(1)空间的morris遍历;
二叉树的结构定义:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
1.先序遍历:
递归:
void preOrderRecursive(TreeNode *root) {
if (!root)
return;
cout << root->val << " ";
preOrderRecursive(root->left);
preOrderRecursive(root->right);
}
迭代:
迭代要用到栈来保存父亲结点,
先序遍历,所有访问过的结点都先输出,
先遍历当前结点和当前结点的左子树,一直到左子树的最左边的结点,
遍历过的这些结点都入栈,左孩子为空时,栈顶元素设为当前结点,出栈,
然后把当前结点设为该节点的右孩子,循环一直到当前结点为空且栈也为空。
void preOrderIterative(TreeNode *root) {
if (!root)
return;
stack<TreeNode*> stk;
TreeNode *cur = root;
while (cur || !stk.empty()) {
while (cur) {
cout << cur->val << " ";
stk.push(cur);
cur = cur->left;
}
if (!stk.empty()) {
cur = stk.top();
stk.pop();
cur = cur->right;
}
}
}
/*
* 模拟递归
* */
void preOrderIterative1(TreeNode *root) {
if (!root)
return;
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode* tp = stk.top();
stk.pop();
cout << tp->val << " ";
if (tp->right)
stk.push(tp->right);
if (tp->left)
stk.push(tp->left);
}
}
Morris方法:
1.当前结点的左孩子为空,输出当前结点,并设置当前结点的右孩子为当前结点;
2.当前结点的左孩子不为空:
a.找到当前结点中序遍历的前驱结点,即为该节点的左孩子的最右边的结点,前驱结点的右孩子为空,则设置前驱结点的右孩子为当前结点,并输出当前结点,设当前结点的左孩子为当前结点;
b.前驱结点的右孩子为当前结点,则恢复前驱结点的右孩子为NULL,设当前结点的右孩子为当前结点;
void preOrderMorris(TreeNode *root) {
if (!root)
return;
TreeNode* cur = root;
TreeNode* pre = NULL;
while (cur) {
if (cur->left == NULL) {
cout << cur->val << " ";
cur = cur->right;
}
else {
pre = cur->left;
while (pre->right != NULL && pre->right != cur)
pre = pre->right;
if (pre->right == NULL) {
cout << cur->val << " ";
pre->right = cur;
cur = cur->left;
}
else {
pre->right = NULL;
cur = cur->right;
}
}
}
}
2.中序遍历:
递归:
void inOrderRecursive(TreeNode *root) {
if (!root)
return;
inOrderRecursive(root->left);
cout << root->val << " ";
inOrderRecursive(root->right);
}
迭代:
1.如果当前结点的左孩子不为空,则把当前结点的左孩子入栈,知道当前结点的左孩子为空;
2.如果栈不为空,则出栈,栈顶元素为当前结点,输出当前结点,并把当前结点的右孩子设为当前结点;
重复1,2直到当前结点为NULL且栈也为空;
void inOrderIterative(TreeNode *root) {
if (!root)
return;
stack<TreeNode*> stk;
TreeNode *cur = root;
while (cur || !stk.empty()) {
while (cur) {
stk.push(cur);
cur = cur->left;
}
if (!stk.empty()) {
cur = stk.top();
stk.pop();
cout << cur->val << " ";
cur = cur->right;
}
}
}
Morris方法:
和先序遍历的过程类似,只不过输出结点的位置不一样,中序遍历是在2.b中,也就是前驱结点的右孩子为当前结点时,即当前结点的左子树都已经遍历完成时,输出当前结点;
void inOrderMorris(TreeNode *root) {
if (!root)
return;
TreeNode* cur = root;
TreeNode* pre = NULL;
while (cur) {
if (cur->left == NULL) {
cout << cur->val << " ";
cur = cur->right;
}
else {
pre = cur->left;
while (pre->right != NULL && pre->right != cur)
pre = pre->right;
if (pre->right == NULL) {
pre->right = cur;
cur = cur->left;
}
else {
cout << cur->val << " ";
pre->right = NULL;
cur = cur->right;
}
}
}
}
3.后序遍历:
递归:
void postOrderRecursive(TreeNode *root) {
if (!root)
return;
postOrderRecursive(root->left);
postOrderRecursive(root->right);
cout << root->val << " ";
}
迭代:
后序遍历比先序、中序都要复杂,
第一种迭代方法,可以用两个栈来模拟递归的遍历;
栈1初始化时把根节点入栈,
1.栈1出栈,把出栈的元素加入栈2,然后把该元素的左孩子(如果不为空),右孩子(如果不为空)加入栈1,知道栈1为空;
2.栈2出栈直到空,每次出栈时输出栈顶元素;
通过两个栈,保证了栈2中的元素顺序,
第二种迭代方法,
用一个结点保存访问过的最后一个结点pre,如果pre为栈顶元素的右孩子,则说明栈顶元素的右子树已经遍历过了,直接输出栈顶元素,并把当前结点设为NULL,并更新pre为出栈的元素;
1.如果当前结点存在,则一直向左遍历,入栈遍历的元素,直到结点为空;
2.栈不为空时,出栈,当前结点为栈顶元素,
如果当前结点的右孩子不为空且不为pre,说明当前结点的右子树没有遍历过,设置当前结点为该节点的右孩子,
如果右孩子为空或者为pre,直接输出当前结点,更新pre为当前结点,并设当前结点为NULL,
重复1,2直到当前结点为NULL并且栈为空;
void postOrderIterative(TreeNode *root) {
if (!root)
return;
stack<TreeNode*> stk;
TreeNode *cur = root;
TreeNode *pre = NULL;
while (cur || !stk.empty()) {
while (cur) {
stk.push(cur);
cur = cur->left;
}
if (!stk.empty()) {
cur = stk.top();
if (cur->right != NULL && cur->right != pre) {
cur = cur->right;
}
else {
cout << cur->val << " ";
pre = cur;
stk.pop();
cur = NULL;
}
}
}
}
/*
* 双栈法
*/
void postOrderIterative1(TreeNode *root) {
if (!root)
return;
stack<TreeNode*> stk1, stk2;
TreeNode *cur;
stk1.push(root);
while (!stk1.empty()) {
cur = stk1.top();
stk1.pop();
stk2.push(cur);
if (cur->left)
stk1.push(cur->left);
if (cur->right)
stk1.push(cur->right);
}
while (!stk2.empty()) {
cout << stk2.top()->val << " ";
stk2.pop();
}
}
Morris方法:
morris方法的后序遍历较为复杂,因为需要逆序输出右孩子到父亲结点;
遍历过程与先序与中序类似,
当前驱结点的右孩子为当前结点时,左子树已经遍历完成,逆序输出当前结点的左孩子到前驱结点;
类似于链表的反转,不过反转输出之后,记得要反转回来。
void reverse(TreeNode *begin, TreeNode *end) {
if (begin == end)
return;
TreeNode *pre = begin;
TreeNode *cur = begin->right;
TreeNode *next;
while (pre != end) {
temp = cur->right;
cur->right = pre;
pre = cur;
cur = temp;
}
} void traversalReversal(TreeNode *begin, TreeNode *end) {
reverse(begin, end);
TreeNode *it = end;
while (true) {
cout << it->val << " ";
if (it == begin)
break;
it = it->right;
}
reverse(end, begin);
} void postOrderMorris(TreeNode *root) {
if (!root)
return;
TreeNode dump();
dump.left = root;
TreeNode *cur = &dump;
TreeNode *pre = NULL;
while (cur) {
if (cur->left == NULL) {
cur = cur->right;
}
else {
pre = cur->left;
while (pre->right != NULL && pre->right != cur)
pre = pre->right;
if (pre->right == NULL) {
pre->right = cur;
cur = cur->left;
}
else {
traversalReverse(cur->left, pre);
pre->right = NULL;
cur = cur->right;
}
}
}
}
参考:
http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html
http://blog.csdn.net/hackbuteer1/article/details/6583988
最新文章
- JQuery中$.ajax()方法参数都有哪些?
- delphi的webBrowser操作HTML研究
- min-height在安卓下不起作用
- 周赛-Toy Cars 分类: 比赛 2015-08-08 15:41 5人阅读 评论(0) 收藏
- STL源码分析-AVL树-RB树
- 【IHttpHandler】IHttpModule实现URL重写
- efficient c++,单线程内存池
- unity3d 下操作excel 与打印
- COJ 0802 非传统题(二)
- 安卓图表引擎AChartEngine(二) - 示例源码概述和分析
- wireshark使用方法
- 深入Redis持久化
- React Native——react-navigation的使用
- SQLite保存报错sqlite.SQLiteConstraintException: UNIQUE constraint failed: &#183;&#183;&#183;&#183;&#183;&#183; code 1555
- 软工网络15团队作业4——Alpha阶段敏捷冲刺3.0
- #pragma pack(n)的使用
- C++中的new、operator new与placement new
- Redis need tcl 8.5 or newer
- jquery load ($.load) 事件用法与分析(转)
- Linux进阶路线