参考别人的代码,然后加入一点自己的理解吧,算法最主要的是理解,拷贝代码没用。先根序
- /*===========================================================================
* Function name: BT_PreOrder
* Parameter: root:树根节点指针
* Precondition: None
* Description: 前序遍历
* Return value: void
* Author: Liu Qi, [12/29/2005]
==================================================================== - void BT_PreOrder(pTreeT root)
-
{
-
if (NULL != root)
-
{
-
visit(root);
-
BT_PreOrder(root->left);
-
BT_PreOrder(root->right);
-
}
-
}
- //还是递归简单
- //但是我很讨厌递归这种算法,一方面是因为对于stack的消耗,另外一点就是递归容易将脑子搞糊涂
- /*===========================================================================
-
* Function name: BT_PreOrderNoRec
-
* Parameter: root:树根节点指针
-
* Precondition: Node
-
* Description: 前序(先根)遍历非递归算法
-
* Return value: void
-
* Author: Liu Qi, [1/1/2006]
-
===========================================================================*/
-
void BT_PreOrderNoRec(pTreeT root)
-
{
-
stack<treeT *> s;
-
-
while ((NULL != root) || !s.empty())
-
{
-
if (NULL != root)
-
{
-
visit(root);
-
s.push(root);
-
root = root->left;
-
}
-
else
-
{
-
root = s.top();
-
s.pop();
-
root = root->right;
- //原来理解错误了,以为这儿应该改为root = s.top()->right.
- //发现非递归遍历二叉树都是采用了kunth的借助辅助栈的方法
- //所谓先根序即先访问左节点,再访问根节点,最后是右节点,这儿的根借用“树”的递归概念,并不是指二叉树树的根
- //而是一个只有父节点,左右节点的节点(当然左右节点可以为空)如下图所示,所谓的二叉树就是由这样的子树组成的。
- //由于是先根序,那么一个stack中每一个节点必然已经被访问过了,但是这些节点的右子树没有被访问
-
}
-
}
-
}
中根序
- /*===========================================================================
-
* Function name: BT_InOrder
-
* Parameter: root:树根节点指针
-
* Precondition: None
-
* Description: 中序遍历
-
* Return value: void
-
* Author: Liu Qi, [12/30/2005]
-
===========================================================================*/
-
void BT_InOrder(pTreeT root)
-
{
-
if (NULL != root)
-
{
-
BT_InOrder(root->left);
-
visit(root);
-
BT_InOrder(root->right);
-
}
-
}
- void BT_InOrderNoRec(pTreeT root)
-
{
-
stack<treeT *> s;
-
while ((NULL != root) || !s.empty())
-
{
-
if (NULL != root)
-
{
-
s.push(root);
-
root = root->left;//一路压栈到底
-
}
-
else
-
{
-
root = s.top();//在退栈的时候访问,
-
visit(root);
-
s.pop();
-
root = root->right;
-
}
-
}
-
}
InOrderTraverse(BiTree T)
{
InitStack(S);Push(S,T);
while(!StackEmpty(S)){
While(GetTop(S,p) && p)
Push(S,p->left);//向左走到尽头,然后开始退栈
Pop(S,p);//将最后一个空指针退栈
if(!StackEmpty(S)){
Pop(S,p);
Visit(p);
Push(S,p->right);//将右节点压栈,然后准备再一次向左走到尽头。
}
}
对于中根序,栈中的每一个节点必然是没有被访问过的,都是等待到退栈的时候访问的。
但是如果仔细的话会发现,访问的第一个节点必然是从二叉树的根一路向左访问的最后一个节点。那么有人就会疑惑,为什么访问的是一个左节点,却叫中根序呢?其实从上图任然可以看出,这个左节点的两个孩子都是空指针,所以它任然是一个根。
阅读(1220) | 评论(0) | 转发(0) |