PTA（树和二叉树）1-6 层次遍历

1-6 层次遍历

分数 3

作者 黄龙军

单位 绍兴文理学院

要求实现函数，输出二叉树的层次遍历序列，可借助STL（标准模板库）之queue（队列）。二叉树采用二叉链表存储，结点结构如下：

1
2
3
4
struct BiTNode {               // 结点结构
    char data;                 // 结点数据域
    BiTNode *lchild, *rchild;  // 左、右孩子指针
};

函数接口定义：

1
void LevelTraverse(BiTNode* T);

其中参数 T是指向二叉树根结点的指针。

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<queue>
#include<string>
using namespace std;

struct BiTNode {
    char data;
    BiTNode *lchild, *rchild;
};

void LevelTraverse(BiTNode* T);    // 层次遍历
BiTNode *createBT(string &s);  // 创建二叉树，s存放带虚结点的先序遍历序列

// 根据带虚结点的先序序列创建二叉树并调用层次遍历函数LevelTraverse输出层次遍历结果
int main() {
    string s;
    while(cin>>s) {
        BiTNode* root=createBT(s);
        LevelTraverse(root);
    }    
    return 0;
}

// 请在此处填写答案

// 按字符串s创建二叉树，返回根结点指针
BiTNode *createBT(string &s) {
    if(s[0]=='*') {
        s=s.substr(1);
        return NULL; 
    }
    BiTNode *p=new BiTNode;
    p->data=s[0];
    s=s.substr(1);
    p->lchild=createBT(s);
    p->rchild=createBT(s);
    return p;
}

输入样例：

1
2
HDA**C*B**GF*E***
-+a**xb**-c**d**/e**f**

输出样例：

1
2
HDGACFBE
-+/axefb-cd

我的错误代码

存在问题，因为层次遍历不能用递归实现（递归本质是深度优先思想），必须用队列按 “先入先出” 的规则逐层处理节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void LevelTraverse(BiTNode* T) {
    queue<char> queue; // 将遍历到的入队列
    if (T == NULL) {    // 指针指向空，直接退出
        return;
    } else { // T指向根节点
        queue.push(T->data); // 先将根节点入队列
        LevelTraverse(T->lchild);
        LevelTraverse(T->rchild);
    }
    while (!queue.empty()) {
        cout << queue.front();
        queue.pop();
    }
}
  • 我懂了，先把指向根节点的指针存入到队列里面
  • 每次判断队列是否是空，非空就依次访问队头，将队头的左右孩子入队，自己出队，这样就是从上到下，从左到右了

正确答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void LevelTraverse(BiTNode* T) {
    queue<BiTNode*> queue; // 将遍历到的入队列
    queue.push(T);
    while (!queue.empty()) {
        BiTNode *p = queue.front(); // p指向该根结点
        cout << p->data;
        queue.pop();
        if (p->lchild != NULL) {
            queue.push(p->lchild);
        }
        if (p->rchild != NULL) {
            queue.push(p->rchild);
        }
    }
    cout << endl;
}

  • 例子

    1
    2
    3
    4
    5
    6
    7
        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7
1
1 | 2 3 | 4 5 6 | 7