從PAT甲級1064題說開去

原題連結：https://www.patest.cn/contests/pat-a-practise/1064

這題的意思是，給定一系列樹，要用它構造一棵完全二叉樹，這棵完全二叉樹滿足二叉查找樹的性質。

在二叉樹的周遊中提到了完全二叉樹的概念，它是一棵隻有最後一層不滿，其他所有層都填滿的樹，最後一層從左向右依次填滿。在二叉樹的恢複中提到了二叉查找樹的性質，它的左子樹上的節點均小于它，右子樹的節點都大于等于它，左子樹右子樹都是二叉查找樹。

這樣這題的思路就很清晰了：既然這棵樹是完全二叉樹，那這棵樹的形狀是固定下來的，再把排序好的數字往裡填就可以了。

我利用了二叉樹在每層上節點個數的性質，疊代地找到每一棵（子）樹的根節點，建立完二叉樹以後再層序周遊。

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

int listof2[] = { , , , , , , , , , ,  };

struct tree_node
{
    int data = ;
    tree_node* left_child = NULL;
    tree_node* right_child = NULL;
};

void find_insert_node(tree_node* &this_node, int node_num, int *data_formal)
{
    if (node_num == ) return;
    if (node_num == )
    {
        this_node = new tree_node;
        this_node->data = *data_formal;
        return;
    }
    if (node_num == )
    {
        this_node = new tree_node;
        this_node->data = *(data_formal + );
        this_node->left_child = new tree_node;
        this_node->left_child->data = *data_formal;
        return;
    }
    if (node_num == )
    {
        this_node = new tree_node;
        this_node->data = *(data_formal + );
        this_node->left_child = new tree_node;
        this_node->left_child->data = *data_formal;
        this_node->right_child = new tree_node;
        this_node->right_child->data = *(data_formal + );
        return;
    }
    int level;
    for (level = ; level < ; ++level)
    {
        if (listof2[level]- >= node_num) break;
    }
    if (listof2[level] *  /  -  >= node_num)
    {
        this_node = new tree_node;
        this_node->data = *(data_formal + node_num - listof2[level] / );
        find_insert_node(this_node->left_child, node_num - listof2[level] / , data_formal);
        find_insert_node(this_node->right_child, listof2[level] /  - , data_formal + node_num - listof2[level] /  + );
    }
    else
    {
        this_node = new tree_node;
        this_node->data = *(data_formal + listof2[level] /  - );
        find_insert_node(this_node->left_child, listof2[level] /  - , data_formal);
        find_insert_node(this_node->right_child, node_num - listof2[level] / , data_formal + listof2[level] / );
    }
}

queue<int> data_save;
queue<tree_node*> temp_node;

void level_order()
{
    if (temp_node.empty()) return;
    tree_node* this_node = temp_node.front();
    data_save.push(this_node->data);
    temp_node.pop();
    if (this_node->left_child) temp_node.push(this_node->left_child);
    if (this_node->right_child) temp_node.push(this_node->right_child);
    level_order();
}

int main()
{
    int num = ; cin >> num;
    int data_formal[] = { , , , , , , , , ,  };
    for (int i = ; i < num; ++i) cin >> data_formal[i];
    sort(data_formal, data_formal + num);
    tree_node* root_node = NULL;
    find_insert_node(root_node, num, data_formal);
    temp_node.push(root_node);
    level_order();
    for (int i = ; i < num; ++i)
    {
        cout << data_save.front();
        data_save.pop();
        if (i != num - ) cout << " ";
    }
    getchar(); getchar();
    return ;
}
           

這個代碼可以AC，但是稍有不慎就會出錯，很麻煩。

這個大神的解法很美，分析以後發現寫出這樣的代碼需要深厚的數學和程式設計功底。

#include <cstdio>  
    #include <cstdlib>  


    const int maxx = ;  
    int node[maxx];  
    int tree[maxx];  
    int pos,n;  

    int cmp(const void *a,const void *b){  
        int *pa = (int *)a;  
        int *pb = (int *)b;  
        return *pa-*pb;  
    }  //用于排序

    void build(int root){  
        if(root>n)return;  
        int lson = root<<,rson = (root<<)+;  
        build(lson);  
        tree[root] = node[pos++];  
        build(rson);  
    }  

    void print(int *a,int n){  
        int i;  
        for(i=;i<n;++i){  
            printf("%d ",a[i]);  
        }  
        printf("\n");  
    }  //調試代碼

    int main()  
    {  
        int i;  
        scanf("%d",&n);  
        for(i=;i<n;++i){  
            scanf("%d",&node[i]);  
        }  

        qsort(node,n,sizeof(int),cmp);  

    //  print(node,n);  

        pos = ;  
        build();  

        printf("%d",tree[]);  
        for(i=;i<=n;++i){  
            printf(" %d",tree[i]);  
        }  
        printf("\n");  
        return ;  
    }  
           

仔細分析代碼，事實上他的代碼将建構二叉樹和層序排列二叉樹在短短6行内完成了

void build(int root){  //第一次調用時：root=1，pos指向已經升序排列的數組的第一個元素
        if(root>n)return;  
        int lson = root<<,rson = (root<<)+;  //用左移乘以2
        build(lson);  
        tree[root] = node[pos++];  
        build(rson);  
    }  
           

這篇文章提到了完全二叉樹的五個基本性質，其中之一是：

如果有一顆有n個節點的完全二叉樹的節點按層次序編号，對任一層的節點i（1<=i<=n）有

1）如果i=1，則節點是二叉樹的根，無雙親，如果i>1，則其雙親節點為[i/2]，向下取整

2）如果2i>n那麼節點i沒有左孩子，否則其左孩子為2i

3）如果2i+1>n那麼節點沒有右孩子，否則右孩子為2i+1

通過這個性質，我們可以定位目前處理的節點在數組中應該儲存的位置。

按照中序二叉樹的周遊順序，它會從小到大依次周遊二叉查找樹的節點。

知道了這兩個資訊，我們就可以往數組裡一個一個填。

即使看懂了他的代碼，我大概也無法短時間内寫出這麼美的代碼吧。