验证一棵二叉树是否是另一棵二叉树的镜像

Question

我正在用C语言编写一个程序，旨在识别两个二叉树是否是镜像。在我的程序中，我设法创建了两棵树，其结构如下图所示：

我的问题是我不知道如何创建递归方法来验证两棵二叉树是否是镜像的，一棵相对于另一棵；我试过创建这个方法，但我只设法比较了两个二叉树的根，我无法超越开头。

附件是我目前的代码。

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

//Define the structure for the two binary trees
typedef struct{
int dato;
struct nodo *izq;
struct nodo *der;
}nodo;


typedef struct{
int dato;
struct nodo *izq;
struct nodo *der;
}nodo1;

//Define auxiliary pointers
nodo *raiz = NULL;/

nodo1 *raiz1 = NULL;//


//Function to add nodes
void insertarNodo(int datoI){


nodo *nuevo = malloc(sizeof(nodo));

nuevo->dato = datoI;
nuevo->izq = NULL;
nuevo->der = NULL;

if(raiz == NULL)
raiz = nuevo;
else{

nodo *anterior, *recorrer;

anterior = NULL;

recorrer = raiz;


while(recorrer != NULL){
    
    anterior = recorrer;
    
    if(datoI < recorrer->dato)
        recorrer = recorrer->izq;
    else
        recorrer = recorrer->der;
}

if(datoI < anterior->dato)
    anterior->izq = nuevo;
else
    anterior->der = nuevo;
}

}



//Function to add nodes
void insertarNodo1(datoI){


nodo1 *nuevo = malloc(sizeof(nodo1));


nuevo->dato = datoI;
nuevo->izq = NULL;  
nuevo->der = NULL;


if(raiz1 == NULL)
raiz1 = nuevo;
else{

nodo1 *anterior, *recorrer;

anterior = NULL;

recorrer = raiz1;


while(recorrer != NULL){
   
    anterior = recorrer;
    
    if(datoI > recorrer->dato)
        recorrer = recorrer->izq;
    else
        recorrer = recorrer->der;
}

if(datoI > anterior->dato)
    anterior->izq = nuevo;
else
    anterior->der = nuevo;
}

}


void mostrarArbol1(nodo *arbol, int contador){
int i = 0;

if(arbol == NULL){
return;
}else{
mostrarArbol1(arbol->der,contador+1);

for(i=0; i<contador;i++)
    printf("   ");

printf("(%d)\n",arbol->dato);
mostrarArbol1(arbol->izq,contador+1);
}
}




void mostrarArbol2(nodo1 *arbol, int contador){
int i = 0;

if(arbol == NULL){
return;
}else{
mostrarArbol2(arbol->der,contador+1);

for(i=0; i<contador;i++)
    printf("   ");

printf("(%d)\n",arbol->dato);
mostrarArbol2(arbol->izq,contador+1);
}
}

//Recursive method I need help with
void isMirror(nodo* p,nodo1* q) {



if(p->dato == q->dato){
printf("Mirrors");
}

else{
printf("Not mirrors");
}

isMirror(p->der, q->izq);


}




int main(){


insertarNodo(20);
insertarNodo(8);
insertarNodo(22);
insertarNodo(25);
insertarNodo(12);
insertarNodo(14);
insertarNodo(10);
insertarNodo(14);



insertarNodo1(20);
insertarNodo1(8);
insertarNodo1(22);
insertarNodo1(25);
insertarNodo1(12);
insertarNodo1(4);
insertarNodo1(10);
insertarNodo1(14);



mostrarArbol1(raiz, 0);

printf("\n\n--------------------------\n\n");

mostrarArbol2(raiz1, 0);
printf("\n\n--------------------------\n\n");



isMirror(raiz, raiz1);




 return 0;

}

你能帮帮我吗？

非常感谢您。

Answer 1

为您的 isMirror 函数尝试以下修复。我们只是从第一个根节点取左边，从第二个根节点取右边，然后比较它们的值。

void isMirror(nodo* p,nodo1* q) {

  if(!p || !q) return;

  if(p->dato == q->dato){
      printf("%d Mirrors\n", p->dato);
  } else {
     printf("%d %d Not mirrors\n", p->dato,q->dato);
  }

  isMirror(p->der, q->izq);
  isMirror(q->der, p->izq);
}

更新：添加了布尔结果 return

bool isMirror(nodo* p,nodo1* q) {

  if(!p && !q) return true;
  if(!p || !q) return false;

  bool result = true;
  if(p->dato == q->dato){
      printf("%d Mirrors\n", p->dato);
  } else {
     printf("%d %d Not mirrors\n", p->dato,q->dato);
     return false;
  }

  result = result && isMirror(p->der, q->izq);
  result = result && isMirror(q->der, p->izq);
  return result;
}

Answer 2

递归方式

int isMirror(nodo* p,nodo1* q) {
  if (p == NULL && q == NULL)) return 1; // Reached the end of the line
  if (p != NULL || q != NULL) return 0; // One branch is longer than the other

  if(p->dato != q->dato){
      return 0; // Not the same
  }

  return isMirror(p->der, q->izq) && isMirror(q->der, p->izq); // Both the same?
}

Answer 3

对于初学者来说，函数应该这样声明

bool isMirror( const nodo *p, const nodo1 *q );

也就是说它的参数应该有限定符 const 因为传递的节点在函数内没有改变。而函数应该做一件事：检查一棵二叉树是否是另一棵二叉树的镜像，由函数的调用者决定是否输出消息。

函数可以这样定义

bool isMirror( const nodo *p, const nodo1 *q )
{
    return ( p == NULL && q == NULL ) ||
           ( p != NULL && q != NULL && 
             p->dato == q->dato  && 
             isMirror( p->izq, q->der ) &&
             isMirror( p->der, q->izq ) ); 
}

然后在main里面可以写

printf( "raiz1 is a mirror of raiz is %s\n", 
        isMirror( raiz, raiz1 ) ? "true" : "false" );

验证一棵二叉树是否是另一棵二叉树的镜像

Verify if a binary tree is a mirror of another binary tree

c

struct

binary-tree

function-definition