Отображение узлов двоичного дерева поиска, которому принадлежит путь глубины дерева
У меня есть метод в 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
На данный момент это дает мне частичное решение (исключая корень и принимая во внимание узел, который не является частью этого пути).
Может кто-нибудь помочь мне исправить этот код?
Кроме того, любые другие комментарии о реализации также будут отличными.
Решение
Вы должны убедиться, что когда он вызывает 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 раза.
Другие решения
Других решений пока нет …