algorithm
木

備考

前書き

ツリーは、より一般的なノード - エッジグラフデータ構造のサブタイプである。

ツリーであるためには、グラフは次の2つの要件を満たさなければなりません。

• それは非環式である。サイクル（または「ループ」）は含まれません。
• それは接続されています。グラフ内の任意のノードについて、すべてのノードに到達可能である。すべてのノードは、グラフの1つのパスで到達可能です。

木のデータ構造はコンピュータサイエンスの中では非常に一般的です。ツリーは、通常のバイナリツリー、レッドブラックツリー、Bツリー、ABツリー、23ツリー、ヒープ、および試行など、さまざまなアルゴリズムデータ構造をモデル化するために使用されます。

ツリーをRooted Treeと呼ぶのは一般的です。

choosing 1 cell to be called `Root`
painting the `Root` at the top
creating lower layer for each cell in the graph depending on their distance from the root -the bigger the distance, the lower the cells (example above)

木の共通シンボル： T

典型的な橋渡し的な木表現

典型的には、バイナリツリー（ノードあたり正確に2つの子を持つもの）として、1つのツリー（1ノードあたり潜在的に無制限の子を持つもの）をバイナリツリーとして表します。 「次の」子供は兄弟とみなされます。ツリーがバイナリの場合、この表現は余分なノードを作成することに注意してください。

次に、兄弟を繰り返して、子供たちを再帰させます。ほとんどの木は比較的浅く、子供はたくさんありますが、少数の階層しかないので、効率的なコードが作成されます。人間の系譜は例外です（祖先のレベルはたくさんあり、レベルごとに少数の子供のみです）。

必要に応じて、バックポインタを保持してツリーを昇順にすることができます。これらは維持することがより困難です。

ルートを呼び出す関数と、余分なパラメータ（この場合はツリーの深さ）を持つ再帰関数を持つ関数が一般的であることに注意してください。

  struct node
  {
     struct node *next;
     struct node *child;
     std::string data;
  }

  void printtree_r(struct node *node, int depth)
  {
     int i;

     while(node)
     {
         if(node->child)
         {
            for(i=0;i<depth*3;i++)
                printf(" ");
            printf("{\n"):
            printtree_r(node->child, depth +1);
            for(i=0;i<depth*3;i++)
                printf(" ");
            printf("{\n"):
    
            for(i=0;i<depth*3;i++)
               printf(" ");
             printf("%s\n", node->data.c_str());

             node = node->next;
          }
      }
  }

  void printtree(node *root)
  {
     printree_r(root, 0);
  }

2つのバイナリツリーが同じかどうかをチェックする

1. たとえば、入力が次の場合：

例：1

a）

b）

出力は真でなければなりません。

例：2

入力が以下の場合：

a）

b）

出力はfalseにする必要があります。

同じのための擬似コード：

boolean sameTree(node root1, node root2){

if(root1 == NULL && root2 == NULL)
return true;

if(root1 == NULL || root2 == NULL)
return false;

if(root1->data == root2->data 
     && sameTree(root1->left,root2->left)
        && sameTree(root1->right, root2->right))
return true;

}