二叉树的遍历方式有前序遍历，中序遍历和后序遍历这三种方式，我们现在就定义一个数据结构树，如下：
struct Tree{
Tree * lchild;
Tree * rchild;
Element data;//数据域
}
为了实现树的非递归遍历，这里我们需要增加一个数据结构站stack,其实，递归的实现是用系统自带的栈来实现的。
对应的前序遍历如下：
void preTraverse(Tree * t){
if(t!=null){
print(t->data);
preTraverse(t->lchild);
preTraverse(t->rchild);
}
}
非递归形式的实现如下：
void preTraverse(Tree* t){
if(t==null)
return ;
Stack s ;
while(t!=null){
s.push(t);
print(t->data);
t= t->lchild;
}
while(!s.empty()){
Tree * temp = s.top()->rchild;
s.pop();
while(temp!=null){
s.push(temp);
print(temp->data);
temp= temp->lchild;
}
;
}
}
中序遍历的递归形式如下：
void inOrderTraverse(Tree * t){
if(t!=null){
inOrderTraverse(t->lchild);
print(t->data);
inOrderTraverse(t->rchild);
}
}
中序遍历对应的非递归形式如下：
void inOrderTraverse(Tree * t){
if(t==null)
return;
Stack s;
s.push(t);
Tree curr = t->lchild;
while(curr!=null || !s.empty()){
while(curr!=null){
s.push(t);
curr = curr->lchild;
}
curr = s.top();
s.pop();
print(cur->data);
curr = curr->rchild;
}
}
后序遍历对应的递归程序如下：
void postOrderTraverse(Tree * t){
if(t!=null){
postOrderTraverse(t->lchild);
postOrderTraverse(t->rchild);
print(t->data);
}
}
后序遍历对应的非递归程序如下：
void postOrder(Tree * t){
if(t == null)
return;
Stack s;
s.push(t);
Tree curr = t-lchild;
while(!s.empty()){
while(curr ! = null){
s.push(curr);
curr = curr - > lchild;
}
curr = s.top();
if(curr->rchild == nulll ||curr->rchild == previsited ){
print(curr->data);
prvisited = curr;
s.pop();
curr = null; //
}else{
curr = curr->right;
}
}
}
阅读(2220) | 评论(0) | 转发(4) |
