глубина бинарного дерева поиска
поэтому мне нужно написать функцию в c ++, которая возвращает глубину дерева. Я немного сбит с толку относительно того, что это влечет за собой. Это глубина каждого отдельного узла или глубина всего дерева, например, дерево имеет 4 уровня. любая помощь будет оценена
Решение
Глубина дерева — это уровень самого глубокого узла. Это выглядит как хорошее определение. Сказав это, вот реализация в классе в C ++, где root является атрибутом класса. По сути, вы получаете глубину левого поддерева и глубину правого поддерева и выбираете, какой из этих двух будет наибольшим.
#define max(a,b) ((a)>=(b) ? (a) : (b))int height2(Node *t) {
if(!t)
return 0;
int height_left = height2(t->L);
int height_right = height2(t->R);
return 1 + max(height_left,height_right);
};int height() {
return height2(root);
};
Другие решения
class Node {
public:
//...
unsigned int depth() {
return 1 + max(depth(left),
depth(right));
}
private:
unsigned int depth(Node* node) {
return node ? node->depth() : 0;
}
Node* left;
Node* right;
};