ホームページ  >  記事  >  完全な二分木の葉ノードの数

完全な二分木の葉ノードの数

步履不停
步履不停オリジナル
2019-06-20 13:07:1417764ブラウズ

完全な二分木の葉ノードの数

n 個のノードを持つ完全なバイナリ ツリー、リーフ ノードの数 n0 は次のとおりです: n/2 切り上げ、または (n 1)/2 切り捨て 全体

拡張情報:

完全なバイナリ ツリー

完全なバイナリ ツリーは非常に効率的なデータ構造です。完全なバイナリ ツリーは完全なバイナリで構成されます。木が引き出した。深さ K でノードが n のバイナリ ツリーの場合、各ノードが深さ K の完全なバイナリ ツリー内の 1 から n までの番号が付けられたノードと 1 対 1 で対応する場合にのみ、完全なバイナリ ツリーと呼ばれます。

定義

二分木の深さが h の場合、h 番目の層を除くすべてのその他の階層 (1 ~h-1) ノード数が最大数に達し、h 階層のすべてのノードが連続して最左側に集中しており、完全な二分木になります。

完全なバイナリ ツリーは、完全なバイナリ ツリーから派生します。深さ K でノードが n のバイナリ ツリーの場合、各ノードが深さ K の完全なバイナリ ツリー内の 1 から n までの番号が付けられたノードと 1 対 1 で対応する場合にのみ、完全なバイナリ ツリーと呼ばれます。

(1) すべてのリーフ ノードは、k 番目の層または k-l 層 (最大の 2 つの層) に表示されます。

(2) 任意のノードについて、その右のサブツリーの最大レベルはL の場合、その左側のサブツリーの最大レベルは L または L l です。

バイナリ ツリーでは、下位 2 レベルのノードの次数は最大でも 2 未満であり、最下位レベルのノードはすべてレベルの左端の位置に集中しており、完全二分木となる 最下位階層のノードが階層の左端に集中し、最終階層で右側のノードが多数欠落した二分木は完全二分木となる。

よくある質問に関連する技術的な記事については、FAQ 列を参照してください。もっと!

以上が完全な二分木の葉ノードの数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。