一、引言
用递归方式实现二叉树先序、中序和后序遍历很简单。 用递归方法解决的问题都能用非递归的方法实现。递归就是利用函数栈来保存信息,如果用自己申请的数据结构来代替函数栈,也可以实现相同的功能。
二、用非递归的方式实现二叉树的先序遍历
1、申请一个栈stack,然后将头节点压入stack中。
2、从stack中弹出栈顶节点,打印,再将其右孩子节点(不为空的话)先压入stack中,最后将其左孩子节点(不为空的话)压入stack中。
3、不断重复步骤2,直到stack为空,全部过程结束。
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
/**
* 定义树节点
* struct TreeNode {
* int data;
* TreeNode* left;
* TreeNode* right;
* };
*/
void prev_iterate(TreeNode* root) {
stack<TreeNode*> st; //申请栈存放树节点的指针
if (root != NULL) {
st.push(root);
while (!st.empty()) {
TreeNode* now = st.top();
st.pop();
printf("%d ", now->data); //打印树节点的数据,也可以用个数组把它存下来
if (now->right != NULL) {
st.push(now->right);
}
if (now->left != NULL) {
st.push(now->left);
}
}
}
}
三、用非递归的方式实现二叉树的先序遍历
1、申请一个栈stack,初始时令cur=root
2、先把cur压入栈中,依次把左边界压入栈中,即不停的令cur=cur->left,重复步骤2
3、不断重复2,直到为null,从stack中弹出一个节点,记为node,打印node的值,并令cur=node->right,重复步骤2
4、当stack为空且cur为空时,整个过程停止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 定义树节点
* struct TreeNode {
* int data;
* TreeNode* left;
* TreeNode* right;
* };
*/
void mid_itertor(TreeNode* root) {
stack<TreeNode*> st; //申请栈存放树节点的指针
TreeNode* cur = root;
while (cur != NULL && !st.empty()) {
while(cur != NULL) {
st.push(cur);
cur = cur->left;
}
if (!st.empty()){
cur = st.top();
st.pop();
printf("%d ", cur->data); //打印树节点的数据,也可以用个数组把它存下来
cur = cur->right;
}
}
}
四、用非递归的方式实现二叉树的先序遍历
用非递归的方式实现后序遍历有点麻烦。
1、申请一个栈s1,然后将头节点压入栈s1中。
2、从s1中弹出的节点记为cur,然后依次将cur的左孩子节点和右孩子节点压入s1中。
3、在整个过程中,每一个从s1中弹出的节点都放进s2中。
4、不断重复步骤2和步骤3,直到s1为空,过程停止。
5、从s2中依次弹出节点并打印,打印的顺序就是后序遍历的顺序。
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
/**
* 定义树节点
* struct TreeNode {
* int data;
* TreeNode* left;
* TreeNode* right;
* };
*/
void next_itertor(TreeNode* root) {
stack<TreeNode*> s1, s2;
TreeNode* cur = root;
if (root != NULL) {
s1.push(cur);
while (!s1.empty()) {
cur = s1.top();
s1.pop();
s2.push(cur);
if (cur->left != NULL) {
s1.push(cur->left);
}
if (cur->right != NULL) {
s1.push(cur->right);
}
}
}
while (!s2.empty()) {
printf("%d ", s2.top()->data);
s2.pop();
}
putchar(10);
}
五、用非递归的方式实现二叉树的先序遍历
从二叉树的第一层(根节点)开始,从上至下逐层遍历,在每一层中又按照从左到右的顺序对结点逐个遍历。我们可以看出如果某个结点比同一层的先遍历,其孩子也将比其同层的孩子结点先遍历,这种先进先出的方式,不就是队列这种数据结构吗?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 定义树节点
* struct TreeNode {
* int data;
* TreeNode* left;
* TreeNode* right;
* };
*/
void level_iterate(TreeNode* root){
queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {
TreeNode* cur = que.front();
que.pop();
printf("%d ", cur->data);
if (cur->left != NULL) {
que.push(cur->left);
}
if (cur->right != NULL) {
que.push(cur->right);
}
}
}