ในบทช่วยสอนนี้ เราจะเรียนรู้วิธีค้นหาความลึกของต้นไม้ n-ary
น-อารี tree คือ ต้นไม้ที่แต่ละโหนดของต้นไม้มีไม่เกิน n โหนดย่อย
เราต้องหาความลึกของต้นไม้ n-ary เราจะใช้เวกเตอร์เพื่อเก็บลูกของแต่ละโหนดในทรี
มาดูขั้นตอนการแก้ปัญหากัน
-
เริ่มต้นต้นไม้ด้วยข้อมูลจำลอง
-
เขียนฟังก์ชันแบบเรียกซ้ำเพื่อค้นหาความลึกของทรี n-ary
-
เริ่มต้นตัวแปรเพื่อเก็บความลึกสูงสุดของต้นไม้
-
วนซ้ำบนชายน์ของแต่ละโหนด
-
ความลึกสูงสุดคือค่าสูงสุดของความลึกสูงสุดในปัจจุบันและความลึกของโหนดลูก
-
หากเราถือว่าตัวแปรความลึกสูงสุดคือ maxDepth และ maxDepth =max(maxDepth, findDepthOfTree(*children) เป็นคำสั่งแบบเรียกซ้ำเพื่อหาความลึกของต้นไม้
-
-
ความลึกสูงสุดของต้นไม้คือ ความลึกสูงสุด + 1 .
-
-
พิมพ์ความลึกสูงสุดของต้นไม้
ตัวอย่าง
มาดูโค้ดกันเลย
#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;
} ผลลัพธ์
หากคุณเรียกใช้โค้ดด้านบน คุณจะได้ผลลัพธ์ดังต่อไปนี้
3
บทสรุป
หากคุณมีข้อสงสัยใดๆ ในบทแนะนำ โปรดระบุในส่วนความคิดเห็น
