新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> We choose to study algorithmic problems,  not because they are easy,  but because they are hard.
    [返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『 算法理论与分析 』 → 层序遍历二叉树［原创］ ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 37728 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 层序遍历二叉树［原创］ 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     binaryluo 帅哥哟，离线，有人找我吗？
      
      
      威望：6
      等级：研二(Pi-Calculus看得一头雾水)(版主)
      文章：679
      积分：5543
      门派：IEEE.ORG.CN
      注册：2005/2/19

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给binaryluo发送一个短消息 把binaryluo加入好友 查看binaryluo的个人资料 搜索binaryluo在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看binaryluo的博客楼主
    发贴心情 层序遍历二叉树［原创］

    要求：设计一个算法层序遍历二叉树（同一层从左到右访问）。

    我写了一个算法：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。

    Status HierarchyBiTree(BiTree T, Status (*Visit)(TElemType e)) {
            LinkQueue *Q;     // 保存当前节点的左右孩子的队列
            
            InitQueue(Q);       // 初始化队列

            if (T == NULL) return ERROR; //树为空则返回
            p = T;                  // 临时保存树根T到指针p中
            Visit(p->data);      // 访问根节点
            if (p->lchild) EnQueue(Q, p->lchild);  // 若存在左孩子，左孩子进队列
            if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列

            while (!QueueEmpty(Q)) {                // 若队列不空，则层序遍历
                    DeQueue(Q, p);                       // 出队列
                    Visit(p->data);                         // 访问当前节点

                    if (p->lchild) EnQueue(Q, p->lchild);  // 若存在左孩子，左孩子进队列
                    if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列
            }

            DestroyQueue(Q);                           // 释放队列空间
            return OK;
    }

    算法分析：假设T有n个节点。因为本算法中基本操作是Visit(p->data)，则时间复杂度为O(n)；由于用一个队列保存当前孩子的节点，所以队列占用的额外空间为该二叉树的叶子节点数，最好情况是一棵只有左分支或只有右分支的单边树，此时占用空间最少，仅为1。最坏情况是该树是满二叉树，此时占用的空间最多为（n+1）/2。


       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/1/24 23:35:00
     
     elfstone 帅哥哟，离线，有人找我吗？射手座1983-12-6
      
      
      等级：大四(总算啃完XML规范了)
      文章：185
      积分：1177
      门派：IEEE.ORG.CN
      注册：2006/2/25

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给elfstone发送一个短消息 把elfstone加入好友 查看elfstone的个人资料 搜索elfstone在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看elfstone的博客第2楼
    发贴心情 
    我以前写的一个层次遍历森林的算法,在此作为补充
    void travel_tree(tree t)    //tree为森林结构
    {
        tree tmp=t;
        while(tmp!=NULL)
        {
         visite_tnode(tmp);    //   visite_tnode为访问树结点函数，主要是打标记
         if(tmp->firstson!=NULL)
             seqqueue_enqueue(s,tmp->firstson);    //入队
         while(tmp->nextbrother!=NULL)
         {
             tmp=tmp->nextbrother;       //兄弟节点不为空就访问兄弟节点
             visite_tnode(tmp);
             if(tmp->firstson!=NULL)        //同时保存该节点的第一个子节点
          seqqueue_enqueue(s,tmp->firstson);
         }
         seqqueue_outqueue(s,tmp);     //一层（一枝）结束后，由队列中拿到下一层（一枝）的节点
        }
    }

    ----------------------------------------------
    Ich liebe erst meines Leben...

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/3/5 14:34:00
     
     detivoli 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：1
      积分：58
      门派：IEEE.ORG.CN
      注册：2006/3/17

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给detivoli发送一个短消息 把detivoli加入好友 查看detivoli的个人资料 搜索detivoli在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看detivoli的博客第3楼
    发贴心情 
    算法设计一直没有很好的学习,以前上DA的时候,老师说层次遍历不是太重要,也没怎么去看,自己也没认真看过.
    还好,能够看懂!

    ----------------------------------------------
    I am free.

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/3/17 12:21:00
     
     bigqueues 美女呀，离线，快来找我吧！
      
      
      等级：大一新生
      文章：2
      积分：69
      门派：XML.ORG.CN
      注册：2006/4/25

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给bigqueues发送一个短消息 把bigqueues加入好友 查看bigqueues的个人资料 搜索bigqueues在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看bigqueues的博客第4楼
    发贴心情 
    呵呵,顶一个
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/27 18:11:00
     
     LEAGUE 美女呀，离线，快来找我吧！
      
      
      等级：大一新生
      文章：3
      积分：72
      门派：XML.ORG.CN
      注册：2006/7/7

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给LEAGUE发送一个短消息 把LEAGUE加入好友 查看LEAGUE的个人资料 搜索LEAGUE在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看LEAGUE的博客第5楼
    发贴心情 
    ding~~~~~~~~~~
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/10 13:58:00
     
     wnn349308824 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：2
      积分：61
      门派：XML.ORG.CN
      注册：2006/6/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给wnn349308824发送一个短消息 把wnn349308824加入好友 查看wnn349308824的个人资料 搜索wnn349308824在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看wnn349308824的博客第6楼
    发贴心情 
    广搜
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/9 23:49:00
     
     sjx19871109 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：1
      积分：56
      门派：XML.ORG.CN
      注册：2008/4/17

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给sjx19871109发送一个短消息 把sjx19871109加入好友 查看sjx19871109的个人资料 搜索sjx19871109在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看sjx19871109的博客第7楼
    发贴心情 顶一个
    刚学数据结构，一直不太清楚队列的用途，现在终于看到了，谢谢！
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/4/17 12:08:00
     
     netjian 帅哥哟，离线，有人找我吗？白羊座1986-4-16
      
      
      头衔：智能入门者
      等级：大四(GRE考了1600分!)
      文章：198
      积分：1332
      门派：IEEE.ORG.CN
      注册：2007/5/5

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给netjian发送一个短消息 把netjian加入好友 查看netjian的个人资料 搜索netjian在『 算法理论与分析 』的所有贴子 点击这里发送电邮给netjian  引用回复这个贴子 回复这个贴子 查看netjian的博客第8楼
    发贴心情 
    对于某些搜索，如赫夫曼树，层序遍历是非常重要的。

    ----------------------------------------------
    长江后浪，无坚不摧。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/4/28 22:42:00
     
     冬天的农夫 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(面向对象是个好东东!)
      文章：85
      积分：606
      门派：XML.ORG.CN
      注册：2006/7/1

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给冬天的农夫发送一个短消息 把冬天的农夫加入好友 查看冬天的农夫的个人资料 搜索冬天的农夫在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看冬天的农夫的博客第9楼
    发贴心情 
    你写这个代码要说明什么问题？？？？？？？//
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/4/30 15:13:00
     
     lxztju 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：10
      积分：101
      门派：XML.ORG.CN
      注册：2006/1/3

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给lxztju发送一个短消息 把lxztju加入好友 查看lxztju的个人资料 搜索lxztju在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看lxztju的博客第10楼
    发贴心情 
    有参考价值
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/5/1 10:56:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 算法理论与分析 』的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/7/1 9:35:09

    本主题贴数12，分页： [1] [2]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 78.125ms