поэтому мне нужно написать функцию в C++, которая возвращает глубину дерева. Im немного confussed относительно того, что это влечет за собой. Это глубина каждого отдельного узла или это глубина всего дерева, например дерево имеет 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);
};
Пожалуйста, не делайте домашнее задание OP для них. –
Простите? Не знаю – average
Кроме того, использование макроса здесь значительно снижает эффективность кода. –
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;
};
Это обычно относится к глубине всего дерева. Но будьте осторожны, деревья могут быть неравномерными по глубине, т. Е. У вашего дерева могут быть листья на глубине 3, а некоторые на глубине 4, в этом случае глубина дерева будет равна 4. – us2012
Возможно, вам придется ознакомиться с определением " глубина дерева "? – taocp
Хорошей идеей является обновление значений глубины и узлов при добавлении или перемещении новых узлов. –