二叉树之分层遍历

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

图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，说明该层访问结束，输出换行符 
            }
        }