初学树Ⅱ-二叉树非递归遍历

栈的应用——二叉树的非递归遍历

递归遍历实现起来比较简单,但是后序遍历无法实现。

结合可以实现二叉树的非递归遍历。

PreOrderTraverse

对于每一个深度为2的二叉树,先把根节点入栈,之后等根节点出栈之后,将右孩子跟左孩子依次入栈。

再pop左孩子,同时左孩子作为另一颗深度为2的子树的根节点,将右孩子和左孩子依次入栈,重复上述过程直到栈空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void PreOrderTraverse(node *T)
{
if(!T) return;
stack<node*> s;
s.push(T);
while(!s.empty())
{
node *t = s.top();
cout<<t->data;
s.pop();
if(t->rchild)
s.push(t->rchild);
if(t->lchild)
s.push(t->lchild);
}
return;
}

InOrderTraverse

一直沿着左边走,将每一个节点入栈,直到叶子也入栈。

然后pop栈顶节点,pop完之后检查是否还有右孩子。

有的话,重复刚刚的操作。

重复上述操作直到栈空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void InOrderTraverse(node *T)
{
if(!T) return;
stack<node*> s;
s.push(T);
node *t = T->lchild;
while(t!=NULL||!s.empty())
{
while(t!=NULL) //一直向左走
{
s.push(t);
t = t->lchild;
}
t = s.top();
s.pop();
cout<<t->data;
t = t->rchild;
}
}

PostOrderTraverse

后序遍历相对来说麻烦一点,这里用的双栈实现。

可以这么理解:

对于下面这样一个二叉树:

1
2
3
A
/ \
B C

后序遍历是BCA;前序遍历是ABC

那么入栈顺序就应该是ACB

刚好是个左右反转的前序遍历,那就很棒棒了对不对。

前序遍历的入栈顺序是 根节点->右孩子->左孩子

那么这里反过来变成 左孩子->右孩子 就OK了

所以第一个栈就是用来解决左右镜像的前序遍历

然后第二个栈就是用来存储镜像前序遍历的结果

最后pop第二个栈直到其为空就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void PostOrderTraverse(node *T)
{
stack<node*> s1,s2;
node *t;
s1.push(T);
while(!s1.empty())
{
t = s1.top();
s1.pop();
s2.push(t);
if(t->lchild)
s1.push(t->lchild);
if(t->rchild)
s1.push(t->rchild);
}
while(!s2.empty())
{
cout<<s2.top()->data;
s2.pop();
}
}

主函数

1
2
3
4
5
6
7
8
int main(void)
{
node *Tree;
Tree = CreateBiTree();
PostOrderTraverse(Tree);
printf("\n");
return 0;
}