【树的应用】——列出叶结点 (25分)（附测试点）-白红宇

【树的应用】——列出叶结点 (25分)（附测试点）

阅读量：99 次

发布时间：2019-02-26

本文共 1902 字，大约阅读时间需要 6 分钟。

为了解决这个问题，我们需要构建一个二叉树，并按从上到下、从左到右的顺序输出所有叶节点的编号。叶节点是指没有左孩子和右孩子的节点。

方法思路

读取输入：首先读取输入数据，确定树的节点总数和每个节点的左、右孩子。

构建树结构：使用数组来表示每个节点的左、右孩子和节点值。

确定根节点：根节点是没有作为任何其他节点左或右孩子出现的节点。

层次遍历：使用队列来进行层次遍历，检查每个节点是否为叶节点，并收集这些叶节点。

输出结果：将收集到的叶节点编号按顺序输出。

解决代码

#include 
   
    #include 
    
     #include 
     
      using namespace std;struct Node {    int data;    int left;    int right;};int main() {    int n;    cin >> n;    Node nodes[n];    for (int i = 0; i < n; ++i) {        char a, b;        cin >> a >> b;        nodes[i].left = (a != '-') ? (a - '0') : -1;        nodes[i].right = (b != '-') ? (b - '0') : -1;        nodes[i].data = i;    }        bool used[n] = {false};    for (int i = 0; i < n; ++i) {        int left = nodes[i].left;        int right = nodes[i].right;        if (left != -1 && left < n) {            used[left] = true;        }        if (right != -1 && right < n) {            used[right] = true;        }    }    int root = -1;    for (int i = 0; i < n; ++i) {        if (!used[i]) {            root = i;            break;        }    }        queue
      
        q;    vector
       
         result;    q.push(root);    while (!q.empty()) {        int current = q.front();        q.pop();                if (nodes[current].left == -1 && nodes[current].right == -1) {            result.push_back(current);        }                if (nodes[current].left != -1) {            q.push(nodes[current].left);        }        if (nodes[current].right != -1) {            q.push(nodes[current].right);        }    }        if (!result.empty()) {        cout << result[0];        for (int i = 1; i < result.size(); ++i) {            cout << " " << result[i];        }    }    return 0;}