Chinaunix首页 | 论坛 | 博客
  • 博客访问: 483458
  • 博文数量: 285
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 629
  • 用 户 组: 普通用户
  • 注册时间: 2013-10-14 17:53
个人简介

相信自己,快乐每一天

文章分类

全部博文(285)

分类: 架构设计与优化

2013-11-01 15:03:41

原文地址:二叉树之分层遍历 作者:scq2099yt

一、结点结构
        在二叉树的链接存储中,通常采用的方法是:每个结点中设置三个域,即值域、左指针域和右指针域,其结点结构如下:

图1 二叉树结点结构
        其中,data表示值域,用于存储放入结点的数据元素,left和right分别表示左指针域和右指针域,用于分别存储左孩子和右孩子结点(即左右子树的根结点)的存储位置(即指针)。
        链接存储的指针类型和结点定义如下:
        typedef struct bnode
        {
            ElemType data;
            struct bnode *left, *right;
        }btree;
        其中,ElemType可以是任意数据类型如int、float或者char等,在算法中,规定其默认为int类型。

二、递归遍历
        分层遍历原理:从上到下层按层次访问二叉树,每一层按照从左到右的顺序访问,根节点为第0层,且每个结点仅访问一次。分层遍历问题可以分为几个阶段来解决,首先求访问某层结点的算法,再根据二叉树的深度循环访问每层结点,其递归算法如下:
1、访问某层结点
        void PrintNodeAtLevel(btree *root, int level)
        {
            if ((NULL == root) || (level < 0))
            {
                return 0;
            }
            if (0 == level)
            {
                printf("%d ", root->data)
                return 1;
            }
            return PrintNodeAtLevel(root->left, level-1) + PrintNodeAtLevel(root->right, level-1);
        }
        上面函数输出以root为根节点中的第level层中的所有节点(从左到右),成功返回1,失败则返回0。
2、求二叉树深度
        若一棵二叉树为空,则其深度为0,否则其深度等于左子树和右子树的最大深度加1,其递归算法代码如下:
        int depth(btree *b)
        {
            int dep1, dep2;
            if (NULL == b)
            {
                return (0);
            }
            else
            {
                dep1 = depth(b->left);
                dep2 = depth(b->right);
                if (dep1 > dep2)
                {
                    return (dep1+1);
                }
                else
                {
                    return (dep2+1);
                }
            }
        }

3、循环遍历每层
        void PrintNodeByLevel(btree *root, int depth)
        {
            for (int level=0; level             {
                PrintNodeAtLevel(root, level);
                printf("\n");
            }
        }
        depth为二叉树深度,有步骤2中函数求得。
4、直接层次遍历
        步骤2和3其实可以合并,即可以不必单独求二叉树深度,而是当访问二叉树某一层次失败的时候返回即可,具体代码如下:
        void PrintNodeByLevel(btree *root)
        {
            for (int level=0; ;l level++)
            {
                if (!PrintNodeAtLevel(root, level))
                {
                    break;
                }
                printf("\n");
            }
        }
        前面算法有它的有点,比如:思路清晰、代码简介,但也有其固有的缺陷,比如:效率低即计算时间和占用空间多,每层访问都从根节点开始直到访问完所有层次。

三、非递归遍历
        在访问第k层的时候,只需要直到第k-1层的节点信息就足够了,这样在访问第k层的时候,就不再需要从根节点开始遍历了。根据前面分析,可以从根节点出发,依次将每层的节点从左到右压入一个数组,并用一个游标Cur记录当前访问的节点,另一个游标Last指示当前层次的最后一个节点的下一个位置,以Cur==Last作为当前层次访问结束的条件,在访问某一层的同时将该层的所有节点的子节点压入数组,在访问完某一层之后,检查是否还有新的层次可以访问,直到访问完所有的层析(不再有新节点可以访问)。具体代码如下:
        void PrintNodeByLevel(btree *root)
        {
            if (NULL == root)
            {
                return;
            }     
            vector vec;       
            vec.push_back(root);
            int cur=0, last=1;
            while (cur < vec.size())
            {
                last = vec.size();                            // 新的一行访问开始,重新定位last于当前行最后一个节点的下一个位置
                while (cur < last)
                {
                    printf("%d ", vec[cur]->data);     // 访问节点
                    if (!vec[cur]->left)                     // 当前访问节点的左节点不为空则压入 
                    {
                        vec.push_back(vec[cur]->left);  
                    }
                    if (!vec[cur]->right)                    // 当前访问节点的右节点不为空则压入,注意左右节点的访问顺序不能颠倒
                    {
                        vec.push_back(vec[cur]->right);
                    }
                    cur++;
                }
                printf("\n");                                   // 当cur==last,说明该层访问结束,输出换行符 
            }
        }






阅读(332) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~