ホームページ > バックエンド開発 > C++ > パスを満た​​さず、k 以上のノードを削除する C++ プログラム

パスを満た​​さず、k 以上のノードを削除する C++ プログラム

PHPz
リリース: 2023-09-14 11:25:07
転載
963 人が閲覧しました

パスを満た​​さず、k 以上のノードを削除する C++ プログラム

この問題には、ルート ノードからリーフ ノードまでのパスが完全に定義されているバイナリ ツリーがあります。ルート ノードからリーフ ノードまでのすべてのノードの合計は、定数値 k 以上である必要があります。したがって、ツリー内の残りのパスが k より大きくなるように、パス内の合計が k より小さいノードをすべて削除する必要があります。ここで覚えておくべき重要なことは、ノードは多くのパスの一部である可能性があるため、そのようなノードは、そのノードにつながるすべてのパスの合計が k 未満の場合にのみ削除されるということです。

ルート ノードからリーフ ノードまでの合計を計算できます。ノードへの再帰呼び出しが完了して制御が戻ると、左右のパスの合計が k

150 K と次のようなツリーがあるとします -

リーリー

パス root->left->left の合計が 10 20 5、つまり 25 で 150 未満であることがわかった場合は、それを枝刈りして 5 を削除する必要があります。その後、10→30→40と評価してみましょう。 150未満なので40を削除します。

ここで、別のパス 10->20->35->50 が表示されます。115 の合計は 150 未満なので、50 を削除します。残りのパスは

です。 リーリー

すべてのパスの合計は 150 を超えているため、これ以上プルーニングする必要はありません。

###例###

以下は、どのパスにも存在せず、合計が任意の定数値 k -

以上であるノードを削除する方法を示す C プログラムです。 リーリー ###出力### リーリー

完全に剪定された木 -

リーリー ###結論は###

ご覧のとおり、最初の観察の後、再帰関数が各呼び出しから返されるときにそのノードの合計を計算することで、DFS を適用してノードを削除できます。全体として、これは観察と方法論に関する単純な問題です。

以上がパスを満た​​さず、k 以上のノードを削除する C++ プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ソース:tutorialspoint.com
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート