โปรแกรม C++ พิมพ์เส้นทางใบไปยังใบที่ยาวที่สุดในต้นไม้ไบนารี

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมพิมพ์เส้นทางที่ยาวที่สุดที่มีอยู่จากโหนดใบหนึ่งไปยังอีกโหนดใบในต้นไม้ไบนารีที่กำหนด

กล่าวอีกนัยหนึ่ง เราต้องพิมพ์โหนดทั้งหมดที่ปรากฏในเส้นผ่านศูนย์กลาง (diameter) ของต้นไม้ไบนารี ที่นี่ เส้นผ่านศูนย์กลาง (หรือความกว้าง) สำหรับต้นไม้ไบนารีเฉพาะถูกนิยามว่าเป็นจำนวนโหนดในเส้นทางที่ยาวที่สุดจากโหนดปลายหนึ่งไปอีกโหนดปลาย

เพื่อแก้ปัญหานี้ เราคำนวณเส้นผ่านศูนย์กลางของต้นไม้ไบนารีโดยใช้ฟังก์ชันความสูง (height) จากนั้นหาเส้นทางที่ยาวที่สุดในส่วนซ้ายและขวาของต้นไม้ไบนารี สุดท้ายเพื่อพิมพ์โหนดในเส้นผ่านศูนย์กลาง เราพิมพ์โหนดส่วนซ้าย โหนดราก และโหนดส่วนขวา

ตัวอย่าง

#include <bits/stdc++.h> 
using namespace std; 

struct Node { 
    int data; 
    Node *left, *right; 
}; 

struct Node* create_node(int data){ 
    struct Node* node = new Node; 
    node->data = data; 
    node->left = node->right = NULL; 
    return (node); 
} 

int tree_height(Node* root, int& ans, Node*(&k), int& lh, int& rh, int& f){ 
    if (root == NULL) 
        return 0; 
    int left_tree_height = tree_height(root->left, ans, k, lh, rh, f); 
    int right_tree_height = tree_height(root->right, ans, k, lh, rh, f); 
    if (ans < 1 + left_tree_height + right_tree_height){ 
        ans = 1 + left_tree_height + right_tree_height; 
        k = root; 
        lh = left_tree_height; 
        rh = right_tree_height; 
    } 
    return 1 + max(left_tree_height, right_tree_height); 
} 

void print_roottonode(int ints[], int len, int f){ 
    int i; 
    if (f == 0){ 
        for (i = len - 1; i >= 0; i--) { 
            printf("%d ", ints[i]); 
        } 
    } else if (f == 1) { 
        for (i = 0; i < len; i++) { 
            printf("%d ", ints[i]); 
        } 
    } 
} 

void print_pathr(Node* node, int path[], int pathLen, int max, int& f){ 
    if (node == NULL) 
        return; 
    path[pathLen] = node->data; 
    pathLen++; 
    if (node->left == NULL && node->right == NULL) { 
        if (pathLen == max && (f == 0 || f == 1)) { 
            print_roottonode(path, pathLen, f); 
            f = 2; 
        } 
    } else { 
        print_pathr(node->left, path, pathLen, max, f); 
        print_pathr(node->right, path, pathLen, max, f); 
    } 
} 

void calc_diameter(Node* root){ 
    if (root == NULL) 
        return; 
    int ans = INT_MIN, lh = 0, rh = 0; 
    int f = 0; 
    Node* k; 
    int tree_height_of_tree = tree_height(root, ans, k, lh, rh, f); 
    int lPath[100], pathlen = 0; 
    print_pathr(k->left, lPath, pathlen, lh, f); 
    printf("%d ", k->data); 
    int rPath[100]; 
    f = 1; 
    print_pathr(k->right, rPath, pathlen, rh, f); 
} 

int main(){ 
    struct Node* root = create_node(12); 
    root->left = create_node(22); 
    root->right = create_node(33); 
    root->left->left = create_node(45); 
    root->left->right = create_node(57); 
    root->left->right->left = create_node(26); 
    root->left->right->right = create_node(76); 
    root->left->left->right = create_node(84); 
    root->left->left->right->left = create_node(97); 
    calc_diameter(root); 
    return 0; 
}

ผลลัพธ์

97 84 45 22 57 26