バイナリツリーは、各ノードに値（この場合はキーでもある）があり、左および右の子孫にリンクしている階層データ構造です。 最上位レベルにあるノード（誰かまたは子孫ではない）は、ルートと呼ばれます。 子を持たないノード（両方の子がNULL）は、リーフと呼ばれます。
図 1つのバイナリツリー
バイナリ検索ツリーは、追加のプロパティを持つバイナリツリーです。左側の子の値は親の値よりも小さく、右側の子の値はツリーの各ノードの親の値よりも大きくなります。 つまり、バイナリ検索ツリーのデータはソートされた形式で保存されます。 新しいノードを挿入するか、既存のノードを削除するたびに、ソートされたツリーの順序が保存されます。 要素を検索するとき、検索された値はルートと比較されます。 検索がルートよりも大きい場合、検索はルートの右の子孫で続行され、小さい場合は左、等しい場合は左で検索され、値が検出されて検索が停止します。
図 2バイナリ検索ツリー
平衡二分探索木は、対数の高さを持つ二分探索木です。 この定義は厳密ではなくイデオロギー的です。 厳密な定義は、最も深い葉と最も浅い葉の深さの差（AVLツリー）または最も深い葉と最も浅い葉の深さの比率（赤黒木）で動作します。 バランスの取れたバイナリ検索ツリーでは、検索、挿入、および削除の操作は対数時間で実行されます（ルートからシートへのパスは対数にすぎないため）。 不均衡なバイナリ検索ツリーの縮退した場合、たとえば、ソートされたシーケンスが空のツリーに挿入された場合、ツリーは線形リストに変わり、検索、挿入、および削除の操作は線形時間で実行されます。 したがって、ツリーのバランスを取ることは非常に重要です。 技術的には、この要素の挿入がバランス条件に違反している場合、新しい要素を挿入するときにツリーの一部を回転させることにより、バランシングが実行されます。
図 3バランスの取れたバイナリ検索ツリー
バランスの取れたバイナリ検索ツリーは、新しい要素の挿入と既存の要素の削除を交互に行って、要素のクイック検索を実行する必要がある場合に使用されます。 データ構造に格納されている要素のセットが固定されており、新しい挿入と削除がない場合、配列が推奨されます。 検索は同じ対数時間のバイナリ検索アルゴリズムで実行できますが、ポインターの保存と使用に追加費用はかかりません。 たとえば、C ++では、連想コンテナセットとマップはバランスの取れたバイナリ検索ツリーを表します。
図 4非常に不均衡なバイナリ検索ツリー
次に、再帰について簡単に説明します。 プログラミングの再帰は、他の引数を使用したそれ自体の関数呼び出しです。 原則として、再帰関数は同じ引数で自分自身を呼び出すことができますが、この場合、無限の再帰サイクルが発生し、スタックオーバーフローが発生します。 再帰関数の中には、関数が終了する基本的なケースと、他の引数を使用してそれ自体を呼び出す必要があります。 引数は単に異なるだけでなく、関数呼び出しを基本ケースに近づける必要があります。 たとえば、階乗を計算する再帰関数内の呼び出しはより小さい引数で実行する必要があり、ツリーを走査する再帰関数内の呼び出しは、ノードをルートから遠く、リーフに近づける必要があります。 再帰は、直接（自分を直接呼び出す）だけでなく、間接的でもあります。 たとえば、AがBを呼び出し、BがAを呼び出します。再帰を使用すると、反復ループとスタックデータ構造（LIFO）の操作をエミュレートできます。
int factorial(int n) { if(n <= 1) // { return 1; } return n * factorial(n - 1); // } // factorial(1): return 1 // factorial(2): return 2 * factorial(1) (return 2 * 1) // factorial(3): return 3 * factorial(2) (return 3 * 2 * 1) // factorial(4): return 4 * factorial(3) (return 4 * 3 * 2 * 1) // n (n - int // . long long // . , // // ). void reverseBinary(int n) { if (n == 0) // { return; } cout << n%2; reverseBinary(n/2); // } // void forvardBinary(int n) { if (n == 0) // { return; } forvardBinary(n/2); // cout << n%2; } // // // void ReverseForvardBinary(int n) { if (n == 0) // { return; } cout << n%2; // ReverseForvardBinary(n/2); // cout << n%2; // } // , // int product(int x, int y) { if (y == 0) // { return 0; } return (x + product(x, y-1)); // } // x * y ( xy ) // , //
グラフ理論の観点から木について簡単に説明します。 グラフは、頂点とエッジのセットです。 エッジは、2つの頂点間の接続です。 グラフ内の可能なエッジの数は、頂点の数に二次的に依存します（理解するために、試合のトーナメントテーブルを想像できます）。 ツリーは、サイクルのない接続されたグラフです。 接続性とは、頂点から他の頂点まで、エッジに沿ったパスがあることを意味します。 サイクルがないということは、このパスが唯一のものであることを意味します。 グラフトラバーサルは、そのすべての頂点への体系的な訪問です。 グラフトラバーサルには2つのタイプがあります。1）ディープサーチ。 2）広い検索。
幅優先探索（BFS）は最初の頂点から行われ、最初に最初の頂点から1つのエッジの距離にあるすべての頂点を訪問し、次に最初の頂点から2つのエッジの距離にあるすべての頂点を訪問します。 幅優先探索アルゴリズムは、本質的に非再帰的（反復的）です。 その実装には、キューデータ構造（FIFO）が使用されます。
深さ検索（DFS）は開始頂点から行われ、開始頂点からの距離に関係なく、まだ訪問されていない頂点を訪問します。 ディープサーチアルゴリズムは、本質的に再帰的です。 アルゴリズムの反復バージョンで再帰をエミュレートするには、スタックのデータ構造が使用されます。
正式な観点からは、幅優先探索と深さ探索の両方の再帰バージョンと反復バージョンの両方を作成することができます。 どちらの場合も、ウォークイン幅にはキューが必要です。 幅の再帰の再帰的実装での再帰は、ループをエミュレートするだけです。 ディープウォークには、スタックのない再帰的な実装、スタックのある再帰的な実装、スタックのある反復的な実装があります。 スタックなしで深くなることの反復的な実装は不可能です。
幅と深さの両方で巡回する漸近的な複雑さはO（V + E）です。ここで、Vは頂点の数、Eはエッジの数です。 つまり、頂点とエッジの数は線形です。 実質的な観点からのレコードO（V + E）は、レコードO（max（V、E））と同等ですが、後者は受け入れられません。 つまり、複雑さは最大2つの値によって決定されます。 エッジの数は頂点の数に二次的に依存するという事実にもかかわらず、グラフが非常にまばらな場合、これはエラーになるため、複雑さをO（E）と書くことはできません。
DFSは、有向グラフで強く接続されたコンポーネントを見つけるためのアルゴリズムで使用されます。 BFSは、グラフ、ネットワーク経由でメッセージを送信するためのアルゴリズム、ガベージコレクター、インデックスプログラム、検索エンジンスパイダーで最短経路を見つけるために使用されます。 DFSとBFSの両方がアルゴリズムで使用され、グラフのサイクルをチェックするときに最小スパニングツリーを見つけて、二部をチェックします。
グラフ内の幅のクロールは、バイナリツリーのレベルに沿ったクロールに対応します。 この迂回では、ノードはトップダウンおよび左から右にアクセスされます。 グラフの深さには、直接（事前順序）、対称（順序）、逆（事後順序）の3種類のバイナリツリートラバーサルがあります。
直接バイパスの順序は、ルート、左の子孫、右の子孫です。 対称-左の子孫、ルート、右の子孫。 その逆は、左の子孫、右の子孫、ルートです。 対応する呼び出しの順序（コードの行の順序）は、対応するバイパスの再帰関数のコードに保存され、ルートの代わりにこの再帰関数の呼び出しが呼び出されます。
木の画像が与えられ、そのラウンドを見つける必要がある場合、次の手法が役立ちます（図5を参照）。 閉じた曲線のエンベロープのツリーを円で囲みます（左下に移動し、右上に閉じます）。 直接走査は、ルートから移動するエンベロープが最初に左側のノードの近くを通過する順序に対応します。 対称バイパスの場合、ルートから移動するエンベロープが最初に下のノードの近くを通過する順序。 往復の場合、ルートから移動するエンベロープが右側のノードの隣を初めて通過する順序。 再帰呼び出しのコードでは、直接バイパスが行われます：call、left、right。 対称-左、呼び出し、右。 その逆は左右です、呼び出します。
図 5ラウンドの補助図
バイナリ検索ツリーの場合、対称トラバーサルはソートされた順序ですべてのノードを通過します。 ノードを逆ソート順で訪問したい場合、対称トラバーサルの再帰関数のコードで、右と左の子孫を交換する必要があります。
struct TreeNode { double data; // / TreeNode *left; // TreeNode *right; // }; void levelOrderPrint(TreeNode *root) { if (root == NULL) { return; } queue<TreeNode *> q; // q.push(root); // while (!q.empty() ) // { TreeNode* temp = q.front(); // q.pop(); // cout << temp->data << " "; // if ( temp->left != NULL ) q.push(temp->left); // if ( temp->right != NULL ) q.push(temp->right); // } } void preorderPrint(TreeNode *root) { if (root == NULL) // { return; } cout << root->data << " "; preorderPrint(root->left); // preorderPrint(root->right); // } // . // // void inorderPrint(TreeNode *root) { if (root == NULL) // { return; } preorderPrint(root->left); // cout << root->data << " "; preorderPrint(root->right); // } // . // void postorderPrint(TreeNode *root) { if (root == NULL) // { return; } preorderPrint(root->left); // preorderPrint(root->right); // cout << root->data << " "; } // . // ( ). void reverseInorderPrint(TreeNode *root) { if (root == NULL) // { return; } preorderPrint(root->right); // cout << root->data << " "; preorderPrint(root->left); // } // . // void iterativePreorder(TreeNode *root) { if (root == NULL) { return; } stack<TreeNode *> s; // s.push(root); // /* . 1) 2) ! (! !) 3) ! */ while (s.empty() == false) { // TreeNode *temp = s.top(); s.pop(); cout << temp->data << " "; if (temp->right) s.push(temp->right); // if (temp->left) s.push(temp->left); // } } // // .
私はあなたが眠りに落ちなかったことを願っています、そして記事は役に立ちました。 すぐに記事の