Đếm số cây con đơn lẻ - Theo dõi

Question

Mã này là phiên bản sửa đổi của việc triển khai yêu cầu lời khuyên về cải tiến. Bài gốc ở đây: Đếm số cây con duy nhất Tín dụng cho: [Deduplicator], [Reinderien], [Toby Speight], [chux].

Phiên bản sửa đổi đã được áp dụng những thay đổi sau:

1. Hợp nhất insertRight(), insertLeft()hàm thành createNodehàm
2. tài nguyên miễn phí sau khi sử dụng
3. được sử dụng constnếu giá trị địa chỉ bộ nhớ được tham chiếu không bị thay đổi.
4. sửa isTreeUniv()thành phiên bản đệ quy
5. thoát khỏi hình cầu

Đã sửa đổi mã:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct stTree
{
    struct stTree *left;
    struct stTree *right;
    int value;
} stTree;

stTree* createNode(int value, stTree *leftNode, stTree *rightNode)
{
    stTree *node = malloc(sizeof *node);
    if (!node) abort();

    node->left = leftNode;
    node->right = rightNode;
    node->value = value;

    return node;
}

bool isUnivSubTimpl(const stTree *node, const stTree *parent, size_t *count)
{
    if (!node) return 1;    //node without child count as unival subT

    bool r = isUnivSubTimpl(node->left, node, count) &isUnivSubTimpl(node->right, node, count);
    *count += r;

    return (r &node->value == parent->value);
}

size_t countUnivSubT(const stTree *node)
{
    size_t count = 0;
    isUnivSubTimpl(node, node, &count);
    return count;
}

static stTree* findBottomLeft(stTree *node)
{
    while (node->left)
        node = node->left;
    return node;
}

bool freeTree(stTree *node)
{
    if (!node) return true;
    stTree *bottomLeft = findBottomLeft(node);

    while (node)
    {
        if (node->right)
        {
            bottomLeft->left = node->right;
            bottomLeft = findBottomLeft(bottomLeft);
        }

        stTree *old = node;
        node = node->left;
        free(old);
    }
        return true;
}

int main(void)
{
    //build a tree
    stTree *rootNode =
        createNode(0,
            createNode(1, NULL, NULL),
            createNode(0,
                createNode(1,
                    createNode(1, NULL, NULL),
                    createNode(1, NULL, NULL)
               ),
                createNode(0, NULL, NULL)));

    printf("total universal subree: %u\n", countUnivSubT(rootNode));
    if (freeTree(rootNode))
        printf("memory released\n");

}

Answer 1

Làm tốt lắm - thật vui khi thấy những cải tiến từ các bài đánh giá bạn nhận được.

Tôi khuyên bạn nên sử dụng logic &&thay vì bitwise &trong tính toán r &node->value == parent->value. Các kết quả phải giống nhau, nhưng các lập trình viên mong đợi thấy các toán tử logic với các giá trị boolean.

Việc tính toán rkhông thể được sử dụng &&như hiện nay, bởi vì phía bên phải cần được đánh giá về các tác dụng phụ của nó, ngay cả khi phía bên trái là sai. Tôi coi việc viết lại là các biểu thức riêng biệt, vì vậy người bảo trì trong tương lai không "sửa" &thành &&:

bool l_un = isUnivSubTimpl(node->left, node, count);  /* updates *count */
bool r_un = isUnivSubTimpl(node->right, node, count); /* updates *count */
bool r = l_un && r_un;

Các số nhận dạng bắt đầu bằng isđược dành riêng cho tiện ích mở rộng Thư viện Chuẩn, vì vậy tôi khuyên bạn nên thay đổi tên isUnivSubTimpl, đặc biệt vì nó có liên kết bên ngoài.

Tôi không rõ tại sao freeTree()trả về a bool, vì nó chỉ trả về true.

Việc xây dựng cây có thể được đơn giản hóa một chút với

stTree *createLeafNode(int value)
{
    return createNode(value, NULL, NULL);
}