二分木でノードを数えることができません。下の図に示すように、開始するのは非常に単純なツリーです。
(5)
(3)-------^-------(7)
(2)---^---(6) ^-------(9)
(5)---^---(8)
8 つのノードを追加したので、8 つのはずです。しかし、コードを実行すると、7 つのノードがカウントされます。すべての左ノードと右ノードをカウントし、ルートをカウントしていないと思いますが、ノード数を 1 に設定して、左右のノードをカウントする前にルートをカウントします。以下のコードを参照してください
private int getNumNodes(Node<E> root){
numNodes = 1; // starts by counting the root
// counts the left nodes
if(root.left != null){
numNodes += getNumNodes(root.getLeft());
}
// counts the right nodes
if(root.right != null){
numNodes += getNumNodes(root.getRight());
}
return numNodes;
}
public int getNumNodes(){
return root == null ? 0 : getNumNodes(root);
}
どこかでカウントが欠落しているに違いありませんが、どこで発生しているのかわかりません。皆さん、私を助けてくれませんか。ありがとう。