ユニバルサブツリーのカウント-フォローアップ

Nov 24 2020

このコードは、改善に関するアドバイスを求めた実装の改訂版です。ここでの元の投稿:ユニバルサブツリーのカウントクレジット:[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");

}

回答

1 TobySpeight Nov 25 2020 at 09:19

よくできました-受け取ったレビューから改善が見られるのは素晴らしいことです。

計算&&ではビット単位&ではなく論理を使用することをお勧めしr &node->value == parent->valueます。結果は同じであるはずですが、プログラマーはブール値を持つ論理演算子を見ることを期待しています。

の計算は、左側がfalseの場合でも、右側の副作用を評価する必要があるため、そのままでは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);
}