有哪些算法可以比较两棵树之间的差异？

Question

我希望在比较两种树结构时找到差异。

节点将是字符串。我想捕获它发生在树的哪个级别。

例如找出这两棵树之间的差异：

Answer 1

基本思想是逐层遍历两棵树。一旦你发现，

节点不相同

或者

节点的结构不同

意味着您在这里发现了不同之处！现在您可以根据需要标记级别或节点。

伪代码：

function getDiff(Tree root, Tree root1){
   Queue queue->push(root);
   Queue queue1->push(root1);
   level = 1;
   while(queue->size() != 0 && queue1->size() != 0){
      if(queue->size() != queue1->size()) {
            PRINT: "THE TREE AREN'T IN SAME STRUCTURE :/";
            return;
      }

      size = queue->size();
      /* traversing both trees level-by-level */
      while(size-- > 0){
           Tree temp = queue->peek();
           Tree temp1 = queue1->peek();

           queue->pop();
           queue1->pop();

            if(!temp->node != temp1->node) {
                  PROCESS: level;
            }
            if(temp->left != null && temp1->left != null) {
                queue->push(temp->left);
                queue1->push(temp1->left);
            }

            if(temp->right!= null && temp1->right!= null) {
                queue->push(temp->right);
                queue1->push(temp1->right);
            }
        }
        /* increase level */
        level += 1;
    }
}

注意：将伪代码更改为您最喜欢的语言:)