3

私はバイナリ ツリーの初心者で、アルゴリズムの本を読んでいます。BST のさまざまなトラバーサル方法 (事前注文、事後注文など) について学びました。

誰かが BST をトラバースして、リーフ (子なし) であるノードの数をカウントする方法を説明してもらえますか?

どうもありがとう！

4

3 に答える 3

5

トラバーサル方法が異なれば、アルゴリズムも異なります (ただし、このような単純な問題の場合、すべての DFS バリアントは多かれ少なかれ同じです)。

タイプ のオブジェクトで構成される BST があると仮定しますNode。ノードには、ノードの子である型のleftとの2 つのフィールドがあります。子が存在しない場合、そのフィールドの値は です。ツリー全体は、 と呼ばれるルートへの参照によって参照されます。Java では:rightNodenullroot

class Node {
    public Node left;
    public Node right;
}

Node root;

DFS は再帰によって実装するのが最も簡単です: メソッドを定義します

int numberOfLeafs(Node node)

をルートとするサブツリーの葉の数を返しますnode。もちろん、numberOfLeafs(root)ツリー全体の葉の数が得られるはずです。

前述のように、ここで順序前、順序内、順序後のトラバーサルを区別するのは非常に不自然ですが、とにかくそうします。

DFS の事前注文: 最初に現在のノードを処理し、次に子を処理します

int numberOfLeafs(Node node) {
    int result = 0;
    if (node.left == null && node.right == null)
        result += 1;
    if (node.left != null)
        result += numberOfLeafs(node.left)
    if (node.right != null)
        result += numberOfLeafs(node.right)
    return result;
}

In-order DFS : 最初に左の子を処理し、次に現在のノードを処理し、次に右の子を処理します

int numberOfLeafs(Node node) {
    int result = 0;
    if (node.left != null)
        result += numberOfLeafs(node.left)
    if (node.left == null && node.right == null)
        result += 1;
    if (node.right != null)
        result += numberOfLeafs(node.right)
    return result;
}

ポストオーダー DFS : 最初に子を処理し、次に現在のノードを処理します

int numberOfLeafs(Node node) {
    int result = 0;
    if (node.left != null)
        result += numberOfLeafs(node.left)
    if (node.right != null)
        result += numberOfLeafs(node.right)
    if (node.left == null && node.right == null)
        result += 1;
    return result;
}

BFSの場合、通常、未訪問の頂点を追加するキューで単純なループを使用します。ここで、最後にノードを配置し、前部からノードQueueを配置できるクラスがあると仮定します。addtake

Queue queue = new Queue();
queue.add(root);
int numberOfLeafs = 0;
while (!queue.empty) {
    // take an unhandled node from the queue
    Node node = queue.take();

    if (node.left == null && node.right == null)
        numberOfLeafs += 1;
    if (node.left != null)
        queue.add(node.left);
    if (node.right != null)
        queue.add(node.right);
}
于 2013-10-24T15:07:35.227 に答える
0

これを試して

int countLeafNodes(BTNode node) { 
if (node == null)
        return 0;
    if (node.getLeftChild() == null && node.getRightChild() == null
            && node.getParent() != null)//this is a leaf, no left or right child
        return 1;
    else
        return countLeafNodes(node.getLeftChild())
                + countLeafNodes(node.getRightChild());
}

左右のサブツリーの葉ノードを再帰的にカウントし、合計カウントを返します

于 2013-10-26T05:53:01.333 に答える