【解決方法】Cでバイナリツリーがいっぱいかどうかを確認するにはどうすればよいですか

プログラミングQA

2022.11.23

私のtypedef構造は、

typedef struct treenode{
    int data;
    struct treenode *left, *right;
} *binarytree;

is full のサブプログラムは、

boolean is_full(void) {
    binarytree temp;
    temp = (binarytree) malloc (sizeof(struct treenode));
     if (temp == NULL)
        return TRUE;
    else {
    free (temp);
        return FALSE;
    }
}

命令は言う、

完全なツリーを確認しています:
値渡しを使用する
treenode 構造体のサイズのメモリを割り当てることはできますか?

私が試したこと：

これはスタックプログラムを書くのと似ていると言われたので、スタックプログラムを編集してみましたが、命令があいまいであるため、これが正しいかどうかわかりません。

解決策 1

このようなクエリの場合、まず有効な条件を書き留めてから、それらの条件のコードを記述します。

クエリの場合、二分木が完全であるかどうかは、次の方法で判断できます。

– 二分木ノードが NULL の場合
– 二分木ノードに空の左右のサブツリーがある場合
– 二分木ノードに左右のサブツリーがある場合、それは定義上、完全な二分木の一部です。再帰的に、左と右のサブツリーもバイナリツリーであるかどうかを確認します。

右サブツリーと左サブツリーの他のすべての組み合わせでは、バイナリツリーは完全なバイナリツリーではありません。

したがって、上記の関数内のコーディングは次のようになります。

C++

/* This function tests if a binary tree is a full binary tree. */
bool isFullTree (struct Node* root)
{
    // 1. If empty tree
    if (root == NULL)
        return true;
 
    // 2. If leaf node
    if (root->left == NULL && root->right == NULL)
        return true;
 
    // 3. If both left and right are not NULL, and left & right subtrees
    // are full (checking recursively)
    if ((root->left) && (root->right))
        return (isFullTree(root->left) && isFullTree(root->right));
 
    // If none of the above condition is true
    return false;
}