关于二叉树非递归遍历

首先,这里先给出二叉树的节点定义以及递归的二叉树先序遍历:

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
//节点定义
typedef class node
{
public:
node()
{
lchild=NULL;
rchild=NULL;
};
char data;
class node *lchild;
class node *rchild;
//bool isFromRight;//非递归后序遍历用
}BiNode;
//递归先序遍历
void preorder(BiNode* p)
{
if(p==NULL)
return;
cout<<p->data<<" ";//先序遍历
preorder(p->lchild);
//cout<<p->data<<" ";//放在这就是中序遍历
preorder(p->rchild);
//cout<<p->data<<" ";//放在这就是后序遍历
}

下面我们要将先序遍历由递归形式变成非递归形式。按照常理来说,只要模拟递归函数中的隐含的栈操作,就能够把递归变成非递归。所以,二叉树先序遍历的非递归形式应该是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//非递归先序遍历
void iterativePreorderClassical(BiNode* p)
{
stack<BiNode*> s;
if(p!=NULL)
{
s.push(p);
while(!s.empty())
{
p=s.top();
s.pop();
cout<<p->data<<" ";//对V节点的访问已经完成
if(p->rchild!=NULL)
s.push(p->rchild);//先将右子节点压入栈
//cout<data<<endl;//放在这并不能实现中序遍历!
if(p->lchild!=NULL)
s.push(p->lchild);//将左子节点压入栈
//cout<data<<endl;//放在这并不能实现后序遍历!
}
}
}

这里有一个问题,将输出语句放到两个push()操作之间或者之后,能使二叉树遍历形式变成中序或者后序吗?答案是不能。要注意这里对当前节点的访问和两个子节点的压栈操作是同级别的,而子节点的访问必定在下一次循环中,所以对当前节点的访问必定在子节点之前,所以输出不管放哪儿都是先序遍历。

Read More