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

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

阅读量：99 次

发布时间：2019-02-26

本文共 1960 字，大约阅读时间需要 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;
}