二分木のデータ構造

あ 二分木のデータ構造 は、各ノードが最大 2 つの子 (左の子と右の子と呼ばれます) を持つ階層データ構造です。これは、挿入、削除、走査などのさまざまな操作によるデータの効率的な保存と取得のためにコンピュータサイエンスで一般的に使用されます。

二分木のデータ構造

導入：

二分木の性質
二分木の種類
バイナリーツリーの用途、メリット、デメリット
バイナリツリー (配列実装)
完全なバイナリツリー
完璧な二分木

バイナリツリーの基本操作:

その他の重要なバイナリツリートラバーサル:

スパイラル形式のレベル順序トラバーサル
逆レベル順序トラバーサル
バイナリツリーの BFS と DFS
再帰なしの順序ツリー走査
プレオーダー用のモリス・トラバーサル
反復的な事前注文トラバーサル
2 つのスタックを使用した反復事後探索
二分木の斜め走査
二分木の境界トラバーサル

二分木のデータ構造に関する簡単な問題:

Preorder から完全なバイナリツリーの深さを計算します
Inorder および Level の順序トラバーサルからツリーを構築する
指定されたバイナリツリーが SumTree かどうかを確認する
バイナリツリー内の 2 つのノードがいとこであるかどうかを確認する
エッジを削除するとバイナリツリーが 2 つの半分に分割されるかどうかを確認する
指定された二分木が完全かどうかを確認します
バイナリツリーにサイズ 2 以上の重複サブツリーが含まれているかどうかを確認する
2 つの木がミラーかどうかを確認する
折りたたみ可能なバイナリツリー
対称ツリー (それ自体の鏡像)
2 つのツリーが同一かどうかを判断するコードを作成する
二分木内の指定された合計を持つサブツリー
バイナリツリーの簡潔なエンコーディング
木のサイズを計算するプログラムを作成する
二分木の直径
バイナリツリー内のノードのレベルを取得する

二分木のデータ構造に関する中程度の問題:

指定されたインオーダートラバーサルで可能なすべてのバイナリツリーを検索します
すべてのノードにInorder Successorを設定します。
リンクされたリスト表現から完全なバイナリツリーを構築する
二分木を二分探索木に変換するために必要な最小スワップ
指定されたバイナリツリーを二重リンクリストに変換する |セット1
ツリーを偶数ノードのフォレストに変換する
バイナリツリーを反転
再帰を使用せずにルートからリーフへのパスを出力します
指定された Preorder、Inorder、Postorder のトラバースが同じツリーのものであるかどうかを確認します
指定されたバイナリツリーが完全かどうかを確認します。セット 1 (反復解法)
バイナリツリーが別のバイナリツリーのサブツリーであるかどうかを確認します。セット2
ツリー内の最大のサブツリー合計を見つける
2 つのノードが隣接しないようなバイナリツリー内のノードの最大合計
二分木における最下位共通祖先 |セット1
親配列からの汎用ツリーの高さ
バイナリツリーの 2 つの指定されたキー間の距離を求める

二分木のデータ構造に関する難しい問題:

右ポインタのみを使用して事前順序トラバーサルを取得するようにバイナリツリーを変更する
Preorder トラバーサルとミラーツリーの Preorder トラバーサルを使用して完全なバイナリツリーを構築する
指定された事前注文トラバーサルから特別なツリーを構築します
祖先行列からツリーを構築する
事前順序走査から完全な k 進木を構築する
括弧表現を使用して文字列からバイナリツリーを構築する
スパイラル形式でバイナリツリーを二重リンクリストに変換する
バイナリツリーを循環二重リンクリストに変換する
三項式を二項木に変換する
指定されたシーケンスを持つルートからリーフへのパスがあるかどうかを確認します
sum>= k のパスに存在しないすべてのノードを削除します
二分木における最大スパイラル和
文字列として表されるツリーの k 番目のレベルのノードの合計
ルートからリーフのパスまでに形成されるすべての数値の合計
ノード合計を実行して 2 つのバイナリツリーをマージする (再帰的および反復的)
すべてのノードの子 ID の合計が与えられるツリーのルートを検索します。

クイックリンク：

樹上の「ビデオ」

推奨：

データ構造とアルゴリズムを学ぶ | DSA チュートリアル