алгоритм — C ++ находит самый большой BST в двоичном дереве

Как вы подходите, чтобы иметь самый большой BST в двоичном дереве? с самым большим, я имею в виду: самый высокий.

Я имею в виду эта почта где очень хорошая реализация для поиска, если дерево
BST или нет

bool isBinarySearchTree(BinaryTree * n,
int min=std::numeric_limits<int>::min(),
int max=std::numeric_limits<int>::max())
{
return !n || (min < n->value && n->value < max
&& isBinarySearchTree(n->l, min, n->value)
&& isBinarySearchTree(n->r, n->value, max));
}

Довольно просто реализовать решение, чтобы найти, содержит ли дерево двоичное дерево поиска. я думаю, что следующий метод делает это:

bool includeSomeBST(BinaryTree* n)
{
return includeSomeBST(n->left)  ||  includeSomeBST(n->right) ;

if(n == NULL)
return false ;

return true ;
}

но что, если я хочу самый большой BST? это моя первая идея,

BinaryTree largestBST(BinaryTree* n)
{
if(isBinarySearchTree(n))
return n;

if(!isBinarySearchTree(n->left))
{
if(!isBinarySearchTree(n->right))
if(includeSomeBST(n->right))
return largestBST(n->right);

else if(includeSomeBST(n->left))
return largestBST(n->left);

else
return NULL;

else
return n->right;
}
else
return n->left;
}

но это не говорит о самом большом. я изо всех сил пытаюсь сделать сравнение. как это должно происходить?

Спасибо

0

Решение

Да, ваша функция includeSomeBST неверна. Вы просто проверяете узлы n, n-> left и n-> right, но вы должны проверять узлы рекурсивно.

bool includeSomeBST (BinaryTree * n)
{

  if(!isBinarySearchTree(n))
{

return includeSomeBST(n->left) || includeSomeBST(n->right);
}

if(n==NULL) return false;
return true;

}

1

Другие решения

Вот успешная реализация кода для того же вместе с программой драйвера:

#include <iostream>
using namespace std;

class BinaryTree {
public:
BinaryTree *right;
BinaryTree *left;
int value;
BinaryTree(int value) {
this->value = value;
}
};int max_value(int a, int b) {
if (a > b) {
return a;
} else {
return b;
}
}

int min_value(int a, int b) {
if (a < b) {
return a;
} else {
return b;
}
}

BinaryTree* findLargestBST(BinaryTree *n, int* maxSize, int *max, int *min, bool *is_bst) {
if (n == NULL) {
*maxSize = 0;
*is_bst = true;
return n;
}
int *lc_max_size = new int;
int *rc_max_size = new int;
int *lc_max = new int;
int *lc_min = new int;
int *rc_max = new int;
int *rc_min = new int;
*lc_max = std::numeric_limits<int>::min();
*rc_max = *lc_max;
*lc_min = std::numeric_limits<int>::max();
*rc_min = *lc_min;
BinaryTree* returnPointer;

bool is_curr_bst = true;
BinaryTree* lc = findLargestBST(n->left, lc_max_size, lc_max, lc_min, is_bst);
if (!*is_bst) {
is_curr_bst = false;
}

BinaryTree* rc = findLargestBST(n->right, rc_max_size, rc_max, rc_min, is_bst);
if (!*is_bst) {
is_curr_bst = false;
}

if (is_curr_bst && *lc_max <= n->value && n->value <= *rc_min) {
*is_bst = true;
*maxSize = 1 + *lc_max_size + *rc_max_size;
returnPointer = n;
*max = max_value (n->value, *rc_max);
*min = min_value (n->value, *lc_min);
} else {
*is_bst = false;
*maxSize = max_value(*lc_max_size, *rc_max_size);
if (*maxSize == *lc_max_size) {
returnPointer = lc;
} else {
returnPointer = rc;
}
*max = *min = n->value;
}

delete lc_max_size;
delete rc_max_size;
delete lc_max;
delete lc_min;
delete rc_max;
delete rc_min;
return returnPointer;
}

int main() {

/* Let us construct the following Tree
50
/      \
10        60
/  \       /  \
5   20    55    70
/     /  \
45     65    80
*/

BinaryTree *root = new BinaryTree(50);
root->left        = new BinaryTree(10);
root->right       = new BinaryTree(60);
root->left->left  = new BinaryTree(5);
root->left->right = new BinaryTree(20);
root->right->left  = new BinaryTree(55);
root->right->left->left  = new BinaryTree(45);
root->right->right = new BinaryTree(70);
root->right->right->left = new BinaryTree(65);
root->right->right->right = new BinaryTree(80);

/* The complete tree is not BST as 45 is in right subtree of 50.
The following subtree is the largest BST
60
/  \
55    70
/     /  \
5     65    80
*/

int *maxSize = new int;
int *min_value = new int;
int *max_value = new int;
*min_value = std::numeric_limits<int>::max();
*max_value = std::numeric_limits<int>::min();
bool *is_bst = new bool;
BinaryTree *largestBSTNode = findLargestBST(root, maxSize, max_value, min_value, is_bst);
printf(" Size of the largest BST is %d", *maxSize);
printf("Max size node is %d", largestBSTNode->value);
delete maxSize;
delete min_value;
delete max_value;
delete is_bst;
getchar();

return 0;
}

Используемый подход довольно прост и может быть понят следующим образом:

Это подход снизу вверх а не сверху вниз, который мы используем при определении, является ли дерево BST или нет. Он использует тот же самый макс-мин подход, который используется при определении дерева как BST или нет.

Ниже приведены шаги, которые выполняются на каждом из узлов рекурсивным способом:
Примечание: пожалуйста, помните, что это подход снизу вверх, и информация будет перетекать снизу вверх.

1) Определить, существую ли я или нет. Если я не (я ноль), я не должен влиять на алгоритм в любом случае и должен вернуться без каких-либо изменений.

2) На каждом узле сохраняется максимальный размер BST до этой точки. Это определяется с использованием общего размера левого поддерева + общий размер правого поддерева + 1 (для самого узла), если дерево в этом конкретном узле удовлетворяет свойству BST. В противном случае он вычисляется по максимальным значениям, которые были возвращены из левого поддерева и правого поддерева.

3) В случае, если свойство BST удовлетворяется в данном узле, тогда текущий узел возвращается как максимальный размер BST до этой точки, в противном случае он определяется из левого и правого поддеревьев.

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector