algorithm - 查找由数组表示的 2 BST 是否同构

Question

1) 给定 2 个包含完整二叉树元素的数组(逐级)，而无需实际重建树(即仅通过在数组中进行交换)，我如何确定这 2 个数组是否同构？

2) 如果一个同构树形成二叉搜索树，则更好的解决方案。

更新 例如

     5 
    / \
    4  7
   /\  /\
  2  3 6 8

可以用数组表示为 5 4 7 2 3 6 8

同构树是可以通过围绕节点旋转而相互转换的树

     5 
    / \
    4  7
   /\  /\
  2  3 6 8



     5 
    / \
    4  7
   /\  /\
  3  2 6 8



     5 
    / \
    4  7
   /\  /\
  3  2 8 6



     5 
    / \
    7  4
   /\  /\
  8  6 3 2

Answer 1

对于第一个问题:

一些符号:

• t0, t1 - 树
• value(t) - 存储在节点上的数字
• left(t) - 左子树
• right(t) - 右子树

t1 和 t2 是同构的，当且仅当t1 和t2 为空，

或值(t1)==值(t2)

和

或者 left(t1) 同构于 left(t2) 并且 right(t1) 同构于 right(t2 ),

或 left(t1) 同构于 right(t2) 而 right(t1) 同构于 left(t2 )

假设树存储在数组中，元素 0 是根，如果 t 是内部节点 2t+1 和 2t+2 是其直接子项的索引，直接实现:

#include <stdio.h>

#define N 7

int a[] = { 5, 4, 7, 2, 3, 6, 8 };
int b[] = { 5, 7, 4, 6, 8, 2, 3 };

int
is_isomorphic (int t1, int t2)
{
  if (t1 >= N && t2 >= N)
    return 1;

  if (a [t1] != b [t2])
    return 0;

  return ((is_isomorphic (2*t1 + 1, 2*t2 + 1)
           && is_isomorphic (2*t1 + 2, 2*t2 + 2))
          || (is_isomorphic (2*t1 + 1, 2*t2 + 2)
              && is_isomorphic (2*t1 + 2, 2*t2 + 1)));
}

int main ()
{
  printf ("%s\n", (is_isomorphic (0, 0) ? "yes" : "no"));
  return 0;
}

对于第二个问题，在每一步中，我们将a的子树与根较小的子树与b的子树进行比较，然后是子树具有较大根的a 到具有较大根的b 的子树(比a 和b 的当前根更小和更大) )。

int
is_isomorphic_bst (int t1, int t2)
{
  if (t1 >= N && t2 >= N)
    return 1;

  if (a [t1] != b [t2])
    return 0;

  int t1l, t1r, t2l, t2r;
  if (a [2*t1 + 1] < a [t1] && a [t1] < a [2*t1 + 2])
    {
      t1l = 2*t1 + 1;
      t1r = 2*t1 + 2;
    }
  else if (a [2*t1 + 1] > a [t1] && a [t1] > a [2*t1 + 2])
    {
      t1l = 2*t1 + 2;
      t1r = 2*t1 + 1;
    }
  else
    return 0;

  if (b [2*t2 + 1] < b [t2] && b [t2] < b [2*t2 + 2])
    {
      t2l = 2*t2 + 1;
      t2r = 2*t2 + 2;
    }
  else if (b [2*t2 + 1] > b [t2] && b [t2] > b [2*t2 + 2])
    {
      t2l = 2*t2 + 2;
      t2r = 2*t2 + 1;
    }
  else
    return 0;

  return is_isomorphic_bst (t1l, t2l) && is_isomorphic_bst (t1r, t2r);
}