Для BST:
- Возьмите первые элементы обоих массивов и сопоставьте.Если не равны, то BST не будут одинаковыми.
- Найдите первых левых потомков , которые не были отсканированы (в позициях leftPos1 и leftPos2) и сопоставьте.Если не совпадают, то BST не совпадают.
- Найдите первых правых потомков , которые не были отсканированы (в позициях rightPos1 и rightPos2) и сопоставьте.Если не совпадают, то BST не совпадают.
- Если оба левых и правых потомка совпадают, рекурсивно выполняются одни и те же операции над двумя парами sublists / subtree (из leftPos1 и leftPos2) и (из rightPos1 и rightPos2).Родителем этого поддерева является первый элемент массива.
При поиске левого и правого дочерних элементов в подсписке могут быть элементы, которые уже отсканированы.Чтобы найти такие элементы, убедитесь, что этот элемент является дочерним элементом текущего поддерева.Если текущее поддерево находится слева от родителя, то сравните элемент с родителем, если он принадлежит правой стороне, тогда игнорируйте этот элемент.
#include <stdio.h>
#define BOOL int
#define TRUE 1
#define FALSE 0
BOOL isLeft(int parent, int child) {
return child <= parent;
}
BOOL isRight(int parent, int child) {
return child > parent;
}
BOOL isBelongToChild(int parent, int child, int value) {
if (isLeft(parent, child) && (isLeft(parent, value))) {
return TRUE;
}
if (isRight(parent, child) && (isRight(parent, value))) {
return TRUE;
}
return FALSE;
}
int getLeftPosition(int * array, int size, int parent, BOOL parentExists) {
int i;
int first = *array;
for (i = 1; i < size; i++) {
int value = *(array + i);
if (! isBelongToChild(parent, first, value)) {
continue;
}
if (isLeft(first, value)) {
return i;
}
}
return -1;
}
int getRightPosition(int * array, int size, int parent, BOOL parentExists) {
int i;
int first = *array;
for (i = 1; i < size; i++) {
int value = *(array + i);
if (! isBelongToChild(parent, first, value)) {
continue;
}
if (isRight(first, value)) {
return i;
}
}
return -1;
}
BOOL areSame(int * array1, int pos1, int * array2, int pos2) {
if (pos1 == -1 && pos2 == -1) {
return TRUE;
} else if (*(array1 + pos1) == *(array2 + pos2)) {
return TRUE;
} else {
return FALSE;
}
}
BOOL isSameBst(int * array1, int size1, int * array2, int size2, int parent, BOOL parentExists) {
if (0 == size1 && 0 == size2) {
return TRUE;
}
if (*array1 != *array2) {
return FALSE;
}
int leftPos1 = getLeftPosition(array1, size1, parent, parentExists);
int leftPos2 = getLeftPosition(array2, size2, parent, parentExists);
if (! areSame(array1, leftPos1, array2, leftPos2)) {
return FALSE;
}
int rightPos1 = getRightPosition(array1, size1, parent, parentExists);
int rightPos2 = getRightPosition(array2, size2, parent, parentExists);
if (! areSame(array1, rightPos1, array2, rightPos2)) {
return FALSE;
}
if (leftPos1 > -1) {
int result = isSameBst((array1 + leftPos1), size1 - leftPos1, (array2 + leftPos2), size2 - leftPos2, *array1, TRUE);
if (FALSE == result) {
return FALSE;
}
}
if (rightPos1 > -1) {
int result = isSameBst((array1 + rightPos1), size1 - rightPos1, (array2 + rightPos2), size2 - rightPos2, *array1, TRUE);
if (FALSE == result) {
return FALSE;
}
}
return TRUE;
}
int main ()
{
int a[] = { 5, 6, 2, 7, 4 };
int b[] = { 5, 6, 7, 2, 4 };
printf ("%s\n", (isSameBst(a, 5, b, 5, 0, FALSE) ? "yes" : "no"));
return 0;
}