[数据结构与算法]树形结构基础&字典树

A - Binary Tree Traversals

?题意：输入一个二叉树的先序遍历和中序遍历的结果序列，求这棵二叉树后序遍历的序列。

思路：这道题是为了让我们熟悉二叉树的结构基础同时掌握树上搜索的技巧。根据先（中）序遍历的概念，可以知道先序的第一个数就是这棵树的root，然后根据中序序列可知，root点左边的数构成以这个root点为根节点的左子树，同理，右边的树构成其右子树。这里有一种递归的思想，然后再把左（右）子树当做单独的一棵树，再来寻找。

#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long ll;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
using namespace std;
ll n;

typedef struct node{
    int v;
    node *l, *r;
}node, *pnode;//这是建立节点的标配

pnode create( int n, int *pre, int *ino ){// n：还要建立的节点树，pre：先序来找root，ino：
    if( !n ){
        return NULL;
    }
    pnode root;
    int *p;
    root = ( pnode )malloc( sizeof( node ) );
    root -> v = pre[0];
    for( p = ino;  *p != '\0'; p++ ){
        if( pre[0] == *p ){
            break;
        }
    }
    int cnt = p - ino;
    root -> l = create( cnt, pre + 1, ino );
    root -> r = create( n - cnt - 1, pre + 1 + cnt, p + 1 );
    return root;
}
void post( pnode root , int len ){
    if( root == NULL ){
        return ;
    }
    post( root -> l, n + 1 );
    post( root -> r, n + 1 );
    if( len == 0 ){
        cout << root -> v << endl;
    }
    else{
        cout << root -> v << " ";
    }
}

int main()
{
    ios :: sync_with_stdio( false );
    cin.tie( NULL );
    while( cin >> n ){
        int pre[N], ino[N];
        for( int i = 0; i < n; i++ ){
            cin >> pre[i];
        }
        for( int i = 0; i < n; i++ ){
            cin >> ino[i];
        }
        pnode root = create( n, pre, ino );
        //其实不管是哪种遍历方式，只要知道了整个树的root点，就可以遍历整个树。
        post( root, 0 );//后序遍历
    }
    return 0;
}

B - 统计难题

?题意：Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀)。输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串。注意:本题只有一组测试数据,处理到文件结束。对于每个提问,给出以该字符串为前缀的单词的数量。

思路：这道题是个典型的字典树模板题。具体见代码吧~

#include <iostream>
#include<cstdio>
#include <cstring>
#include <algorithm>

typedef long long ll;
const int N = 4e5 + 10;
const int INF = 0x3f3f3f3f;
using namespace std;
char s[11];
int tree[N][26], id, sum[N];

int to_num( char c ){
    return ( c - 'a' );
}

 void create( char *s ){
     int len = strlen(s);
     int pre = 0;
     for( int i = 0; i < len; i++ ){
         int nw = to_num( s[i] );
         if( !tree[pre][nw] ){
          //这其实相当于是映射，用二维数组来记录，pre就是前缀，nw就是要准备加上的内容
             tree[pre][nw] = ++id;// 如果还没有这个分支，就加上并且把这个分支节点做上标记
         }
         pre = tree[pre][nw];// 再在这个前缀的基础上再来建立儿子节点
         ++sum[pre];// 只要有了过这个前缀，我们就记录一次
     }
 }

int query( char *s ){
    int len = strlen(s);
    int pre = 0;
    for( int i = 0; i < len; i++ ){
        int nw = to_num( s[i] );
        if( !tree[pre][nw] ){
            return 0;
        }//如果没有找到，就说明可能根本就找不到这个节点了，可能是找完也可能是根本就没有这个节点
        pre = tree[pre][nw];// 不断往下寻找
    }
    return sum[pre];
}

int main()
{
    while( gets( s )  ){
    // 注意输入方式不要直接使用cin，不然程序会把所有的输入都当做第一部分
    // 使用头文件#include<cstdio>
    // 注意这个函数必须是gets( 地址 )，而且在acwing上运行不起
        if( !strlen(s) ){ 
    //用char形成的字符串要用这个函数 strlen( s )来计算字符串长度，以'\0'来作为结束符
            break;
        }
        create( s );
    }
    while( gets( s ) ){
        if( !strlen(s) ){
            break;
        }
        int ans = query( s );
        cout << ans << endl;

    }
    return 0;
}

C - Xor Sum

题意：输入长度为n的数组，q次询问，每次询问给一个数S，对于每个询问，输出一个正整数K，使得K与S异或值最大。

思路：要异或结果最大，很明显最好的结果就是要找一个数，让这个数尽量从高位开始的二进制数就和S相反，那么目标其实就已经确认了，为了加快查找效率完全可以使用字典树，只不过每个节点的分支最多有两个。其实这题和上面B题很相似的，也是建立映射关系，要学会变通。但是这道题妙在使用了二进制来取得每个二进制位，以及取反操作。我原来没用二进制运算，写了好多函数来分存储二进制串，二进制取反串，还要进行串的遍历……太麻烦了，人麻了，到底还是对二进制运算不熟悉……

#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long ll;
const int N = 1e5 + 10;
using namespace std;
ll t, n, m, tree[N * 32][2], id, sum[N *32];//根据create函数可知每个数字需要自己二进制长度
                                            //个结点，而题目中说每个数字最多32位

void create( ll num ){
    
    int pre = 0, nw;
    for( int i = 31; i > -1; i-- ){
        nw = ( num >> i ) & 1 ;
        if( !tree[pre][nw] ){
            tree[pre][nw] = ++id;//标号
        }
        pre = tree[pre][nw];
    }
    sum[pre] = num;//最后就是直接赋值
}

ll query( ll num  ){
    int pre = 0, nw;
    for( int i = 31; i > -1; i-- ){
        nw = ( num >> i ) & 1 ;//这是单独取数字单个二进制位的方法，妙啊！！！
        if( tree[pre][nw^1] ){
            pre = tree[pre][nw^1];
        }
        else{
            pre = tree[pre][nw];
        }
    }
    return sum[pre];
}

int main()
{
    ios :: sync_with_stdio( false );
    cin.tie( NULL );
    cin >> t;
    int y = 0;
    while( t-- ){
        memset( sum, 0, sizeof( sum ) );//注意有多次操作，注意清零
        memset( tree, 0, sizeof( tree ) );
        id = 0;
        cin >> n >> m;
        ll num;
        for( int i = 0; i < n; i++ ){
            cin >> num;
            create( num );//建立字典树
        }
        cout << "Case #" << ++y << ":\n";
        while( m-- ){
            cin >> num;
            ll ans = query( num );//查询
            cout << ans << endl;
        }
    }
    return 0;
}

取一个十进制数的各个二进制位数的板子:

    for( int i = 31; i > -1; i-- ){// i >= 0
        nw = ( num >> i ) & 1 ;
    }//若是32位 i == 31；64位 i == 63

/*
    二进制取反操作： num^1

*/

总结：

此次学习对于树这种数据结构更加了解了，加深了自己对专业知识的了解，回忆了以前学习的专业知识，同时切身通过敲代码深入了解，二叉树是竞赛中常用的数据结构、同时B题入门了字典树，C题练习了字典树，同时掌握了二进制的一些技巧，字典树的本质是映射。