树相等

请实现两棵树是否相等的比较，相等返回，否则返回其他值，并说明算法复杂度。
数据结构为：
typedef struct_TreeNode{
char c;
TreeNode *leftchild;
TreeNode *rightchild;
}TreeNode;
函数接口为：int CompTree(TreeNode* tree1,TreeNode* tree2);
注：A、B两棵树相等当且仅当Root->c==RootB-->c,而且A和B的左右子树相等

 

这里我用到的是层次遍历两个树,比较如果不一样就退出,这题其实很easy倒是不知道是不是有简单的方法

没有free难得写了

 

 

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

#define MAX 7
 
typedef struct tree
{
   int num;
   struct tree* parent;
   struct tree* lchild;
   struct tree* rchild;
 }TREE;

typedef struct queue
{
 int front;
 int rear;
 TREE** tree;
}QUEUE;

void init_queue(QUEUE** Q)
{
  *Q = (QUEUE*)malloc(sizeof(QUEUE));
  (*Q)->front = 0;
  (*Q)->rear = 0;
  (*Q)->tree = (TREE**)malloc(sizeof(TREE)*MAX);
}

void en_queue(QUEUE* Q,TREE* T)
{
    if((Q->rear + 1)%MAX==Q->front)
     {
      printf("full\n");
      return;
     }
    Q->tree[Q->rear] = T;
    if(++(Q->rear)==MAX)
      Q->rear = 0;
}
    
TREE* de_queue(QUEUE* Q)
{
   TREE* tree = NULL;
  if(Q->front == Q->rear)
    return NULL;
    
  tree = Q->tree[Q->front];
   
  if(++(Q->front)==MAX)
      Q->front = 0;
          
    return tree;
}

int tree_add(TREE** T,TREE* parent,int num)
{
   if(*T == NULL)
    {
       printf("add %d\n",num);
       *T = (TREE*)malloc(sizeof(TREE));
      (*T)->num = num;
      (*T)->parent = parent;
      (*T)->lchild = NULL;
      (*T)->rchild = NULL;
      return 0;
     }
    else if((*T)->num <= num)
     return tree_add(&((*T)->rchild),*T,num);
    else
     return tree_add(&((*T)->lchild),*T,num);
}

int init_tree(TREE** T,int A[])
{
  int i= 0;
  for(;i<MAX;i++)
    tree_add(T, NULL, A[i]);
  
  return 0;
}

int judge_equal_tree(TREE* T1, QUEUE* Q1, TREE* T2, QUEUE* Q2)
{
  int ret;
  
  while(T1!=NULL && T2!=NULL)
  {
   printf("num1:%d\tnum2:%d\n", T1->num, T2->num);
   if(T1->num != T2->num)
    {
      ret = -1;
      break;
     }
     
   if((T1->lchild != NULL) &&(T2->lchild != NULL))
    {
     en_queue(Q1,T1->lchild);
     en_queue(Q2,T2->lchild);
     }
     
   if((T1->rchild != NULL) &&(T2->rchild != NULL))
     {
      en_queue(Q1,T1->rchild);
      en_queue(Q2,T2->rchild);
      }
      
    T1 = de_queue(Q1);
    T2 = de_queue(Q2);
   }
   
   if((T1 == NULL)&&(T2 == NULL))
      ret = 0;
      
   return ret;
}


int main(int argc, char *argv[])
{
  TREE* T1 = NULL;
  TREE* T2 = NULL;
  QUEUE* Q1 = NULL;
  QUEUE* Q2 = NULL;
  
  int A[] = { 50, 30, 60, 10, 40, 55, 80};
  int B[] = { 50, 30, 60, 20, 40, 55, 80};
  init_tree( &T1, A);
  init_tree( &T2, B);
  
  init_queue(&Q1);
  init_queue(&Q2);
  
  if(judge_equal_tree( T1, Q1, T2, Q2) == -1)
    printf("tree T1 and tree T2 not euqal\n");
  else
    printf("tree T1 and tree T2 euqal\n");
   
  
  system("PAUSE");    
  return 0;
}