두 갈래 나무의 균형, 완전한 두 갈래 나무, 두 갈래 정렬 나무를 판단하다

// 
int isBalanced(Node* t)  
{ 
    if(t==NULL) return 1; 
    int leftDepth = TreeDepth(t->left); 
    int rightDepth = TreeDepth(t->right); 
    if(abs(leftDepth-rightDepth) > 1) 
        return 0; 
    else 
        return isBalanced(t->left) && isBalanced(t->right); 
}

// 
int CompTree(Node* tree1, Node* tree2)
{
    if(tree1==NULL && tree2==NULL)
        return 1;
    else if(tree1==NULL || tree2==NULL)
        return 0;
    if(tree1->data != tree2->data)
        return 0;
    if(CompTree(tree1->left,tree2->left)==1 && CompTree(tree1->right,tree2->right)==1)
        return 1;
    // 
    if(CompTree(tree1->left,tree2->right)==1 && CompTree(tree1->right,tree2->left)==1)
        return 1;
    return 0;
}

// 
void CopyTree(Node* s,Node* & d)
{
     if(s==NULL) d = NULL;
     Node* temp = new Node;
     temp->data = s->data;
     if(d==NULL) d = temp;
     if(s->left) CopyTree(s->left,d->left);
     if(s->right) CopyTree(s->right,d->right);
}

// ： ， 。 ， ， ， 
int ComplateTree(Node* bt)
{
    Node* p=bt;
    queue<Node*> q;
    int tag=0;
    if(p==NULL) return 1;
    q.push(p);
    while(!q.empty())
    {
         p=q.front(); q.pop(); 
         if(p->left && !tag) q.push(p->left);
         else if(p->left)  return 0;
         else tag=1;
         if(p->right && !tag) q.push(p->right);
         else if(p->right)  return 0;
         else tag=1;
    }
    return 1;
}

// （BST）：  
bool IsBinarySortTree ( BinTree bt )
{
  InitStack(S);
  p = bt;  pre = 0;   // pre p 
  while ( p or ! StackEmpty(S) ) 
  {
    if ( p ) 
    {
      Push(S, p);
      p = p->lchild;
    } 
    else 
    {
      p = Pop(S);
      if ( pre and (p->data <= pre->data) )  return false;  //  
      pre = p;   //  
      p = p->rchild;
    }
  }
  return true;  //  
}

// （BST）： ， ， ， BST， BST
bool IsBST(Node* T)
{
    Queue q;Node* p;
    if(T==NULL) return true;
    EnQueue(q,T);
    while(!empty(Q))
    {
        p=Dequeue(Q);
        if(p->left)
          if(p->data < p->left->data)
             return false;
          else EnQueue(Q,p->left);
        if(p->right)
          if(p->data > p->right->data)
             return false;
          else EnQueue(Q,p->right);
    }
    return true;
}