层次遍历二叉树（编程之美3.10）

时间：2014-02-21 13:49:52 阅读：263 评论：0 收藏：0 [点我收藏+]

bubuko.com,布布扣

问题（假定根节点位于第0层）

1. 层次遍历二叉树（每层换行分开）

2. 层次遍历二叉树指定的某层

例如

上图中

第三层
7 8

可以看出得出第二问的解，第一问迎刃而解了，所以从问题二下手

分析与解

1. 层次遍历二叉树指定的某层

可以得出这样的一个结论：遍历二叉树的第k层，相当于遍历二叉树根节点的左右子树的第k-1层。这样一直遍历下去，知道k=0时，输出节点即可。

参考代码

int PrintNodeAtLevel(BiTree root, int level)
{
    if(!root || level < 0)
        return 0;
    else if(level == 0)
    {
        cout << root->data << endl;
        return 1;
    }
    else
        return PrintNodeAtLevel(root->left, level - 1) + PrintNodeAtLevel(root->right, level - 1);
}

完整执行代码

#include<iostream>
using namespace std;
typedef struct BiTNode
{
    int data;
    BiTNode *left;
    BiTNode *right;
}BiTNode, *BiTree;

void createTree(BiTree &root)
{
    BiTree left1 = new(BiTNode);
    BiTree right1 = new(BiTNode);
    
    left1->data = 1;
    left1->left = NULL;
    left1->right = NULL;
    right1->data = 2;
    right1->left = NULL;
    right1->right = NULL;

    root->left = left1;
    root->right = right1;


    BiTree left2 = new(BiTNode);
    left2->data = 3;
    left2->left = NULL;
    left2->right = NULL;
    BiTree right2 = new(BiTNode);
    right2->data = 4;
    right2->left = NULL;
    right2->right = NULL;
    left1->left = left2;
    left1->right = right2;

    BiTree left3 = new(BiTNode);
    left3->data = 5;
    left3->left = NULL;
    left3->right = NULL;
    BiTree right3 = new(BiTNode);
    right3->data = 6;
    right3->left = NULL;
    right3->right = NULL;
    left2->left = left3;
    left2->right = right3;
}

void deleteTree(BiTree root)
{
    if(root)
    {
        deleteTree(root->left);
        deleteTree(root->right);
        delete(root);
        root = NULL;
    }
}

int PrintNodeAtLevel(BiTree root, int level)
{
    if(!root || level < 0)
        return 0;
    else if(level == 0)
    {
        cout << root->data << endl;
        return 1;
    }
    else
        return PrintNodeAtLevel(root->left, level - 1) + PrintNodeAtLevel(root->right, level - 1);
}

int main()
{
    BiTree root = new(BiTNode);
    root->data = 0;
    root->right = root->left = NULL;
    createTree(root);    
    cout << "Level 0:" << endl;
    PrintNodeAtLevel(root, 0);
    cout << "-------------------" << endl;
    cout << "Level 1:" << endl;
    PrintNodeAtLevel(root, 1);
    cout << "-------------------" << endl;
    cout << "Level 2:" << endl;
    PrintNodeAtLevel(root, 2);
    cout << "-------------------" << endl;
    cout << "Level 3:" << endl;
    PrintNodeAtLevel(root, 3);
    cout << "-------------------" << endl;
    deleteTree(root);
}

View Code

执行结果

bubuko.com,布布扣

2. 层次遍历二叉树

解法1——根据求得的层次，遍历每一层

参考代码

void TranverseTree(BiTree root)
{
    for(int i = 0; i < Height(root); ++i)
    {
        PrintNodeAtLevel(root, i);
        cout << "_____________________________" << endl;
    }
}

完整执行程序

#include<iostream>
using namespace std;
typedef struct BiTNode
{
    int data;
    BiTNode *left;
    BiTNode *right;
}BiTNode, *BiTree;

int maxDis = 0;

void createTree(BiTree &root)
{
    BiTree left1 = new(BiTNode);
    BiTree right1 = new(BiTNode);
    
    left1->data = 1;
    left1->left = NULL;
    left1->right = NULL;
    right1->data = 2;
    right1->left = NULL;
    right1->right = NULL;

    root->left = left1;
    root->right = right1;


    BiTree left2 = new(BiTNode);
    left2->data = 3;
    left2->left = NULL;
    left2->right = NULL;
    BiTree right2 = new(BiTNode);
    right2->data = 4;
    right2->left = NULL;
    right2->right = NULL;
    left1->left = left2;
    left1->right = right2;

    BiTree left3 = new(BiTNode);
    left3->data = 5;
    left3->left = NULL;
    left3->right = NULL;
    BiTree right3 = new(BiTNode);
    right3->data = 6;
    right3->left = NULL;
    right3->right = NULL;
    left2->left = left3;
    left2->right = right3;
}

void deleteTree(BiTree root)
{
    if(root)
    {
        deleteTree(root->left);
        deleteTree(root->right);
        delete(root);
        root = NULL;
    }
}

int PrintNodeAtLevel(BiTree root, int level)
{
    if(!root || level < 0)
        return 0;
    else if(level == 0)
    {
        cout << root->data << endl;
        return 1;
    }
    else
        return PrintNodeAtLevel(root->left, level - 1) + PrintNodeAtLevel(root->right, level - 1);
}

int Height(BiTree root)
{
    if(root == NULL)
        return 0;
    else
        return Height(root->left) > Height(root->right) ? Height(root->left)+1 : Height(root->right) + 1;
}

void TranverseTree(BiTree root)
{
    for(int i = 0; i < Height(root); ++i)
    {
        PrintNodeAtLevel(root, i);
        cout << "_____________________________" << endl;
    }
}

int main()
{
    BiTree root = new(BiTNode);
    root->data = 0;
    root->right = root->left = NULL;
    createTree(root);    
    TranverseTree(root);
    deleteTree(root);
}

View Code

执行结果

bubuko.com,布布扣

解法2——无需求得层次，根据遍历每层的返回信息确定遍历

参考代码

void TranverseTree(BiTree root)
{
    for(int i = 0; ; ++i)
    {
        if(!PrintNodeAtLevel(root, i))
            break;
        cout << "_____________________________" << endl;
    }
}

完整执行代码

#include<iostream>
using namespace std;
typedef struct BiTNode
{
    int data;
    BiTNode *left;
    BiTNode *right;
}BiTNode, *BiTree;

int maxDis = 0;

void createTree(BiTree &root)
{
    BiTree left1 = new(BiTNode);
    BiTree right1 = new(BiTNode);
    
    left1->data = 1;
    left1->left = NULL;
    left1->right = NULL;
    right1->data = 2;
    right1->left = NULL;
    right1->right = NULL;

    root->left = left1;
    root->right = right1;


    BiTree left2 = new(BiTNode);
    left2->data = 3;
    left2->left = NULL;
    left2->right = NULL;
    BiTree right2 = new(BiTNode);
    right2->data = 4;
    right2->left = NULL;
    right2->right = NULL;
    left1->left = left2;
    left1->right = right2;

    BiTree left3 = new(BiTNode);
    left3->data = 5;
    left3->left = NULL;
    left3->right = NULL;
    BiTree right3 = new(BiTNode);
    right3->data = 6;
    right3->left = NULL;
    right3->right = NULL;
    left2->left = left3;
    left2->right = right3;
}

void deleteTree(BiTree root)
{
    if(root)
    {
        deleteTree(root->left);
        deleteTree(root->right);
        delete(root);
        root = NULL;
    }
}

int PrintNodeAtLevel(BiTree root, int level)
{
    if(!root || level < 0)
        return 0;
    else if(level == 0)
    {
        cout << root->data << endl;
        return 1;
    }
    else
        return PrintNodeAtLevel(root->left, level - 1) + PrintNodeAtLevel(root->right, level - 1);
}

void TranverseTree(BiTree root)
{
    for(int i = 0; ; ++i)
    {
        if(!PrintNodeAtLevel(root, i))
            break;
        cout << "_____________________________" << endl;
    }
}

int main()
{
    BiTree root = new(BiTNode);
    root->data = 0;
    root->right = root->left = NULL;
    createTree(root);    
    TranverseTree(root);
    deleteTree(root);
}

View Code

执行结果

bubuko.com,布布扣

解法3——无需求每次都从根说起，一次遍历成功

可以看出，解法1、2每次都需要从根说起，还可以不从跟谈起，一次遍历所有的节点，不过这需要额外的存储空间

思路

定义两个指针：cur、last.cur指向目前该访问的节点位置，last指向目前队列中最后一个元素的后一个位置

遍历每一层时，遍历每一个元素是cur往后移动，同时把cur指向的左右孩子加入到队列中，当cur==last时说明该层已经遍历完事了。

参考代码

void TranverseTree(BiTree root)
{
    vector<BiTree> vec;
    vec.push_back(root);
    int cur =0, last = 1;
    while(cur < vec.size())
    {
        last = vec.size();
        while(cur < last)
        {
            cout << vec[cur]->data << " ";
            if(vec[cur]->left)
                vec.push_back(vec[cur]->left);
            if(vec[cur]->right)
                vec.push_back(vec[cur]->right);
            ++cur;
        }
        cout << endl;
    }
}

完整执行代码

#include <iostream>
#include <vector>
using namespace std;
typedef struct BiTNode
{
    int data;
    BiTNode *left;
    BiTNode *right;
}BiTNode, *BiTree;

int maxDis = 0;

void createTree(BiTree &root)
{
    BiTree left1 = new(BiTNode);
    BiTree right1 = new(BiTNode);
    
    left1->data = 1;
    left1->left = NULL;
    left1->right = NULL;
    right1->data = 2;
    right1->left = NULL;
    right1->right = NULL;

    root->left = left1;
    root->right = right1;


    BiTree left2 = new(BiTNode);
    left2->data = 3;
    left2->left = NULL;
    left2->right = NULL;
    BiTree right2 = new(BiTNode);
    right2->data = 4;
    right2->left = NULL;
    right2->right = NULL;
    left1->left = left2;
    left1->right = right2;

    BiTree left3 = new(BiTNode);
    left3->data = 5;
    left3->left = NULL;
    left3->right = NULL;
    BiTree right3 = new(BiTNode);
    right3->data = 6;
    right3->left = NULL;
    right3->right = NULL;
    left2->left = left3;
    left2->right = right3;
}

void deleteTree(BiTree root)
{
    if(root)
    {
        deleteTree(root->left);
        deleteTree(root->right);
        delete(root);
        root = NULL;
    }
}

void TranverseTree(BiTree root)
{
    vector<BiTree> vec;
    vec.push_back(root);
    int cur =0, last = 1;
    while(cur < vec.size())
    {
        last = vec.size();
        while(cur < last)
        {
            cout << vec[cur]->data << " ";
            if(vec[cur]->left)
                vec.push_back(vec[cur]->left);
            if(vec[cur]->right)
                vec.push_back(vec[cur]->right);
            ++cur;
        }
        cout << endl;
    }
}

int main()
{
    BiTree root = new(BiTNode);
    root->data = 0;
    root->right = root->left = NULL;
    createTree(root);    
    TranverseTree(root);
    deleteTree(root);
}

View Code

执行结果

bubuko.com,布布扣

层次遍历二叉树（编程之美3.10）

原文：http://www.cnblogs.com/kaituorensheng/p/3558645.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)