前、中、后序遍历是对树进行的基础操作,当使用递归来实现时代码非常简单。但是由于递归时会不断将当前状态保存下来,因此空间复杂度较高。下面就介绍一下用非递归的方式如何来实现这些操作。
二叉树的数据结构定义如下:
1 2 3 4 5 6 7 |
struct TreeNode { TreeNode *left; TreeNode *right; int val; TreeNode(int x): val(x), left(NULL),right(NULL) {} } |
- 前序遍历:非递归遍历通过栈来实现,并且有两种不同的实现方式。思路一是先将根节点压入栈,然后当栈不为空的时候,先将栈顶元素出栈并访问这个节点,然后依次将该节点的右孩子和左孩子入栈。代码如下:
12345678910111213141516171819void preOrder(TreeNode *root) {if(root == NULL) {return;}stack<struct TreeNode *> s;s.push(root);while(! s.empty()) {TreeNode *node = s.top();s.pop();cout << node->val << endl;if (node->right) {s.push(node->right);}if (node->left) {s.push(node->left);}}}
思路二则是使用回溯,先遍历完左子树,然后回溯遍历右子树。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
void preOrder_(TreeNode *root) { if (root == NULL) { return; } stack<TreeNode *> s; TreeNode *ptr = root; while(ptr != NULL || ! s.empty()) { if(ptr != NULL) { // 访问当前节点 cout << ptr->val << endl; s.push(ptr); ptr = ptr->left; } else { // 当 ptr 为空的时候,说明刚刚入栈的那个节点的左子树已经遍历完了 // 因此应该把它弹出来然后遍历它的右子树了 ptr = s.top(); s.pop(); ptr = ptr->right; } } } |
- 中序遍历:和前序遍历的实现非常类似,只不过访问节点的时机不同。
12345678910111213141516171819void inOrder(TreeNode *root) {if (root == NULL) {return;}stack<TreeNode *> s;TreeNode *ptr = root;while(ptr != NULL || ! s.empty()) {if (ptr != NULL) {s.push(ptr);ptr = ptr->left;} else {ptr = s.top();s.pop();cout << ptr->val << endl;ptr = ptr->right;}}} - 后序遍历:后序遍历是这几种遍历方式中比较麻烦的一种。前面的算法的规律是,当一个节点的左子树已经访问完了后,会将当前节点从栈中直接弹出并访问这个节点,然后再遍历它的右子树。但是后序遍历时,当访问完一个节点的左子树后,先得从栈顶获得这个节点,得到它的右子树并访问右子树,当右子树访问之后,再从栈顶获得这个节点,然后去访问这个节点自身,然后将该节点出栈。可以看出,访问该节点的过程发生了两次,但是只有访问了它的右子树后才可以将这个节点从栈中弹出。因此我们需要标记该节点是否被访问过。代码如下:
12345678910111213141516171819202122232425262728void postOrder(TreeNode *root) {if (root == NULL) {return;}stack<TreeNode *> s;TreeNode *p,*q;p = root;do {while (p) {s.push(p);p = p->left;}q = NULL;while (! s.empty()) {p = s.top();s.pop();if (p->right == q) {cout << p->val << endl;q = p;} else {s.push(p);p = p->right;break;}}} while (! s.empty());} - 层序遍历:作为树的遍历方式的一种,虽然不如前面三种方式常见,但是也是非常有必要了解的。与前面三种方式不同的是,层序遍历使用了队列而不是栈这种结构。思路是:先将根节点入队,当队列不为空的时候,从队列头出队一个元素并访问它,然后将它的左右孩子依次入队。
12345678910111213141516171819void levelOrder(TreeNode *root) {if (root == NULL) {return NULL;}queue<TreeNode *> que;que.push(root);while (! que.empty()) {TreeNode *node = que.front();que.pop();cout << node->val << endl;if (node->left) {que.push(node->left);}if (node->right) {que.push(node->right);}}}