広告

ツリーは、エッジで接続されたノードを表します。 二分木または二分探索木について具体的に議論する。

バイナリツリーは、データストレージの目的で使用される特別なデータ構造です。 二分木は、各ノードが最大二つの子を持つことができるという特別な条件を持っています。, バイナリツリーには、並べ替えられた配列と同じくらい検索が速く、挿入または削除操作がリンクリストと同じくらい速いため、順序付けられた配列と

重要な用語

以下は、ツリーに関する重要な用語です。

  • Path-Pathは、ツリーのエッジに沿ったノードのシーケンスを指します。

  • Root-ツリーの上部にあるノードはrootと呼ばれます。 あるルート当たり、一つのパスからのルートノードに他のノードです。,

  • Parent-ルートノード以外のすべてのノードは、親と呼ばれるノードに上向きの一方のエッジを持っています。

  • Child−指定されたノードの下のノードは、そのエッジで下方に接続されているノードを子ノードと呼びます。

  • Leaf-子ノードを持たないノードをリーフノードと呼びます。

  • Subtree-サブツリーはノードの子孫を表します。

  • 訪問-訪問は、制御がノード上にあるときにノードの値をチェックすることを指します。

  • トラバース−トラバースとは、特定の順序でノードを通過することを意味します。,

  • Levels-ノードのレベルは、ノードの生成を表します。 ルートノードがレベル0の場合、その次の子ノードはレベル1、孫ノードはレベル2などになります。キー−キーは、ノードに対して探索操作が実行されるノードの値を表します。

バイナリ検索ツリー表現

バイナリ検索ツリーは特別な動作を示します。 ノードの左の子は、親の値よりも小さい値を持ち、ノードの右の子は、親の値よりも大きい値を持つ必要があります。,

ノードオブジェクトを使用してツリーを実装し、参照を介してそれらを接続します。

ツリーノード

ツリーノードを記述するコードは、以下に示すものと似ています。 これは、データ部分とその左と右の子ノードへの参照を持っています。

struct node { int data; struct node *leftChild; struct node *rightChild;};

ツリーでは、すべてのノードが共通の構造を共有します。

BST基本操作

バイナリ検索ツリーデータ構造で実行できる基本操作は、次のとおりです。

  • Insert−ツリーに要素を挿入/ツリーを作成します。,

  • 検索-ツリー内の要素を検索します。

  • Preorder Traversal−事前に順序付けされた方法でツリーをトラバースします。

  • Inorder Traversal−順序通りにツリーをトラバースします。

  • Postorder Traversal−ポストオーダーの方法でツリーをトラバースします。

この章では、ツリー構造を作成（挿入）し、ツリー内のデータ項目を検索することについて学びます。 私たちは、来る章でツリートラバース方法について学びましょう。

挿入操作

最初の挿入はツリーを作成します。, その後、要素が挿入されるたびに、まずその適切な場所を見つけます。 ルートノードから検索を開始し、データがキー値よりも小さい場合は、左側のサブツリーで空の場所を検索してデータを挿入します。 それ以外の場合は、右側のサブツリーで空の場所を検索し、データを挿入します。,

Algorithm

If root is NULL then create root nodereturnIf root exists then compare the data with node.data while until insertion position is located If data is greater than node.data goto right subtree else goto left subtree endwhile insert dataend If

実装

挿入関数の実装は次のようになります−

検索操作

要素を検索するたびに、ルートノードから検索を開始し、データがキー値よりも小さい場合は、左のサブツリーの要素を検索します。 それ以外の場合は、右側のサブツリー内の要素を検索します。 各ノードで同じアルゴリズムに従います。

Algorithm

If root.data is equal to search.data return rootelse while data not found If data is greater than node.data goto right subtree else goto left subtree If data found return node endwhile return data not found end if

このアルゴリズムの実装は次のようになります。,

バイナリ検索ツリーデータ構造の実装について知るには、ここをクリックしてください。

広告

0