首先,这里先给出二叉树的节点定义以及递归的二叉树先序遍历:
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; }BiNode; void preorder(BiNode* p) { if(p==NULL) return; cout<<p->data<<" "; preorder(p->lchild); preorder(p->rchild); }
|
下面我们要将先序遍历由递归形式变成非递归形式。按照常理来说,只要模拟递归函数中的隐含的栈操作,就能够把递归变成非递归。所以,二叉树先序遍历的非递归形式应该是这样的:
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<<" "; if(p->rchild!=NULL) s.push(p->rchild); if(p->lchild!=NULL) s.push(p->lchild); } } }
|
这里有一个问题,将输出语句放到两个push()操作之间或者之后,能使二叉树遍历形式变成中序或者后序吗?答案是不能。要注意这里对当前节点的访问和两个子节点的压栈操作是同级别的,而子节点的访问必定在下一次循环中,所以对当前节点的访问必定在子节点之前,所以输出不管放哪儿都是先序遍历。
Read More