struct BiTreeNode
{
int data;
BiTreeNode *leftChild;
BiTreeNode *rightChild;
};
三种遍历是:前序、中序、后序遍历;
每种遍历的实现都有递归和循环2种方法。(注:递归在本质上就是一个栈结构,所以遍历的循环方法可以用栈实现)
前序遍历(递归):
void PreOrder(BiTreeNode *t)
{
if(t != NULL)
{
cout<<t->data<< " " ;
PreOrder(t->leftChild);
PreOrder(t->rightChild);
}
}
前序遍历(循环):
void PreOrderUnrec(BiTreeNode *t)
{
std::stack<BiTreeNode*> s;
BiTreeNode *p=t;
while (p!=NULL || !s.empty())
{
while (p!=NULL) //遍历左子树,存放到栈s中
{
cout<< p->data << " " ;
s.push(p);
p=p->leftChild;
} //endwhile
if (!s.empty()) //通过下一次循环中的内嵌while实现右子树遍历
{
p=s.top();
s.pop();
p=p->rightChild;
} //endif
} //endwhile
} //PreOrderUnrec
中序遍历(递归):
void InOrder(BiTreeNode *t)
{
if(t != NULL)
{
InOrder(t->leftChild);
cout<<t->data<< " " ;
InOrder(t->rightChild);
}
}
中序遍历(循环):
void InOrderUnrec(BiTreeNode *t)
{
std::stack<BiTreeNode*> s;
BiTreeNode *p=t;
while (p!=NULL || !s.empty())
{
while (p!=NULL) //遍历左子树
{
s.push(p);
p=p->leftChild;
} //endwhile
if (!s.empty())
{
p=s.top();
s.pop();
cout<<p->data<< " " ; //访问根结点
p=p->rightChild; //通过下一次循环实现右子树遍历
} //endif
} //endwhile
} //InOrderUnrec
后序遍历(递归):
void PostOrder(BiTreeNode *t)
{
if(t != NULL)
{
PostOrder(t->leftChild);
PostOrder(t->rightChild);
cout<<t->data<< " " ;
}
}
后序遍历(循环):
typedef struct
{
BiTreeNode* ptr;
char tag;
}stacknode;
void PostOrderUnrec(BiTreeNode *t)
{
std::stack<stacknode> s;
stacknode x;
BiTreeNode *p=t;
do
{
while (p!=NULL) //遍历左子树
{
x.ptr = p;
x.tag = 'L' ; //标记为左子树
s.push(x);
p=p->leftChild;
}
while (!s.empty() && s.top().tag== 'R' )
{
x = s.top();
s.pop();
p = x.ptr;
cout<<p->data<< " " ; //tag为R,表示右子树访问完毕,故访问根结点
}
if (!s.empty())
{
s.top().tag ='R'; //遍历右子树
p = s.top().ptr->rightChild;
}
}while (!s.empty());
} //PostOrderUnrec