유니 벌 하위 트리 계산-후속 조치

Question

이 코드는 개선에 대한 조언을 요청한 수정 된 버전의 구현입니다. 원본 게시물 : 유니 벌 하위 트리 계산 출처 : [Deduplicator], [Reinderien], [Toby Speight], [chux].

수정 된 버전은 다음 변경 사항에 적용되었습니다.

1. insertRight(), insertLeft()함수를 createNode함수에 병합
2. 사용 후 무료 자원
3. const참조 된 메모리 주소 값이 변경되지 않은 경우 사용 됩니다.
4. isTreeUniv()재귀 버전으로 수정
5. 글로벌을 제거하다

수정 된 코드 :

#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

잘하셨습니다. 여러분이받은 리뷰에서 개선 된 것을 보게되어 기쁩니다.

계산에서 &&비트보다는 논리를 사용하는 것이 좋습니다 . 결과는 동일해야하지만 프로그래머는 부울 값이있는 논리 연산자를 볼 것으로 예상합니다.&r &node->value == parent->value

의 계산은 r있는 그대로 사용할 수 없습니다 &&. 왜냐하면 왼쪽이 거짓 인 경우에도 오른쪽은 부작용에 대해 평가 될 필요가 없기 때문입니다. 미래의 메인테이너가 "올바른"하지 않는, 그래서 나는, 별도의 표현으로 다시 작성 줄 &에 &&:

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;

로 시작하는 식별자 is는 표준 라이브러리 확장 용으로 예약되어 있으므로 isUnivSubTimpl특히 외부 연결이 있으므로 이름을 변경하는 것이 좋습니다.

왜 나에게 분명하지 않다 freeTree()다시 발생 bool, 그것은 오직 반환 등 true.

트리 구축은

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