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

1）给定包含完整二叉树元素的两个数组（逐级），在不重建树的情况下（即仅在数组中进行交换），如何确定这两个数组是否同构？
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

最佳答案

对于第一个问题：
一点符号：
t0，t1-树
值（t）-存储在节点上的数字
左（t）-左子树
右（t）-右子树
t1和t2是同构的，iff
t1和t2为空，
或value (t1) == value (t2)
和
left(t1)与left(t2)同构，right(t1)与right(t2)同构，
或者left(t1)与right(t2)同构，right(t1)与left(t2)同构
假设树存储在数组中，元素0是根，如果t是内部节点的索引，而2t+1是其直系子节点的索引，则直接实现：

#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;
}

对于第二个问题，在每个步骤中，我们比较了2t+2的子树与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);
}

关于algorithm - 查找数组表示的2个BST是否同构，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8040898/