树查找

方法一：利用完全二叉树的性质，除最后一层外都是满二叉树，且最后一层的叶子结点都集中在树的左侧

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, d;//n代表节点个数，d代表深度 
void input(vector<int> &arr){
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
}
int main(){
    while(cin >> n){
        vector<int> arr(n);
        input(arr);
        cin >> d;
        int left = (int)pow(2, d - 1) - 1, right = (int)pow(2, d) - 2;
        if(left < 0 || right < 0 || left >= n || right >= n){
            printf("EMPTY\n");
            continue;
        }
        for(int i = left; i <= right; i++){
            printf("%d", arr[i]);
            if(i != right){
                printf(" ");
            }
        }
        printf("\n");    
    }
    return 0;
} 

方法二：建立完全二叉树进行层次遍历

#include <iostream>
#include <cstdio>
#include <utility>
#include <queue> 
using namespace std;

int d;//代表深度
struct node{
  int val;
  node* left, *right;
};
typedef pair<node*, int> tree;
node* newNode(int v){
    node* Node = new node;
    Node->val = v;
    Node->left = Node->right = NULL;
    return Node;
}
bool flag = false;
void bfs(node* root){
    int cnt = 0;
    queue<tree> q;
    q.push(make_pair(root, 1));
    while(!q.empty()){
        tree tmp = q.front();
        int h = tmp.second;    
        q.pop();
        if(h > d) break;
        if(h == d){
            flag = true;
            cnt++ ? printf(" %d", tmp.first->val) : printf("%d", tmp.first->val);
        }
        if(tmp.first->left != NULL){
            q.push(make_pair(tmp.first->left, h + 1));
        }
        if(tmp.first->right != NULL){
            q.push(make_pair(tmp.first->right, h + 1));
        }
    }
}
void Create(node*& root, vector<int> arr, int len, int index){
    if(index > len) return;
    root = newNode(arr[index]);
    Create(root->left, arr, len, 2 * index + 1);
    Create(root->right, arr, len, 2 * index + 2);
}
int main(){
    int n, x;
    while(cin >> n){
        node* root = NULL;
        vector<int> arr(n);
        for(int i = 0; i < n; i++){
            cin >> arr[i];
        }
        Create(root, arr, n, 0);
        cin >> d;
        bfs(root);
        if(!flag) printf("EMPTY\n");
        flag = false;    
    } 
    return 0;
}