6.3 树和二叉树

定义

二叉树的递归定义:二叉树要么为空,要么由根节点、左子树和右子树构成。左子树和右子树分别是一棵二叉树。
树和二叉树类似,区别在于每个结点不一定只有两棵子树。
无论是树还是二叉树,每个非根结点都有一个父亲,也称作父结点。

二叉树的编号

例题:小球下落(UVa 679)

有一颗二叉树,最大深度为D,且所有叶子的深度都相同。所有节点从上到下从左到右依次编号为1、2、3……2^D-1。在结点1处放上一个小球,每一个结点都有一个开关,初始为关闭状态。小球往下落的过程中,每遇到一个开关,开关的状态就会改变。小球遇到开关时,如果关闭则往左走,如果打开则往右走。

模拟程序

所以可以写出如下的模拟程序:

#include<cstdio>
#include<cstring>
const int maxd = 20;
int s[i<<maxd];
int main(){
    int D, I;
    while (scanf("%d%d", &D, &I) == 2){
        memset(s, 0, sizeof(s));
        int k, n = (1 << D) - 1;
        for(int i = 0; i < I; i ++){
            k = 1;
            for(;;){
                s[k] = !s[k];
                k = s[k] ? k*2 : k*2+1;
                if(k > n) break;
            }
        }
    printf("%d\n", k/2);
    }
return 0;
}

这个模拟程序简单易懂,但是缺点在于运算量太大,导致时间和空间复杂度都不可控。

分析改良

再次观察问题,发现每个小球都会落在根节点上,因此前两个小球必然一个在左子树,一个在右子树。以此类推我们只看小球的编号就能判断小球的落点。即:_当小球编号I是奇数时,它是往左走的第(I+1)/2个小球,当I是偶数时,它是往右走的第I/2个小球。

while(scanf("%d%d, &D, &I) == 2)) {
    int k = 1;
    for(int i = 0 ; i < D; i++) {
        if(I%2) { k = k * 2; I = (I+1)/2; }
        else { k = k*2; I /= 2; }
    }
    printf("%d\n", k);
}

这样程序的运算量就和小球编号无关了,并且节省了一个巨大的数组空间。

二叉树的层次遍历

例题:树的层次遍历(UVa 122)

输入一颗二叉树,你的任务是从上到下从左到右输出各个节点的值。每个节点都按照从根节点到它的移动序列给出(L表示左,R表示右)。在输入中,每个结点的左括号和右括号之间没有空格,相邻结点之间用一个空格隔开。每棵树的输入用一对空括号“()”结束。
如果从根到某一个叶结点的路径上有的结点没有在输出中给出,或者给出超过了一次,应当输出-1。结点个数不超过256。

题意分析

这道题不能通过数组来保存每一个结点的编号,因为编号的量太大。所以需要使用动态结构来建立结点,组织成树。

二叉树遍历程序

char s[maxn];
bool read_input(){ // 读入
    failed = false;
    bool = newnode();
    for(;;){
        if(scanf("%s", s) 1= 1) return false;
        if(!strcmp(s, "()")) break;
        int v;
        sscanf(&s[1], "%d", &v);
        addnode(v. strchr(s, ',')+1);
    }
    return true;
}
struct Node{ // 结点类型
    bool have_value;
    int v;
    Node *left, *right;
    Node():have_value(false), left(NULL), right(NULL){}
};
Node* root; // 根结点
Node* newnode(){ // 新建结点空间
    return new Node();
}
void addnode(int v, char* s){
    int n = strlen(s);
    Node* u = root;
    for(int i = 0; i< n; i++)
        if(s[i] == 'L'){
            if(u->left == NULL) u->left = newnode();
            u = u->left;
        }
        else if(s[i] == 'R'){
            if(u->right == NULL) u->right = newnode();
            u = u->right;
        }
    if(u->heve_value) failed = true;
    u->v = v;
    u->have_value = ture;
}
// 输入和建树已经完成,接下来需要按照层次顺序遍历这棵树。此处使用一个队列来完成这个任务
// 初始时候只有一个根结点,然后每次取出一个结点,就把它的左右子结点放进队列
bool bfs(vector<int>& ans){
    queue<Node*> q;
    ans.clear();
    q.push(root);
    while(!q.empty()){
        Node* u = q.front(); q.pop();
        if(!u->have_value) return false;
        ans.push_back(u->v);
        if(u->left != NULL) q.push(u->left);
        if(u->right != NULL) q.push(u->right);
    }
    return true;
}
// 这样的遍历方法称为BFS
// 这里有个小问题:在输入一组新数据时,没有释放上一课二叉树所申请的内存空间
// 所以我们需要释放二叉树
void remove_tree(Node* u){
    if(u == NULL) return;
    remove_tree(u->left);
    remove_tree(u->right);
    delete u;
}

二叉树非指针建构

二叉树也可以不使用指针的方法来进行建构。
首先还是给每个结点编号,但不是按照从上到下从左到右的顺序,而是按照结点是生成顺序。用计数器cnt表示已经存在的结点编号的最大值,因此newnode函数需要改成这样:

const int root = 1;
vold newtree(){ left[root] = right[root] = 0; have_value[root] = false; cnt = root; }
int newnode() { int u  = ++cnt; left[u] = right[u] = 0; have_value[root] = false; return u; }

这里的newtree是用来代替上面的remove_tree(root)root = newnode()两条语句的:由于没有了动态内存的申请和释放,只需要重置结点计数器和根结点的左右子树了。
接下来,把所有的Node*类型改成int类型然后把结点结构中的成员变量改成全局变量,这样除了字符数组之外就没有任何指针了。
用数组来实现二叉树比结构体+指针的方法略慢,但是编程简单,容易调试。
有时候newnode函数也会写成:

Node* newnode(){
    Node* u = &node[++cnt]; u->left = u->right = NULL;
    u->have_value = false; 
    return u;
}

这样写释放内存就会很不方便,如果反复新建、删除结点,cnt就会一直增加,但是用完的内存却无法重用。解决方案是写一个简单的内存池,具体来说就是维护一个空闲列表,在初始的时候吧上述node数组中所有的元素的指针放到该列表中。

queue<Node*> freenodes;
Node node[maxn];
void init(){
    for(int i = 0; i < maxn; i++)
        freenodes.push(&node[i]);
}
Node* newnode(){
    Node* u = freenodes.front();
    u->left = u->right = NULL;
    u->have_value = false;
    freenodes.pop();
    return u;
}
voide deletenode(Node* u){
    freenodes.push(u);
}

二叉树的递归遍历

定义

  • 先序 PreOrder(T) = T的根结点+PreOrder(T的左子树)+PreOrder(T的右子树)
  • 中序 InOrder(T) = InOrder(T的左子树)+T的根结点+InOrder(T的右子树)
  • 后序 PostOrder(T) = PostOrder(T的左子树)+PostOrder(T的右子树)+T的根结点

例题:树(UVa 548)

给出一棵点带权(权值各不相同)的二叉树的中序和后序遍历,找一个叶子使得它到根的路径上的权和最小。如果有多解,该叶子本身的权应该尽量小。输入中每两行表示一棵树,第一行为中序遍历,第二行为后序遍历。

题解代码

#include<iostream>
#include<string>
#include<sstream>
#include<algorithm>
using namespace std;

// 因为各个结点的权值各不相同企鹅都是正整数,所以直接用权值作为编号
const int maxv = 10000 + 10;
int in_order[maxv], post_order[maxv], lch[maxv], rch[maxv];
int n;
bool read_list(int *a){
    string line;
    if(!getline(cin, line)) retu;rn false;
    stringstream ss(line);
    n = 0;
    int x;
    while(ss >> x) a[n++] = x;
    return n > 0;
}

// 把in_order[L1..R1]和post_order[L2..R2]建成一棵二叉树,返回树根
int build(int L1, int R1, int L2, int R2){
    if(L1 > R1) return 0;
    int root = post_order[R2];
    int p = L1;
    while(in_order[p] != root) p++;
    int cnt = p-L1;
    lch[root] = build(L1, p-1, L2, L2+cnt-1);
    rch[root] = build(p+1, R1, L2+cnt, R2-1);
    return root;
}

int best, best_sum;
void dfs(int u, int sum){
    sum += u;
    if(!lch[u] && !rch[u])
        if(sum < best_sum || (sum == best_sum && u < best)) {
            best = u;
            best_sum = sum;
        }
    if(lch[u]) dfs(lch[u], sum);
    if(rch[u]) dfs(rch[u], sum);
}

int main(){
    while(read_list(in_order)){
        read_list(post_order);
        build(0, n-1, 0, n-1);
        dfs(post_order[n-1], 0);
        cout << best << endl;
    }
    return 0;
}

例题:天平(UVA839)

输入了一个树状天平,根据力矩相等原则判断是否平衡。所谓力矩相等就是W1D1=W2D2,其中W1W2分别是左右两边砝码的重量,D为距离。
采用递归(先序)方式输入:每个天平格式为W1D1W2D2,W为零时表示该砝码实际是一个子天平,接下来会表述这个子天平。当W1W2都为零时,会先描述左子天平,后描述右子天平。

分析

本题的输入就采用了递归的方式,所以可以很自然地用递归的方式来读入。
事实上,在输入的过程当中就能完成判断。由于使用了引用传值,所以代码十分精简。

代码

#include<iostream>
using namespace std;
// 输入一个子天平,返回子天平是否平衡,参数W修改为子天平的总重量
bool solve(int& W){
    int W1, D1, W2, D2;
    bool b1 =true, b2 =true;
    cin >> W1 >> D1 >> W2 >> D2;
    if(!W1) b1 = solve(W1);
    if(!W2) b2 = solve(W2);
    W = W1 + W2;
    return b1 && b2 && (W1 * D1 == W2 * D2);
}

int main(){
    int T, W;
    cin >> T;
    while(T--){
        if(solve(W)) cout << "YES" << endl;
        else cout << "NO" << endl;
        if(T) cout << endl;
    }
    return 0;
}

下落的树叶(UVa 699)

给一棵二叉树,每个结点都有一个水平位置:左子节点在它左边一个单位,右子节点在右边一个单位。从左向右输出每个水平位置的所有结点的权值之和。用-1表示空树。

#include<iostream>
using namespace std;
const int maxn = 10000+10;
int sum[maxn];

// 输入并且统计一棵子树,树根水平位置为p
void build(int p){
    int v;
    cin >> v;
    if(v == -1) return;
    sum[p] += v;
    build(p - 1);
    build(p + 1);
}

// 边读入边统计
bool init(){
    int v;
    cin >> v;
    if(v == -1)return false;
    memset(sum, 0, sizeof(sum));
    int pos = maxn/2;
    sum[pos] = v;
    build(pos - 1);
    build(pos + 1);
}

int main(){
    int kase = 0;
    while(init()){
        int p =0;
        while(sum[p] == 0) p++; // 找最左边的叶子
        cout << "Case " << ++kase << ":\n" << sum[p++]; // 避免行末多余空格
        while(sum[p] != 0) cout << " " << sum[p++];
        cout << "\n\n";
    }
    return 0;
}

非二叉树

例题:四分树(UVa 297)

可以用四分树来表示一个黑白图像,方法是用根结点表示整幅图像,然后把行列各分成两等分,按照图中的方式编号就,从左到右对应4个子结点。如果某个子结点对应的区域全黑或者全白,则直接用一个黑结点或者白结点表示;如果既有黑又有白,则用一个灰结点表示,并且为这个区域递归建树。
给出两棵四分树的先序遍历,求两者合并之后黑色像素的个数。p表示中间结点,f表示黑色,e表示白色。

题解代码

#include<cstdio>
#include<cstring>

const int len = 32;
const int maxn = 1024 + 10;
char s[maxn];
int buf[len][len], cnt;

// 把字符串s[p..]导出到以(r,c)为左上角,边长为w的缓冲区中
// 2 1
// 3 4
void draw(const char* s, int& p, int r, int c, int w){
    char ch = s[p++];
    if(cj == 'p'){
        draw(s, p, r, c+w/2, w/2); // 1
        draw(s, p, r, c, w/2); // 2
        draw(s, p, r+w/2, c, w/2); // 3
        draw(s, p, r+w/2, c+w/2, w/2); // 4
    }
    else if(ch == 'f'){
        for(int i = r; i < r+w; i++)
            for(int j = c; j < c+w; j++)
                if(buf[i][j] == 0){
                    buf[i][j]= 1;
                    cnt++
                }
    }        
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        memset(buf, 0, sizeof(buf));
        cnt = 0;
        for(int i = 0; i< 2; i++){
            scanf("%s", s);
            int p = 0;
            draw(s, p, 0, 0, len);
        }
        printf("There are %d black pixels.\n", cnt);
    }
    return 0;
}