为什么在这个树程序中我得到两次输出？

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 equal”，并在下一行中得到“tree are equal”。我无法破译为什么？我已经写下了整个程序，以便任何人都可以复制粘贴并在他们的系统上运行它。我想问题出在 Same_tree 的递归调用中，但我没有得到的东西在哪里以及为什么

Answer 1

比较树时，如果左节点不同，则仅返回 -1（错误）。您只需忽略正确的节点即可。另外，如果您的树仅在右侧不同，则您的 same_tree 根本不会返回值。我真的很惊讶这个编译结果。

如果仔细查看 Same_tree，您会发现它检查是否只有一个 let/right 为空，然后检查非是否为空。然而，如果它们都为空，你就会失败。您还可以在很多时候忽略返回值。

假设你有两个根，每个根的值为 5，其中一个的值为 7，另一个的值为 8。现在，当输入 same_tree 时，您将比较前面不同的左边。但是，返回值将被忽略，您将继续比较根值（均为 5），并且由于它们相同，您将不会返回错误代码，并且您的 main 方法将认为一切都很好，并打印它们是相等的。

Answer 2

您在 Same_tree 中缺少相同树的 return 语句，这不会让您感到困扰吗？编译器应该警告你。如果您使用 g++，您应该始终使用

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

Answer 3

您的插入方法中缺少 return 语句（令人惊讶的是它已编译）：

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;
}