Почему в этой древовидной программе я получаю вывод дважды?

Question

Может кто-нибудь объяснить, почему я получаю вывод здесь дважды?

# include<iostream>
# include<conio.h>
# include <stdio.h>

using namespace std;

struct tree
{
  int data;
  struct tree * left;
  struct tree * right;
};

struct tree * insert(struct tree * root,int value)
{
   if (root==NULL)
   {
      struct tree * node= (struct tree *)malloc(sizeof(struct tree));
      node->data=value;
      node->right=NULL;
      node->left=NULL;
      return node;
   }
   else if(root->data > value )
      root->left=insert(root->left,value);
   else
      root->right=insert(root->right,value);
}

int same_tree(struct tree * root1, struct tree* root2)
{
   if((root1==NULL && root2!=NULL) || (root1!=NULL && root2==NULL))
   {
      cout << " tree are not equal \n"; 
      return -1;
   }
   if(root1 && root2)
   {
      same_tree(root1->left,root2->left);
      if(root1->data!=root2->data)
      {
         cout << "tree not equal \n";   
         return -1;                        
      } 
      same_tree(root1->right,root2->right);
   }   
}

int main()
{
   struct tree * root=NULL;
   root= insert(root,8);
   insert(root,6);
   insert(root,7);
   insert(root,5);
   insert(root,1);
   insert(root,20);
   insert(root,15);
   struct tree * root2=NULL; 
   root2= insert(root2,8);
   insert(root2,6);
   insert(root2,7);
   insert(root2,5);
   insert(root2,1);
   insert(root2,20);
   insert(root2,18);
   int j= same_tree(root,root2);
   if(j==-1)
      cout << " tree not eqqual \n";
   else
      cout << "tree are equal\n";
   getch();
   return 0;   
}

Программа написана для сравнения, если два дерева одинаковы (в одной иерархической структуре и в данных, которые они содержат). Два дерева, которые я сравниваю, передаются из main (root и root2). В случае равного дерева я получаю O / O как «дерево равны» один раз. Но в случае, если дерево не равно, я получаю o / p "tre not равный" и в следующей строке как "дерево равно". Я не могу расшифровать Почему? Я записал всю программу, чтобы каждый мог скопировать и запустить ее в своей системе. Я предполагаю, что проблема заключается где-то в рекурсивном вызове same_tree, но где и почему что-то я не получаю

Answer 1

Вас не беспокоит, что вы пропускаете оператор return в same_tree для одинаковых деревьев?Компилятор должен предупредить вас об этом.Если вы используете g ++, вы всегда должны использовать

-W -Wall (-pedantic is good as well)

Answer 2

При сравнении деревьев вы возвращаете -1 (ошибка), если левый узел отличается.Вы просто игнорируете правильные узлы.Кроме того, если ваши деревья отличаются только с правой стороны, то same_tree вообще не возвращает значения.Я на самом деле удивлен, что это скомпилировано вообще.

Если вы внимательно посмотрите на ваше same_tree, вы увидите, что он проверяет, является ли только одно из let / right нулевым, а затем, если non - нулевым.Однако, если они оба нулевые, вы просто проваливаетесь.Вы также игнорируете возвращаемое значение во многих точках.

Скажем, у вас есть два корня, каждый со значением 5, и один из них оставил 7, а другой оставил 8. Теперь при вводе same_tree вы будете сравнивать левыекоторый будет противостоять тому, что отличается.Однако возвращаемое значение игнорируется, и вы продолжите сравнение корневого значения (оба значения 5), и, поскольку они одинаковы, вы не вернете код ошибки, и ваш метод main будет думать, что все в порядке, и вывести, что они равны..

Answer 3

В вашем методе вставки отсутствует оператор возврата (удивительно, что он скомпилирован):

struct tree * insert(struct tree * root,int value)
{
   if (root==NULL)
   {
      struct tree * node= (struct tree *)malloc(sizeof(struct tree));
      node->data=value;
      node->right=NULL;
      node->left=NULL;
      return node;
   }
   else if(root->data > value )
      root->left=insert(root->left,value);
   else
      root->right=insert(root->right,value);

   return root;
}