Trong hướng dẫn này, chúng ta sẽ học cách tìm độ sâu của cây n-ary.
An n-ary cây là cây trong đó mỗi nút của cây có không quá n các nút con.
Chúng ta phải tìm độ sâu của cây n-ary. Chúng tôi sẽ sử dụng vectơ để lưu trữ các nút con của mỗi nút trong cây.
Hãy xem các bước để giải quyết vấn đề.
-
Khởi tạo cây bằng dữ liệu giả.
-
Viết một hàm đệ quy để tìm độ sâu của cây n-ary.
-
Khởi tạo một biến để lưu trữ độ sâu tối đa của cây.
-
Lặp lại các nút con của mỗi nút.
-
Độ sâu tối đa là giá trị lớn nhất của độ sâu tối đa hiện tại và độ sâu của nút con.
-
Nếu chúng tôi giả định biến độ sâu tối đa là maxDepth và maxDepth =max (maxDepth, findDepthOfTree (* con) là câu lệnh đệ quy để tìm độ sâu của cây.
-
-
Độ sâu tối đa cuối cùng của cây là maxDepth + 1 .
-
-
In độ sâu tối đa của cây.
Ví dụ
Hãy xem mã.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
vector<Node *> child;
};
Node *newNode(int data) {
Node *temp = new Node;
temp->data = data;
return temp;
}
int findDepthOfTree(struct Node *node) {
if (node == NULL) {
return 0;
}
int maxDepth = 0;
for (vector<Node*>::iterator it = node->child.begin(); it != node->child.end(); it++) {
maxDepth = max(maxDepth, findDepthOfTree(*it));
}
return maxDepth + 1;
}
int main() {
Node *root = newNode(1);
root->child.push_back(newNode(2));
root->child.push_back(newNode(3));
root->child.push_back(newNode(4));
root->child[2]->child.push_back(newNode(1));
root->child[2]->child.push_back(newNode(2));
root->child[2]->child.push_back(newNode(3));
root->child[2]->child.push_back(newNode(4));
cout << findDepthOfTree(root) << endl;
return 0;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
3
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.