C++で配列を実装した二分木

二分木は、ツリーの各ノードが最大2つの子ノードを持つことができる特殊なタイプのツリーです。これらの子ノードは、右子および左子と呼ばれます。

単純な二分木は-

木を表現するには、2つの方法があります。

• リンクリストを使用する動的ノード表現
• 配列を使用する順次表現。

ここでは、二分木の配列表現について説明します。このために、BTのノードに番号を付ける必要があります。この番号付けは、0から（n-1）または1からnまで開始できます。

配列内のノードとその親ノードおよび子ノードの位置を導き出します。

0インデックスベースのシーケンスを使用する場合

親ノードがインデックスpであるとします。

次に、left_childノードはインデックス（2 * p）+1にあります。

right_childノードはインデックス（2 * p）+2にあります。

ルートノードはインデックス0にあります。

left_childはインデックス1にあります。

Right_childはインデックス2にあります。

1つのインデックスベースのシーケンスを使用する場合

親ノードがインデックスpにあるとします。

Right_nodeはインデックス（2 * p）にあります。

Left_nodeはインデックス（2 * p）+1にあります 。

ルートノードはインデックス1にあります。

left_childはインデックス2にあります。

Right_childはインデックス3にあります。

例

#include<bits/stdc++.h>
using namespace std;
char tree[10];
int rootnode(char key){
   if(tree[0] != '\0')
      cout<<"Tree already had root";
   else
      tree[0] = key;
   return 0;
}
int leftchild(char key, int parent){
   if(tree[parent] == '\0')
      cout <<"\nCan't set child at"<<(parent * 2) + 1<<" , no parent found";
   else
      tree[(parent * 2) + 1] = key;
   return 0;
}
int rightchild(char key, int parent){
   if(tree[parent] == '\0')
      cout<<"\nCan't set child at"<<(parent * 2) + 2<<" , no parent found";
   else
      tree[(parent * 2) + 2] = key;
   return 0;
}
int traversetree(){
   cout << "\n";
   for(int i = 0; i < 10; i++){
      if(tree[i] != '\0')
         cout<<tree[i];
      else
         cout<<"-";
   }
   return 0;
}
int main(){
   rootnode('A');
   rightchild('C', 2);
   leftchild('D', 0);
   rightchild('E', 1);
   rightchild('F', 2);
   traversetree();
   return 0;
}

出力

Can't set child at6 , no parent found
Can't set child at6 , no parent found
AD--E-----