c++ - 二分探索木の深さ

Question

そのため、ツリーの深さを返す関数を C++ で記述する必要があります。これが何を意味するのか、私は少し混乱しています。これは、個々のノードの深さ、またはツリー全体の深さです。たとえば、ツリーには 4 つのレベルがあります。任意の助けをいただければ幸いです

Answer 1

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;
};

Answer 2

ツリーの深さは、最も深いノードのレベルです。それは良い定義のように見えます。そうは言っても、ルートがクラスの属性であるC++のクラスでの実装は次のとおりです。基本的に、左のサブツリーの深さと右のサブツリーの深さを取得し、それら 2 つのうち最大のものを選択します。

#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);
};