C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

デカルトツリーを実装するC++プログラム


これがデカルトツリーを実装するためのC++プログラムです。

アルゴリズム

Begin
   class CarTree to declare the functions:
      min() = To find index of the minimum element in array:
   if (arr[i] < min)
      min = arr[i]
      minind = i
      inorder() = For inorder traversal of the tree:
   If tree is empty
      Then return
      inorder (node->l)
      Print the root as node->d
      inorder (node->r)
End

サンプルコード

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct nod//node declaration {
   int d;
   struct nod* l;
   struct nod* r;
};

class CarTree {
   public://declare the functions
   nod *newNode (int);
   int min(int [], int, int);
   nod *buildTree (int [], int, int);
   void inorder (nod* node);
   void show(nod *, int);
   CTree()
   {}
};

int CarTree::min(int arr[], int s, int e) {
   int i, min = arr[s], minind = s;
   for (i = s + 1; i <= e; i++) {
      if (arr[i] < min) {
         min = arr[i];
         minind = i;
      }
   }
   return minind;
}

nod *CarTree::buildTree (int inorder[], int s, int e)//build the cratesian tree {
   if (s >e)
      return NULL;
      int i = min(inorder, s, e);
      nod *r = newNode(inorder[i]);
   if (s == e)
      return r;
      r->l = buildTree(inorder, s, i - 1);//call the function recursively for left child
      r->r = buildTree(inorder, i + 1, e);//call the function recursively for right child
      return r;
}

void CarTree::inorder (struct nod* node) {
   if (node == NULL)
      return;
      inorder (node->l);
      cout<<node->d<<" ";
      inorder (node->r);
}

void CarTree::show(nod *ptr, int level)//show the tree {
   int i;
   if(ptr == NULL)
      return;
   if (ptr != NULL) {
      show(ptr->r, level + 1);
      cout<<endl;
      for (i = 0;i < level;i++)
         cout<<" ";
         cout<<ptr->d;
         show(ptr->l, level + 1);
   }
}

nod *CarTree::newNode (int d)//creation of new node {
   nod* t = new nod;
   t->d = d;
   t->l = NULL;
   t->r = NULL;
   return t;
}

int main() {
   CarTree ct;
   int i, n;
   cout<<"Enter number of elements to be inserted: ";
   cin>>n;
   int a[n];
   for (i = 0; i < n; i++) {
      cout<<"Enter Element "<<i + 1<<" : ";
      cin>>a[i];
   }
   nod *r = ct.buildTree(a, 0, n - 1);
   cout<<"Cartesian tree Structure: "<<endl;
   ct.show(r,1);
   cout<<endl;
   cout<<"\n Inorder traversal of the tree \n"<<endl;
   ct.inorder(r);
   cout<<endl;
   return 0;
}

出力

Enter number of elements to be inserted: 10
Enter Element 1 : 10
Enter Element 2 : 30
Enter Element 3 : 20
Enter Element 4 : 40
Enter Element 5 : 50
Enter Element 6 : 70
Enter Element 7 : 60
Enter Element 8 : 80
Enter Element 9 : 100
Enter Element 10 : 112
Cartesian tree Structure:
112
100
80
60
70
50
40
20
30
10
Inorder traversal of the tree
10 30 20 40 50 70 60 80 100 112

  1. AVLツリーを実装するためのC++プログラム

    AVLツリーは自己平衡二分探索木であり、左右のサブツリーの高さの差がすべてのノードで複数になることはありません。 ツリーの回転は、AVLツリーの要素の順序を妨げることなく構造を変更する操作です。ツリー内で1つのノードを上に移動し、1つのノードを下に移動します。これは、ツリーの形状を変更したり、小さいサブツリーを下に移動したり、大きいサブツリーを上に移動したりして高さを低くしたりするために使用され、多くのツリー操作のパフォーマンスが向上します。回転の方向は、木のノードが移動する側に依存しますが、他の人は、どの子がルートの場所をとるかに依存すると言います。これは、AVLツリーを実装するためのC+

  2. 基数ソートを実装するC++プログラム

    基数ソートは、非比較ソートアルゴリズムです。この並べ替えアルゴリズムは、同じ位置と値を共有する数字をグループ化することにより、整数キーで機能します。基数は、記数法のベースです。 10進法では、基数または基数は10であることがわかっているので、いくつかの10進数を並べ替えるには、数値を格納するために10個の位取りボックスが必要です。 基数ソート手法の複雑さ 時間計算量:O(nk) スペースの複雑さ:O(n + k) Input − The unsorted list: 802 630 20 745 52 300 612 932 78 187 Output &minus