データ構造とアルゴリズム-ツリー

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

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

バイナリツリー

重要な用語

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

パス-パスは、ツリーのエッジに沿ったノードのシーケンスを指します。
ルート-ツリーの最上部のノードはルートと呼ばれます。ツリーごとにルートは1つだけで、ルートノードから任意のノードへのパスは1つだけです。
親-ルートノードを除くすべてのノードは、親と呼ばれるノードの上方に1つのエッジを持ちます。
子-下のエッジで接続された特定のノードの下のノードは、その子ノードと呼ばれます。
リーフ-子ノードを持たないノードは、リーフノードと呼ばれます。
サブツリー-サブツリーはノードの子孫を表します。
訪問-訪問は、制御がノード上にあるときにノードの値をチェックすることを指します。
探索-探索とは、特定の順序でノードを通過することを意味します。
レベル-ノードのレベルは、ノードの生成を表します。ルートノードがレベル0にある場合、その次の子ノードはレベル1に、孫はレベル2に、というように続きます。
キー-キーは、ノードの検索操作が実行されるノードの値を表します。

バイナリ検索ツリー表現

バイナリ検索ツリーは特別な動作を示します。ノードの左の子の値は親の値より小さく、ノードの右の子の値は親の値より大きくなければなりません。

バイナリ検索ツリー

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

ツリーノード

ツリーノードを記述するコードは、以下に示すものに似ています。データ部分と、その左および右の子ノードへの参照があります。

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

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

BSTの基本操作

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

挿入-ツリーに要素を挿入/ツリーを作成します。
検索-ツリー内の要素を検索します。
Preorder Traversal -事前順序でツリーを走査します。
Inorder Traversal -ツリーを順番に走査します。
Postorder Traversal -ポストオーダー方式でツリーを横断します。

この章では、ツリー構造の作成（挿入）とツリー内のデータ項目の検索について学習します。次の章で、ツリートラバースの方法について学習します。

挿入操作

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

アルゴリズム

If root is NULL
   then create root node
return

If 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 data

end If

実装

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

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

  //if tree is empty, create root node
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent  = NULL;

      while(1) {
         parent = current;

        //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;

           //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }

        //go to right of the tree
         else {
            current = current->rightChild;

           //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }
   }
}

検索操作

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

アルゴリズム

If root.data is equal to search.data
   return root
else
   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

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

struct node *search(int data) {
   struct node* current = root;
   printf("Visiting elements: ");

   while(current->data != data) {
      if(current != NULL)
      printf("%d ",current->data);

     //go to left tree

      if(current->data > data) {
         current = current->leftChild;
      }
     //else go to right tree
      else {
         current = current->rightChild;
      }

     //not found
      if(current == NULL) {
         return NULL;
      }

      return current;
   }
}

バイナリ検索ツリーデータ構造の実装については、リンクしてください：/data_structures_algorithms/tree_traversal_in_c [ここをクリック]。

Data-structures-algorithms-tree-data-structure

目次

データ構造とアルゴリズム-ツリー

重要な用語

バイナリ検索ツリー表現

ツリーノード

BSTの基本操作

挿入操作

アルゴリズム

実装

検索操作

アルゴリズム