Two ways to determine whether two binary trees are similar

Name: Determines whether two 2-tree branches are similar

The two methods here are 1 non-recursive, 1 recursive algorithm. In fact, the basic idea of the two algorithms is the same, which is to determine whether two nodes in the same position are both empty or not. But the specific implementation is not one.

For the hierarchical traversal calendar: this is a mistake and should be used as a queue to arrange the next level of elements. Askew, here with the stack can also be, but the node order is not a kind of judgment. In the case of queues, from left to right of each tier. Stack, right to left. It doesn't matter here. I'm going to, if I find a point where I want to access a layer 1 element from right to left, I should use a stack.

For recursion, it looks a lot easier than for non-recursion. The basic idea is simple. Note that the program needs to receive similar information from the subtree. In this case, one problem is that you have to wait until the tree is fully determined before you can finally return. Unlike the above, the process found not one can be returned immediately.

// The hierarchical traversal calendar determines whether two trees are similar 
bool IsSemblable1(BiTree T1,BiTree T2)
{
  stack<BiTNode* > _sta1,_sta2;  // For storage 1 A container for layer elements, where stacks and queues can be both 
  BiTNode *p1 = T1,*p2 = T2;   //p1 Used to track T1,p2 Used to track T2
  while((_sta1.empty() == false || p1 != NULL) &&(_sta2.empty() == false || p2 != NULL))
  {
    if(p1 != NULL && p2 != NULL )  // if p1 and p2 None of them are empty 
    {
      if(p1->lchild != NULL && p2->lchild != NULL)  // if p1 and p2 None of the left subtrees is empty 
      {
        _sta1.push(p1->lchild);
        _sta2.push(p2->lchild);
      }
      else if( p1->lchild != NULL || p2->lchild != NULL)  // if p1 The left subtree is empty, but p2 The left subtree is not empty, or vice versa 
        return false;
      if(p1->rchild != NULL && p2->rchild != NULL)   // if p1 and p2 None of the right subtrees is empty 
      {
        _sta1.push(p1->rchild);
        _sta2.push(p2->rchild);
      }
      else if(p1->rchild != NULL || p2->rchild != NULL)  // if p1 The right subtree is empty, but p2 The right subtree is not empty, or vice versa 
        return false;
      // After accessing the current node of the two trees, leave it empty 1 A secondary loop pops an element out of the stack. 
      p1 = NULL;
      p2 = NULL;
    }
    else if(p1 != NULL || p2 != NULL)    // The current node has 1 A null 
      return false;
    else
    {
      // Pop the top element of two trees 
      p1 = _sta1.top();
      p2 = _sta2.top();
      _sta1.pop();
      _sta2.pop();
    }
  }
  return true;
}

// Recursively determine whether two trees are similar 
bool IsSemblable2(BiTree T1,BiTree T2)
{
  bool leftS = false,rightS = false;   // Used to receive information returned by the subtree 
  if(T1 == NULL && T2 == NULL)    // Both nodes are null 
    return true;
  else if(T1 == NULL || T2 == NULL)  // There are 1 None of these nodes are empty 
    return false;
  else
  {
    int leftS = IsSemblable2(T1->lchild,T2->lchild);  // Recurse the left subtree 
    int rightS = IsSemblable2(T1->rchild,T2->rchild);  // Recursive right subtree 
    return leftS && rightS ;  // Returns information for both subtrees 
  }
}

conclusion