#include <iostream>
#include <queue>
#include <stack>
using namespace std;
struct Node {
int val;
Node *lch, *rch;
Node(int x):val(x), lch(NULL), rch(NULL) {}
};
方法一:
前序遍历就是先访问当前节点,然后依次访问左子结点,右子节点
所以很简单,我们就直接用一个栈先压入右子节点,然后压入左子结点就可以了
*/
void preOrderTraversal(Node *root) {
stack<Node *> s;
Node *cur;
if (root != NULL)
s.push(root);
while (!s.empty()) {
cur = s.top();
s.pop();
cout<<cur->val;
if (cur->rch != NULL)
s.push(cur->rch);
if (cur->lch != NULL)
s.push(cur->lch);
}
}
方法二
*/
void preOrderTraversal1(Node *root) {
if (root == NULL) return;
Node *cur = root;
stack<Node *> st;
while (!st.empty() || cur) {
while (cur) {
cout<<cur->val;
st.push(cur);
cur = cur->lch;
}
cur = st.top();
st.pop();
cur = cur->rch;
}
}
中序遍历不能像后序遍历一样记录前一个访问的节点,因为前一个访问的节点并不是要访问的节点的
直接子节点,所以又得换种方法:
我们用一个节点记录当前访问的节点,然后用一个栈记录上一个访问过的节点。如果当前的节点不为空,
那么向下访问左子结点。
如果当前访问的节点为空,说明上一个访问的节点已经没有左子结点了,那么输出上一个节点,
然后访问上一个节点的右子节点。
*/
void inorderTraversal(Node *root) {
stack<Node *> s;
Node *cur = root;
while (!s.empty() || cur != NULL) {
if (cur != NULL) {
s.push(cur);
cur = cur->lch;
} else {
cur = s.top();
s.pop();
cout<<cur->val;
cur = cur->rch;
}
}
}
方法二
*/
void inOrderTraversal1(Node *root) {
if (root == NULL) return ;
Node *cur = root;
stack<Node *> st;
while (!st.empty() || cur) {
while (cur) {
st.push(cur);
cur = cur->lch;
}
cur = st.top();
cout<<cur->val;
cur = cur->rch;
}
}
后序遍历就是先访问节点的左子结点和右子节点,再访问当前节点
如果不用递归,我们就可以用栈,我们可以依次将当前节点、右子节点和左子结点入栈,
然后再弹栈
但是这里又有另一个问题,如果我们访问到了一个节点,可是我们不知道到底是应该将它的两个子节点
压栈还是该将它弹出。因此就需要一个辅助的节点来记录上一个弹出的节点,如果被弹出的上一个节点
是它的一个子节点,那么说明前面已经将该节点的子节点压栈了,现在该将它弹出。问题就解决了。
*/
void postorderTraversal(Node *root) {
stack<Node *> s;
Node *pre = NULL;
Node *cur = NULL;
if (root != NULL)
s.push(root);
while (!s.empty()) {
cur = s.top();
if ((cur->lch == NULL && cur->rch == NULL) ||
(pre != NULL && (cur->lch == pre || cur->rch == pre))) {
cout<<cur->val;
s.pop();
pre = cur;
} else {
if (cur->rch != NULL)
s.push(cur->rch);
if (cur->lch != NULL)
s.push(cur->lch);
}
}
}
方法二
后序遍历和中序遍历和前序遍历不同,需要保存上一个访问过的节点,
然后根据这个节点来决定是否访问当前点
思路就是使用两个指针,一个用来遍历,另一个用来保存前一个访问的节点
遍历的节点先往左走到头,然后根据当前节点是否有右子节点或者右子节点是否访问过来判断是否要访问当前节点。
否则访问右子节点
*/
void postOrderTraversal1(Node *root) {
if (root == NULL) return ;
Node *cur = root, *pre = NULL;
stack<Node *> st;
while (!st.empty() && cur) {
while (cur) {
st.push(cur);
cur = cur->lch;
}
cur = st.top();
if (cur->rch == NULL || cur->rch == pre) {
cout<<cur->val;
pre = cur;
cur = NULL;
} else {
cur = cur->rch;
}
}
}
void levelorderTraversal(Node *root) {
queue<Node *> que;
Node *cur;
if (root != NULL)
que.push(root);
while (!que.empty()) {
cur = que.front();
cout<<cur->val;
que.pop();
if (cur->lch != NULL)
que.push(cur->lch);
if (cur->rch != NULL)
que.push(cur->rch);
}
}
int main() {
Node root(1);
Node c1(2);
Node c2(3);
Node c3(4);
Node c4(5);
Node c5(6);
root.lch = &c1;
root.rch = &c2;
c1.lch = &c3;
c1.rch = &c4;
c2.lch = &c5;
preOrderTraversal(&root);
cout<<endl;
preOrderTraversal1(&root);
postorderTraversal(&root);
inorderTraversal(&root);
levelorderTraversal(&root);
}