#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct heu{ //结构体，存储待查询的编号与内容
    int number;
    int node_num;
} id_cat;

int compare(const void* a, const void* b){  //比较函数，用于qsort
    return(((id_cat*)a)-> number - ((id_cat*)b)-> number);
}

int father_node(int t){  //给出节点编号（数组中的位置）计算父节点位置（数组中的位置）
    if((t + 1) % 3 == 0)
        return (t + 1) / 3;
    else if((t - 1) % 3 == 0)
        return (t - 1) / 3;
    else if(t % 3 == 0)
        return t / 3;
}

void father_nodes(int s[], int t, int* a, int* i){  // 给出节点编号计算包括该节点在内的所有祖先节点的内容， 数组倒着排
    a[*i] = s[t];
    (*i)++;
    while(t != 1){
        t = father_node(t);
        a[*i] = s[t];
        (*i)++;
    }
}

int main(){
 ...