层次遍历以二叉链表存储的树或森林，#表示空格。输出序列为：ABCDEFGH。

Question

层次遍历以二叉链表存储的树或森林，#表示空格。输出序列为：ABCDEFGH。

Answer 1

参考二叉树的建成与遍历。

#include<iostream>
#include <vector>
#include <stack>
#include <queue>
#pragma warning(disable:4996)
using namespace std;
int n = 8;
vector<char> tree = { 'A', 'B', 'C', 'D', 'E', '*', 'F' };
vector<int> visited = { 0,0,0,0,0,0,0,0 };
int hasChild(int index) {
    if (index * 2 + 1 >= 7) {
        return -1;
    }
    // 左孩子
    if (!visited[index * 2 + 1] && tree[index * 2 + 1] != '*') {
        return index * 2 + 1;
    }
    // 右孩子
    else if (!visited[index * 2 + 2] && tree[index * 2 + 2] != '*') {
        return index * 2 + 2;
    }
    else {
        return -1;
    }
}
int main() {
    stack<int> dfs;
    int node = 0;
    dfs.push(node);
    while (dfs.size() != 0) {
        // 查询子节点
        // 子节点在上文中说过,是 node*2+1 node*2+2
        node = dfs.top();
        int child = hasChild(node);
        if ( child != -1) {
            dfs.push(child);
            visited[child] = 1;
            node = dfs.top();
        }
        else {
            node = dfs.top();
            dfs.pop();
        }
        //,不在算法内,只是为了打印栈内元素
        cout << "栈内元素:从栈顶到栈底=>";
        stack<int> s2;
        s2 = dfs;
        while (!s2.empty()) {
            cout << tree[s2.top()] << " ";
            s2.pop();
        }
        cout << endl;
    }
    cout << endl;
    visited = { 0,0,0,0,0,0,0,0 };
    queue<int> bfs;
    node = 0;
    bfs.push(node);
    while (bfs.size() != 0) {
        node = bfs.front();
        int child = hasChild(node);
        // 第一次访问左孩子
        if (child != -1) {
            bfs.push(child);
            visited[child] = 1;
            node = bfs.front();
        }
        child = hasChild(node);
        if (child != -1) {
            bfs.push(child);
            visited[child] = 1;
            node = bfs.front();
        }
        else {
            node = bfs.front();
            bfs.pop();
        }
        //,不在算法内,只是为了打印栈内元素
        cout << "队内元素:从队首到队尾=>";
        queue<int> s2;
        s2 = bfs;
        while (!s2.empty()) {
            cout << tree[s2.front()] << " ";
            s2.pop();
        }
        cout << endl;
    }
    cout << endl;
}