หาความลึกของ N-ary Tree ใน C++

บทนำ

N-ary Tree คือต้นไม้ที่แต่ละโหนดมีลูกได้สูงสุด N ตัว (Binary Tree คือกรณี N=2) ใช้ vector เก็บลูกของแต่ละโหนด

ขั้นตอนการแก้ปัญหา

1. กำหนดโครงสร้างโหนด มี vector<Node*> child
2. สร้างต้นไม้ตัวอย่าง
3. เขียนฟังก์ชัน Recursive หาความลึก
4. ความลึกของโหนด = 1 + max(ความลึกของลูกทุกตัว)
5. โหนดว่าง (NULL) มีความลึก 0

ตัวอย่างโค้ด

#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

โครงสร้างต้นไม้ตัวอย่าง

        1 (depth 1)
      / | \
     2  3  4 (depth 2)
           / | | \
          1 2 3 4 (depth 3)

สรุป

อัลกอริทึมเดียวกับ Binary Tree แต่วนลูป vector child แทนการเรียก left/right แยกกัน ใช้ได้กับ General Tree ทุกประเภท