Отображение узлов двоичного дерева поиска, которому принадлежит путь глубины дерева

У меня есть метод в Tree класс, который вычисляет глубину бинарного дерева поиска.

Моя дополнительная задача состоит в том, чтобы при расчете глубины дерева также хранить (или сохранять каким-либо образом) узлы, которые находятся на этом пути (от корня до самого удаленного листа).

Например, рассмотрим следующее дерево:

      10
/  \
6    13
/ \     \
4   9     14
/   /
3   8

Мне нужно произвести узлы: 8,9,6,10

у меня есть это Node учебный класс:

class Node {

private:
Node *left;
Node *right;
int value;
public:
Node(int v = 0) : left(NULL) , right(NULL) , value(v) { cout << "Node construcotr      " << endl;}

Node *getLeft() {return this->left;}
void setLeft(Node *n) {this->left = n;}
Node *getRight() {return this->right;}
void setRight(Node *n) {this->right = n;}
int getVal() {return this->value;}

};

А вот и соответствующая часть Tree учебный класс:

class Tree {

private:
Node* root;
vector<int> vec; /*.....*/

int calcDepth(Node *n)
{
if (n == NULL)
return 0;
else
{
int ld = calcDepth(n->getLeft());
int rd = calcDepth(n->getRight());

if (ld > rd)
{
if (n->getLeft() != NULL) vec.push_back(n->getLeft()->getVal());
return ld + 1;
}
else
{
if (n->getRight() != NULL) vec.push_back(n->getRight()->getVal());
return rd + 1;
}
}
} // end of calcDepth

На данный момент это дает мне частичное решение (исключая корень и принимая во внимание узел, который не является частью этого пути).

Может кто-нибудь помочь мне исправить этот код?

Кроме того, любые другие комментарии о реализации также будут отличными.

0

Решение

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

class Tree {

private:
Node* root;
vector<int> vec; /*.....*/

int calcDepth(Node *n,int isInPath)
{
if (n == NULL)
return 0;
else
{
int ld = calcDepth(n->getLeft(),0);
int rd = calcDepth(n->getRight(),0);

if(isInPath){
vec.push_back(n->getVal());
if (ld > rd)
{
calcDepth(n->getLeft(),isInPath);
return ld + 1;
}
else
{
calcDepth(n->getRight(),isInPath);
return rd + 1;
}
}
return max(ld+1,rd+1);
}

} // end of calcDepth

Я добавил переменную isInPath, которая равна 1, если текущий узел находится в пути, и 0, если это узел. Вы будете называть это с рутом и 1.

Он находит максимум из двух, и только тогда вызовы с isInPath == 1. И с этим метондом к вектору будут добавлены только узлы с isInPath == 1.

Я не проверял это, но это должно работать. Вы также можете создать это как частную функцию, а затем общедоступную, используя только значение узла.

Примечание. Это имеет сложность O (N ^ 2). Чтобы сделать это в O (N), вы можете запомнить значения, чтобы не вычислять их 2 раза.

1

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

Других решений пока нет …

По вопросам рекламы [email protected]