c - 一棵二叉树中有多少个节点只有一个子节点？

Question

我想计算一棵二叉树中有多少个节点只有一个子节点。我不知道这是否可以。我也不知道是否必须使用后序之类的树搜索。

size_t tree_one_child(const tree_t* t){
if(!t || number_children(t)==0){
    return 0;
}
if(number_children(t)==1){
    return 1 + tree_one_child(t->left) + tree_one_child(t->right);
}
else{
    return tree_one_child(t->left) + tree_one_child(t->right);
}



size_t number_children(const tree_t* t){
int count = 0;
if(t->left != null ) count++;
if(t->right != null) count++;       
return count;
}

Answer 1

对代码的一些评论:

您可以将 if(!t || number_children(t)==0) 简化为 if(!t)。

为了避免重复，您应该将子级的递归计算保存在变量中:

size_t tree_one_child(const tree_t* t){
    if(!t)
        return 0;

    size_t ret = tree_one_child(t->left) + tree_one_child(t->right);
    if (number_children(t) == 1)
        ret++;
    return ret;
}

除非您在其他地方使用number_children，否则您可以使用它:

size_t one_child(const tree_t* t){
    return !t->left != !t->right;
}

表达式!a != !b是一种执行逻辑异或的方法，这正是您想要的。它使代码更加简洁。

size_t tree_one_child(const tree_t* t){
    if(!t)
        return 0;

    size_t ret = tree_one_child(t->left) + tree_one_child(t->right);
    if (one_child(t))
        ret++;
    return ret;
}

为了让这段代码更短，你可以这样做:

size_t tree_one_child(const tree_t* t){
    if(!t)
        return 0;
    return one_child(t) + tree_one_child(t->left) + tree_one_child(t->right);
}

有些人可能会认为这种 id 做法不好，因为 bool 值之间的加法(我知道 one_child 技术上返回 size_t，但它显然意味着被视为 true/false)并不真正有效合理。它恰好起作用，因为它在 true 时返回 1，在 false 时返回 0。

你的代码能工作吗？

据我所知，它似乎完成了这项工作，而且我看不到任何会产生错误结果或做任何坏事的情况。

关于如何说服自己的建议是编写测试。我将提供如何操作的快速指南。

首先，创建一个函数create_tree( .. )，该函数根据其参数创建一棵树。也许您可以有一个只接受 char* 的函数，并对该字符串进行一些魔法来生成一棵树。这样你就可以进行一些像这样的测试:

void test(char * s, int expected_output) {
    tree_t * t = create_tree(s)  
    if(tree_one_child(t) == expected_output)
        printf("Test passed\n");
    else
        printf("   TEST FAILED");
    deallocate_tree(t);
}

test("1332", 3);
test("10423", 0);

注意 有相当标准化的方法可以做到这一点，但我想您已经明白了。找到一些方法来轻松测试您的代码并对其进行测试。