Chinaunix首页 | 论坛 | 博客
  • 博客访问: 283607
  • 博文数量: 118
  • 博客积分: 313
  • 博客等级: 二等列兵
  • 技术积分: 615
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-12 22:51
文章分类

全部博文(118)

文章存档

2012年(68)

2011年(50)

分类:

2012-02-06 22:36:21

原文地址:二叉树的非递归遍历 作者:renjian2011

=================先序遍历===============
先序遍历伪代码1:
void preOrder1(TNode *root)
{
    Stack st;
    while((root != NULL) || !st.empty())
    {
        if(root!=NULL)
        {
            visit(root);  //先访问再入栈
            st.push(root);
            root = root->left;
        }
        else
        {
            root = st.pop();
            root = root->right;
        }
    }
}
先序遍历伪代码2:
void preOrder2(TNode* root)
{
    if(root != NULL)
    {
        Stack st;
        st.push(root);
        while( !st.empty() )
        {
            TNode* node = st.pop();
            visit(node); //先访问根节点,然后根节点就不用入栈了
            st.push(node->right); //先push右节点,然后是左节点
            st.push(node->left); //这样上边先访问到左节点
        }
    }
}
先序遍历不用栈:
void preOrder3(TNode* root)
{
    while(root != NULL)
    {
        if(!root->bVisited)
        {
            visit(root);
            root->bVisited = true;
        }
        if(root->left && !root->left->bVisited)
        {
            root = root->left;
        }
        else if(root->right!=NULL && !root->right->bVisited)
        {
            root = root->right;
        }
        else
        { //回溯
            root = root->parent;
        }
    }
}
=================中序遍历===============
中序遍历伪代码:
void inOrder1(TNode* root)
{
    Stack s;
    while(root != NULL || !s.empty())
    {
        while(root!=NULL) //找到左子树
        {
            s.push(root); //先入栈
            root = root->left;
        }
        if(!s.empty())
        {
            root = s.pop(); //再访问
            visit(root);
            root = root->right; //通过下一次循环遍历右子树
        }
    }
}
中序遍历不用栈:
void inOrder3(TNode* root)
{
    while(root!=NULL)
    {
        while(root->left!=NULL && !root->left->bVisited)
        {
            root = root->left;
        }
        if(!root->bVisited)
        {
            visit(root);
            root->bVisited = true;
        }
        if(root->right!=NULL && !root->right->bVisited)
        {
            root = root->right;
        }
        else
        {
            root = root->parent; // 回溯
        }
    }
}
=================后序遍历===============
后序遍历的伪代码:
void PostOrder(TNode* root)
{
    stack s;
    if(root != NULL)
        s.push(root);
    while(!s.empty())
    {
        TNode* node = s.pop();
        if(node->bPushed) //其左右子树都已入栈,则访问该节点
        {
            visit(node);
        }
        else
        { //左右子树尚未入栈,则依次将根节点、右节点和左节点入栈
            s.push(node); // 1> root入栈
            if( node->right != NULL)
            {
                node->right->bPushed = false; //先把左右子树设为false
                s.push(node->right); // 2> 右子树入栈
            }
            if( node->left != NULL)
            {
                node->left->bPushed = false; //先把左右子树设为false
                s.push(node->left); // 3> 左子树入栈
            }
            node->bPushed = true; // 左右子树都已入栈,根节点可以访问了
           
        }
    }
}
=================层序遍历===============
分层遍历伪代码:
void levelOrder(TNode* root)
{
    Queue Q;
    Q.push(root);
   
    while(!Q.empty())
    {
        TNode* node = Q.front();
        visit(node);
        if( node->left != NULL)
        {
            Q.push(node->left);
        }
        if(node->right != NULL)
        {
            Q.push(node->right);
        }
    }
}
《编程之美》中使用vector容器来储存n个节点信息,并用一个游标变量last记录前一层的访问结束条件,实现如下:
void PrintNodeByLevel(Node* root)
{     
    vector vec; // 这里我们使用STL 中的vector来代替数组,可利用到其动态扩展的属性     
    vec.push_back(root);     
    int cur = 0;     
    int last = 1;     
    while(cur < vec.size()) {
        Last = vec.size(); // 新的一行访问开始,重新定位last于当前行最后一个节点的下一个位置
        while(cur < last) {
            cout << vec[cur]->data << " "; // 访问节点
           
            if(vec[cur] -> lChild) // 当前访问节点的左节点不为空则压入
                vec.push_back( vec[cur]->lChild );
            // 当前访问节点的右节点不为空则压入,注意左右节点的访问顺序不能颠倒
            if( vec[cur]->rChild )
                vec.push_back( vec[cur]->rChild );
            cur++;          
        }          
        cout << endl; // 当cur == last时,说明该层访问结束,输出换行符
    }
}
另外,
============求树深==========
//若T为空树,则深度为0,否则其深度等于左子树或右子树的最大深度加1
int getDepth(BiTree T)
{
    if   (T==NULL)   return   0;
    else{
        dep1 = getDepth(T-> lchild);
        dep2 = getDepth(T-> rchild);
        return dep1 > dep2 ? dep1+1 : dep2+1;
}
小结一下:
用栈来实现比增加指向父节点指针回溯更方便:
1.采用栈的方法,就是跟踪指针移动,用栈保存中间结果的实现方式,先序与中序难度一致,后序很困难。先序与中序只需要修改一下访问的位置即可。
2.采用增加父节点的方法,直接用栈来模拟递归,先序非常简单;而中序与后序难度一致。先序简单是因为节点可以直接访问,访问完毕后无需记录。
而中序与后序时,节点在弹栈后还不能立即访问,还需要等其他节点访问完毕后才能访问,因此节点需要设置标志位来判定,因此需要额外的O(n)空间。
附:C源程序
#include  
#include  
#define   MAX   20
#define   NULL   0
typedef     char   TElemType;
typedef     int   Status;
typedef   struct   BiTNode{
        TElemType   data;
        struct   BiTNode   *lchild,*rchild;
}BiTNode,*BiTree;
Status   CreateBiTree(BiTree   *T){
    char   ch;
    ch=getchar();
    if   (ch== '# ')   (*T)=NULL;                                         /*   #代表空指针*/
    else   {
        (*T)=(BiTree)   malloc(sizeof(BiTNode));/*申请结点       */
        (*T)-> data=ch;                                                 /*生成根结点     */
        CreateBiTree(&(*T)-> lchild)   ;                   /*构造左子树     */
        CreateBiTree(&(*T)-> rchild)   ;                   /*构造右子树     */
            }
    return   1;
}
void   PreOrder(BiTree   T){
          if   (T)   {
          printf( "%2c ",T-> data);         /*访问根结点,此处简化为输出根结点的数据值*/
          PreOrder(T-> lchild);             /*先序遍历左子树*/
          PreOrder(T-> rchild);             /*先序遍历右子树*/
          }
}
void   LevleOrder(BiTree   T){
/*层次遍历二叉树T,从第一层开始,每层从左到右*/
/*用一维数组表示队列,front和rear分别表示队首和队尾指针*/
    BiTree   Queue[MAX],b;  
    int   front,rear;
    front=rear=0;
   
    if(T)   /*若树非空*/
    {
        Queue[rear++]=T;   /*根结点入队列*/
        while(front != rear){  /*当队列非空*/
            b=Queue[front++];      /*队首元素出队列,并访问这个结点*/
            printf( "%2c ",b-> data);
            if(b-> lchild!=NULL)  
                Queue[rear++]=b-> lchild;   /*左子树非空,则入队列*/
            if(b-> rchild!=NULL)  
                Queue[rear++]=b-> rchild;   /*右子树非空,则入队列*/
            }
          }
}//LevelOrder
int getDepth(BiTree T)
{
    if   (T==NULL)   return   0;
    else{
        dep1 = getDepth(T-> lchild);
        dep2 = getDepth(T-> rchild);
        return dep1 > dep2 ? dep1+1 : dep2+1;
}//depth
main(){
    BiTree   T=NULL;
    printf( "\nCreate   a   Binary   Tree\n ");
    CreateBiTree(&T);     /*建立一棵二叉树T*/
    printf( "\nThe   preorder   is:\n ");
    PreOrder(T);               /*先序遍历二叉树*/
    printf( "\nThe   level   order   is:\n ");
    LevleOrder(T);           /*层次遍历二叉树*/
printf( "\nThe   depth   is:%d\n ",depth(T));
}
 
阅读(754) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~