现在有一颗二叉树,初始化的结点都是白色的,现在需要把若干个结点涂成黑色,使得不会出现父结点和它的两个非空孩子结点都是白色

用二进制表示二叉树的状态

1表示进行先序深度遍历,0表示叶子结点

例如

1100100的二叉树形态是

    #
   / \
  o   o

只要对根结点#进行着色一次操作就可以了

例如

1110010011000

对应的二叉树形态是

      o
    /  \
   #    o
  / \  /  \
 o   o o   NULL

这个只要对#结点进行着色就可以了

输入:一个长度小于等于100的二进制数

输出:最少操作次数


还有版本2的

每次对结点进行着色操作都会改变操作结点以及它的非空孩子结点的颜色,如果该结点原色是白色则会变成黑色,如果该结点原色是黑色,则会重新变回白色,并且初始化已经有若干个结点是黑色的,问最少多少次操作才能把所有结点变成黑色?

用w表示白色,b表示黑色,#表示叶子结点(已知结点小于等于100个)

输出最少操作次数

例如:

输入:ww##bb##w##
输出:3

这个问题看上去不是很难,但感觉比较好玩~我虽然找到方法,但不太会证明该方法的正确性,发出来看看怎么理解?~

[此贴子已经被作者于2018-6-9 16:03编辑过]

这么久了，还没人回帖，俺来抢沙发。作为抛砖引玉：

#include<iostream>
using namespace std;
static int i = -1;
//树的节点，包含节点及其颜色
 struct Treep
{
    char data;
    int color;
    Treep *right;
    Treep *left;
};
//转换字符到整型
int Change(char A) {
    int a;
        a = (int)(A) - 48;
        return a;
}
//求字符数组的长度
int Length(char *S) {
    int n = 0;
    while (*(S + n) != '\0') {
        n++;
    }
    return n;
}
//创建二叉树
Treep* Create(char *S) {
        Treep *T = new Treep;
        i = i + 1;
        if (i >= Length(S)) return NULL;
        T->color = Change(S[i]);
        T->data = S[i];
        if (Change(S[i]) == 0) {
            T->left = NULL;
            T->right = NULL;
            return T;
        }
        else {
            if (Change(S[i]) == 1) {
                T->left = Create(S);
                T->right = NULL;
            }
            if (Change(S[i]) == 2) {
                T->left = Create(S);
                T->right = Create(S);
            }
            return T;
        }
}
//判断两个数是否相等
bool judge2(int a, int b) {
    return a != b;
}
//判断三个数是否相等
bool judge3(int a, int b, int c) {
    return (a != c && b != c);
}
//对树进行染色
    void pre_order(Treep *&T,int *A){
        if (T != NULL)
        {
            A[T->color]++;
            if (T->left != NULL) {
                if (judge2(T->left->color, T->color) != true) {
                    T->left->color = (T->left->color + 1) % 3;
                    if (T->right != NULL) {
                        while (judge3(T->color, T->left->color, T->right->color) != true) {
                            T->right->color = (T->right->color + 1) % 3;
                        }
                    }
                }
            }
            else {
                if (T->right != NULL) {
                    if (judge2(T->color, T->right->color) != true) {
                        T->right->color = (T->right->color + 1) % 3;
                    }
                }

            }
            pre_order(T->left,A);//递归左子树
            pre_order(T->right,A);//递归右子树
        }
    }
    //求所用的最大及最小的数量
    void print(int *A) {
        int max = A[0], min = A[0];
        for (int i = 0; i < 3; i++) {
            if (max < A[i]) max = A[i];
            if (min > A[i])min = A[i];
        }
        cout << "白色最大数目为:" << max << endl;
        cout << "白色最小数目为:" << min << endl;
    }
    int main() {
        char S[20];
        cout << "请输入度数序列：";
        cin >> S;
        int A[3] = { 0 };
        Treep *root = Create(S);
        pre_order(root, A);
        print(A);
    }

你这个是第一问么,看上去好像是第二问的样子~第一问的创建就只有0和1两种情况而已,怎么会有三种情况?具体没有怎么看,或者到时要看看结果才能说些什么(想不到原本思路简单的东西用代码表示会这么复杂,不知道是本来就那么复杂还是只是没有找到简单的表述方式而已)

个人感觉第二个版本其实比较好弄一些,要是代码复杂说说思路也是可以的~

[此贴子已经被作者于2018-6-10 15:43编辑过]

算了,先结贴~

知道第二问一种状态只有唯一一个对应解,我,知道方法就不弄代码了,其实稍微比划一下就知道怎么弄了,不用多说~