二叉树的分层遍历

海天一树

发布于 2018-04-17 11:17:15

8500

发布于 2018-04-17 11:17:15

文章被收录于专栏：海天一树海天一树

给定一棵二叉树，要求从上到下从左到右分层输出该二叉树的节点值。

bitree.png

一、递归法

二叉树本身就带有递归属性，通常我们可以用递归方法解决。假设要访问第k层节点，那么其实可以转换成分别访问“以该二叉树根节点的左右子节点为根节点的两棵子树”中层次为k-1的节点（root所在的层看作是第0层）。此方法理论上需要求出二叉树的深度，实际上访问到二叉树某一层次失败的时候返回就可以了。具体见代码：

#include <iostream>
#include <malloc.h>
using namespace std;
struct Node
{
    struct Node *lchild;//左孩子指针
    struct Node *rchild;//右孩子指针
    int data;           //节点数值
};
//创建结点
Node* createTreeNode(int data)
{
    Node *n=(Node *)malloc(sizeof(Node));
    n->data = data;
    n->lchild = NULL;
    n->rchild = NULL;
    return n;
}
//遍历第level层的所有结点
int printNodeAtLevel(Node *root, int level)
{
    if(root == NULL || level < 0)
    {
        return 0;
    }
    if(level == 0)
    {
        cout << root -> data << " ";
        return 1;
    }
    return printNodeAtLevel(root -> lchild, level - 1) + printNodeAtLevel(root -> rchild, level - 1);
}
//遍历所有层
void levelTraverse(Node *root)
{
    for(int level = 0; ; level++)
    {
        if(!printNodeAtLevel(root, level))
        {
            break;
        }
    }
}
int main()
{
    Node* n1 = createTreeNode(1);
    Node* n2 = createTreeNode(2);
    Node* n3 = createTreeNode(3);
    Node* n4 = createTreeNode(4);
    Node* n5 = createTreeNode(5);
    Node* n6 = createTreeNode(6);
    Node* n7 = createTreeNode(7);
    Node* n8 = createTreeNode(8);
    n1->lchild = n2;
    n1->rchild = n3;
    n2->lchild = n4;
    n2->rchild = n5;
    n3->rchild = n6;
    n6->lchild = n7;
    n6->rchild = n8;
    levelTraverse(n1);
    return 0;
}

运行结果：

1 2 3 4 5 6 7 8

缺点：递归法往往需要重复计算，效率不高。上面的递归遍历，对每一层的访问都需要从根节点开始，直到访问完所有的层次，造成效率极低。

二、使用数组和两个游标的非递归方法

在访问k层的时候，我们只需要知道k-1层的信息就足够了，所以在访问第k层的时候，要是能够知道k-1层的节点信息，就不再需要从根节点开始遍历了。

根据上述分析，可以从根节点出发，依次将每一层的根节点从左往右压入一个数组，并并用一个游标cur记录当前访问的节点，另一个游标last指示当前层次的最后一个节点的下一个位置，以cur===last作为当前层次访问结束的条件，在访问某一层的同时将该层的所有节点的子节点压入数组，在访问完某一层之后，检查是否还有新的层次可以访问，直到检查完所有的层次（不再有新的节点可以访问）

#include <iostream>
#include <malloc.h>
#include <vector>
using namespace std;
struct Node
{
    struct Node *lchild;//左孩子指针
    struct Node *rchild;//右孩子指针
    int data;           //节点数值
};
//创建结点
Node* createTreeNode(int data)
{
    Node *n=(Node *)malloc(sizeof(Node));
    n->data = data;
    n->lchild = NULL;
    n->rchild = NULL;
    return n;
}
//分层遍历
void levelTraverse(Node *root)
{
    if(root == NULL)
    {
        return;
    }
    vector<Node *> vec;
    vec.push_back(root);
    int cur = 0;
    int last = vec.size();
    while(cur < (int)vec.size())
    {
        //定位last为当前行最后一个节点的下一个位置，即下行的首位置
        last = vec.size();
        while(cur < last)   //cur位于当前行时
        {
            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++;//cur后移
        }
        cout << endl;//当cur与last相等时，说明该层访问结束，换行
    }
}
int main()
{
    Node* n1 = createTreeNode(1);
    Node* n2 = createTreeNode(2);
    Node* n3 = createTreeNode(3);
    Node* n4 = createTreeNode(4);
    Node* n5 = createTreeNode(5);
    Node* n6 = createTreeNode(6);
    Node* n7 = createTreeNode(7);
    Node* n8 = createTreeNode(8);
    n1->lchild = n2;
    n1->rchild = n3;
    n2->lchild = n4;
    n2->rchild = n5;
    n3->rchild = n6;
    n6->lchild = n7;
    n6->rchild = n8;
    levelTraverse(n1);
    return 0;
}

运行结果：