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

入力二分木が二分木のサブツリーであるかどうかをチェックするC++プログラム


二分木は、各ノードに最大2つの子があり、左の子と右の子として定義されるツリーデータ構造です。

アルゴリズム

Begin
   function identical(): 
      Take two nodes r1 and r2 as parameter.
      If r1 and r2 is NULL then
         Return true.
      If r1 or r2 is NULL then
         Return false.
      Return (r1->d is equal to r2->d and
         Call function Identical(r1->l, r2->l) and
         Call functions Identical(r1->r, r2->r) );
      function Subtree(node *T, node *S) : 
         if (S == NULL) then
            return true;
         if (T == NULL) then
            return false;
         if (call function Identical(T, S))
            return true;
         return Subtree(T->l, S) or Subtree(T->r, S); 
End.


サンプルコード

#include <iostream>
using namespace std;
struct n {
   int d;
   struct n* l;
   struct n* r;
};
bool Identical(struct n * r1, struct n *r2) {
   if (r1 == NULL && r2 == NULL)
      return true;
   if (r1 == NULL || r2 == NULL)
      return false;
      return (r1->d == r2->d && Identical(r1->l, r2->l) && Identical(r1->r, r2->r) );
}
bool Subtree(struct n *T, struct n *S) {
   if (S == NULL)
      return true;
   if (T == NULL)
      return false;
   if (Identical(T, S))
      return true;
      return Subtree(T->l, S) || Subtree(T->r, S);
}
struct n* newN(int d) {
   struct n* nod =
   (struct n*)malloc(sizeof(struct n));
   nod->d = d;
   nod->l = NULL;
   nod->r = NULL;
   return(nod);
}
int main() {
   struct n *T = newN(24);
   T->r = newN(2);
   T->r->r = newN(5);
   T->l = newN(7);
   T->l->l = newN(3);
   T->l->l->r = newN(40);
   T->l->r = newN(6);
   struct n *S = newN(20);
   S->r = newN(5);
   S->l = newN(3);
   S->l->r = newN(50);
   if (Subtree(T, S))
      cout<<"given tree is subtree of Binary tree"<<"\n";
   else
      cout<<"given tree is not subtree of Binary tree"<<"\n";
      struct n *T1 = newN(30);
      T1->r = newN(20);
      T1->r->r = newN(19);
      T1->l = newN(17);
      T1->l->l = newN(4);
      T1->l->l->r = newN(40);
      T1->l->r = newN(15);
      struct n *S1 = newN(17);
      S1->r = newN(15);
      S1->l = newN(4);
      S1->l->r = newN(40);
      if (Subtree(T1, S1))
         cout<<"given tree is subtree of Binary tree";
      else
         cout<<"given tree is not subtree of Binary tree";
         getchar();
         return 0;
}

出力

given tree is not subtree of Binary tree
given tree is subtree of Binary tree

  1. 特定のバイナリツリーがC++のSumTreeであるかどうかを確認します

    ここでは、二分木が和木であるかどうかを確認する方法を説明します。ここで問題となるのは、合計ツリーとは何かです。合計ツリーは、ノードがその子の合計値を保持する二分木です。ツリーのルートには、その下にあるすべての要素の合計が含まれます。これは合計ツリーの例です- これを確認するために、簡単なトリックに従います。合計値がルートと同じである場合は、左右のサブツリー要素の合計を見つけます。これが合計ツリーです。これは再帰的なアプローチの1つになります。 例 #include <bits/stdc++.h> using namespace std; class node {  

  2. 二分木がC++の別の二分木のサブツリーであるかどうかを確認します

    2つの二分木があるとします。小さい方のツリーが別の二分木のサブツリーであるかどうかを確認する必要があります。これらの2本の木が与えられていると考えてください。 2本の木があります。 2番目のツリーは、最初のツリーのサブツリーです。このプロパティを確認するために、ポストオーダー方式でツリーをトラバースします。このノードをルートとするサブツリーが2番目のツリーと同一である場合、それはサブツリーです。 例 #include <bits/stdc++.h> using namespace std; class node {    public:   &