题解 | 树查找

#include <iostream>
#include <queue>
#include <math.h>
using namespace std;

typedef struct Node{
    int data;
    Node * lchild, * rchild;
}Node;

void create(Node* &n){
    n = new Node;
    cin >> n->data;
    n->lchild = n->rchild = NULL;
}

Node* build_tree(int n){
    queue<Node*> q;
    // 头节点
    Node *head;
    create(head);
    q.push(head);
    n--;
    Node *cur, *lchild, *rchild;
    while(n>0){
        // 根节点
        cur = q.front();
        q.pop();
        // 左孩子
        create(lchild);
        cur->lchild = lchild;
        q.push(lchild);
        n--;
        // 右孩子
        if(n>0){
            create(rchild);
            cur->rchild = rchild;
            q.push(rchild);
            n--;
        }
    }
    return head;
}

void print(Node *head, int n, int d){
    int base = pow(2, d-1)-1;
    int top = pow(2, d)-1;
    int i=0;

    if(n < base+1){
        cout << "EMPTY" << endl;
    }

    queue<Node*> q;
    q.push(head);
    while(i<n){
        Node *cur = q.front();
        q.pop();
        i++;
        if(i>base && i<top){
            cout << cur->data << " ";
        }else if(i == top){
            cout << cur->data << endl;
            break;
        }
        if(cur->lchild != NULL){
            q.push(cur->lchild);
        } 
        if(cur->rchild != NULL){
            q.push(cur->rchild);
        }
    }
}

int main() {
    int n, d;
    while(cin>>n){
        // 建树
        Node * head = build_tree(n);
        cin>>d;
        print(head, n, d);
    }
    return 0;
}