3.12二叉树与堆

根据先序遍历建树

【题目描述】
输入一串先序遍历字符串，根据此字符串建立一个二叉树。
例如如下的先序遍历字符串：ABC##DE#G##F###
其中 '#' 表示的是空格，空格字符代表空树。
建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

【输入格式】
输入包括 1 行字符串，长度不超过 100。

【输出格式】
可能有多组测试数据，对于每组数据，
输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。
每个输出结果占一行。

【样例输入】abc##de#g##f###
【样例输出】c b e g d f a

【参考程序】

#include
using namespace std;
const int N=110;
char a[N];
int cnt=0;

typedef struct Node{
    char data;
    struct Node *lch, *rch;
}Node, *Tree;

//递归建树
struct Node* build(){
    struct Node *root=NULL;
    if(a[cnt++]!='#'){
        root = (struct Node*)malloc(sizeof(struct Node));
        root->data = a[cnt-1];
        root->lch = build();
        root->rch = build();
    }
    return root;
}

//中序遍历
void inorder(struct Node *root){
    if(root!=NULL){
        inorder(root->lch);
        printf("%c ", root->data);
        inorder(root->rch);
    }
}

//销毁二叉树
void del(struct Node* &root){
    if(root!=NULL){
        del(root->lch);
        del(root->rch);
        delete root;
        root = NULL;
    }
}
int main(){
    while(scanf("%s", a)!=EOF){
        cnt=0;
        struct Node *root=build();
        inorder(root);
        del(root);
        printf("\n");
    }
    return 0;
}

根据层序遍历和中序遍历建树

【题目描述】
给一棵二叉树的层序遍历序列和中序遍历序列，
求这棵二叉树的先序遍历序列和后序遍历序列。

【输入格式】
第一行一个正整数N（1<=N<=30），代表二叉树的结点个数（结点编号为1~N）。
接下来两行，每行N个正整数，分别代表二叉树的层序遍历序列和中序遍历序列。
数据保证序列中1~N的每个数出现且只出现一次。

【输出格式】
输出一行，包含N个正整数，代表二叉树的先序遍历序列。
每行末尾不输出额外的空格。

【样例输入】

7
3 5 4 2 6 7 1
2 5 3 6 4 7 1

【样例输出】

3 5 2 4 6 7 1

【参考程序】

根据前序遍历和中序遍历建树

【题目描述】
已知一棵二叉树的前序遍历和中序遍历，求二叉树的后序遍历。

【输入格式】
输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。
每组包括两个长度小于50 的字符串，
第一个字符串表示二叉树的先序遍历序列，
第二个字符串表示二叉树的中序遍历序。

【输出格式】
每组第一行输出二叉树的后序遍历序列，第二行输出二叉树的层次遍历序列

【样例输入】

2
abdegcf
dbgeafc
xnliu
lnixu

【样例输出】

dgebfca
abcdefg
linux
xnuli

【参考程序】

堆

堆的定义：堆（英语：heap）是计算机科学中一类特殊的数据结构的统称。
堆通常是一个可以被看做一棵树的数组对象，总是满足下列性质：

1. 堆中某个节点的值总是不大于或不小于其父节点的值；
2. 堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，
根节点最小的堆叫做最小堆或小根堆。
注意：堆内的元素并不一定数组下标顺序来排序的！！

具体操作：(我们以小根堆为例)

1. 上浮 shift_up
   从当前结点开始，和它的父亲节点比较，若是比父亲节点来的小，就交换，
   然后将当前询问的节点下标更新为原父亲节点下标；否则退出。

2. 下沉 shift_down
   让当前结点的左右儿子(如果有的话)作比较，哪个比较小就和它交换，
   并更新询问节点的下标为被交换的儿子节点下标，否则退出。

3. 插入 push
   每次插入的时候呢，我们都往最后一个插入，让后使它上浮。

4. 弹出 pop
   把堆顶元素弹掉，让根节点元素和尾节点进行交换，然后让当前的根元素下沉就可以了。

堆插入和删除，每次O(logN)

程序实现：

#include
using namespace std;
const int N=1e5+10;
int heap[N], size=0;

//建立大根堆
void put_less(int x){
    int son, father;
    size++;
    heap[size]=x;
    son=size;
    while(son>1){
        father = son/2;// 大根堆，父亲大于儿子
        if(heap[son]<=heap[father]) break;
        int temp=heap[son]; heap[son]=heap[father]; heap[father]=temp;
        son=father;
    }
}

//得到大根堆堆顶元素
int get_less(){
    int son, father, ans=0;
    ans=heap[1];
    heap[1]=heap[size];
    size--;
    father=1;
    while(father*2<=size){
        son = father*2;
        if(son1){
        father=son/2;
        if(heap[son]>=heap[father]) break;
        int temp=heap[son]; heap[son]=heap[father]; heap[father]=temp;
        son = father;
    }
}

//得到小根堆堆顶元素
int get_greater(){
    int son, father, ans=0;
    ans=heap[1];
    heap[1]=heap[size];
    size--;
    father=1;
    while(father*2<=size){
        son = father*2;
        if(sonheap[son+1]) son++;//找寻小的节点
        if(heap[son]>=heap[father]) break;
        int temp=heap[son]; heap[son]=heap[father]; heap[father]=temp;
        father=son;
    }
    return ans;
}

int main(){
    freopen("data.in", "r", stdin);
    int n, x; cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];

    memset(heap, 0, sizeof(heap)), size=0; //初始化
    for(int i=1; i<=n; i++) put_less(a[i]);//建立大根堆
    while(size) cout<