6

私は二分木クラスを書いていますが、木のレベルでノードの数を数える必要がある levelCount メソッドに行き詰まっています。クラスとメソッドは次のようになります。

public class ConsTree<T> extends BinaryTree<T>
{
   BinaryTree<T> left;
   BinaryTree<T> right;
   T data;

   public int levelCount(int level) 
   {
   }
}

したがって、各ツリーには左側にツリーがあり、右側にツリーがあり、データがあるという考え方です。抽象クラス binarytree とサブクラス ConsTree および EmptyTree があります。

そのレベルに到達したら、幅優先検索を使用してノードの数をカウントする必要があると思いますが、開始方法に行き詰まっています。ここでのガイダンスは役に立ちます。必要なその他の情報を提供できます。

4

1 に答える 1

9

これが一般的なアプローチです。

通常どおり (深さ優先、順序どおり) ツリーをトラバースしますが、次のような疑似コードを使用して、目的のレベルと実際のレベルも渡すだけです。

def getCountAtLevel (node, curr, desired):
    # If this node doesn't exist, must be zero.
    if node == NULL: return 0

    # If this node is at desired level, must be one.
    if curr == desired: return 1

    # Otherwise sum of nodes at that level in left and right sub-trees.
    return getCountAtLevel (node.left,  curr+1, desired) +
           getCountAtLevel (node.right, curr+1, desired)

#######################################################################
# Get number of nodes at level 7 (root is level 0).
nodesAtLevel7 = getCountAtLevel (rootNode, 0, 7)

目的のレベルに到達すると、その下のすべてを無視できるため、実際にはツリー全体をトラバースするわけではありません。これが実際に動作していることを示す完全な C プログラムを次に示します。

#include <stdio.h>

typedef struct _sNode { struct _sNode *left, *right; } tNode;

// Node naming uses (t)op, (l)eft, and (r)ight.
tNode TLLL = {NULL,  NULL    }; // level 3
tNode TLLR = {NULL,  NULL    };
tNode TRLL = {NULL,  NULL    };
tNode TRLR = {NULL,  NULL    };
tNode TRRR = {NULL,  NULL    };
tNode TLL  = {&TLLL, &TLLR   }; // level 2
tNode TRL  = {&TRLL, &TRLR   };
tNode TRR  = {NULL,  &TRRR   };
tNode TL   = {&TLL,  NULL    }; // level 1
tNode TR   = {&TRL,  &TRR    };
tNode T    = {&TL,   &TR     }; // level 0 (root)

static int getCAL (tNode *node, int curr, int desired) {
    if (node == NULL) return 0;
    if (curr == desired) return 1;
    return getCAL (node->left,  curr+1, desired) +
           getCAL (node->right, curr+1, desired);
}

int main (void) {
    for (int i = 0; i < 5; i++) {
        int count = getCAL(&T, 0, i);
        printf ("Level %d has %d node%s\n", i, count, (count == 1) ? "" : "s");
    }
    return 0;
}

次の形式のツリーを構築します (ここで、T上を意味Lし、左の枝とR右の枝を意味します)。

            ______T______               (1 node)
           /             \
         TL               TR            (2 nodes)
        /                /  \
     TLL              TRL    TRR        (3 nodes)
    /   \            /   \      \
TLLL     TLLR    TRLL     TRLR   TRRR   (5 nodes)

                                        (0 nodes)

そのコードをコンパイルして実行すると、各レベルで正しいノード数が得られることがわかります。

Level 0 has 1 node
Level 1 has 2 nodes
Level 2 has 3 nodes
Level 3 has 5 nodes
Level 4 has 0 nodes
于 2012-10-14T06:49:05.187 に答える