เส้นผ่านศูนย์กลางของไบนารีทรีใน O (n) [วิธีการใหม่] ใน C ++?

เส้นผ่านศูนย์กลางของไบนารีทรีคือ (left_height + right_height + 1) สำหรับแต่ละโหนด ดังนั้นในวิธีนี้ เราจะคำนวณ (left_height + right_height + 1) สำหรับแต่ละโหนดและอัปเดตผลลัพธ์ ความซับซ้อนของเวลาอยู่ที่นี่ O(n)

ให้เรากำหนดโครงสร้างที่จะเป็นตัวแทนของโหนดต้นไม้ที่มีข้อมูลและโหนดลูกของโหนดซ้ายและขวา หากนี่เป็นโหนดแรกที่สร้างขึ้น แสดงว่าเป็นโหนดรูท มิฉะนั้นจะเป็นโหนดย่อย

struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};

ต่อไป เราสร้างฟังก์ชัน newNode(int data) ที่ใช้ค่า int และกำหนดให้กับสมาชิกข้อมูลของโหนด ฟังก์ชันจะส่งกลับตัวชี้ไปยังโหนดโครงสร้างที่สร้างขึ้น นอกจากนี้ ลูกซ้ายและขวาของโหนดที่สร้างขึ้นใหม่จะถูกตั้งค่าเป็นโมฆะ

struct Node* newNode(int data){
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->leftChild = newNode->rightChild = NULL;
   return (newNode);
}

ฟังก์ชันเส้นผ่านศูนย์กลาง (โหนด * รูท) รับโหนดรูทและตรวจสอบว่าโหนดรูทเป็นโมฆะหรือไม่ จากนั้นเราจะกำหนดตัวแปร ans ด้วยค่า INT_MIN ค่าที่ส่งคืนจาก height(root, ans) จะถูกเก็บไว้ที่ตัวแปร height_of_tree ans ถูกส่งกลับจากฟังก์ชัน

int diameter(Node* root){
    if (root == NULL)
        return 0;
    int ans = INT_MIN;
    int height_of_tree = height(root, ans);
    return ans;
}

ฟังก์ชัน height(Node* root, int&ans) รับโหนดรูทและตัวแปร ans โดยการอ้างอิง จากนั้น เราดำเนินการข้ามผ่านแบบไม่เรียงลำดับบนทรีเพื่อคำนวณความยาวของทรีย่อยแต่ละรายการ และค่า maxValue ของ ans จะถูกส่งผ่านเป็นพารามิเตอร์ที่สองในการเรียกซ้ำแต่ละครั้ง ans คือค่าสูงสุดของ (ans, 1 + left_height + right_height)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อค้นหาเส้นผ่านศูนย์กลางของไบนารีทรีในวิธี O(n)

#include <iostream>
using namespace std;
struct Node {
    int data;
    Node* leftChild, *rightChild;
};
struct Node* newNode(int data){
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->leftChild = newNode->rightChild = NULL;
   return (newNode);
}
int height(Node* root, int& ans){
   if (root == NULL)
      return 0;
   int left_height = height(root->left, ans);
   int right_height = height(root->right, ans);
   ans = max(ans, 1 + left_height + right_height);
   return 1 + max(left_height, right_height);
}
int diameter(Node* root){
   if (root == NULL)
      return 0;
   int ans = INT_MIN;
   int height_of_tree = height(root, ans);
   return ans;
}
int main(){
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    printf("Diameter is %d\n", diameter(root));
    return 0;
}

ผลลัพธ์

รหัสข้างต้นจะสร้างผลลัพธ์ต่อไปนี้ -

Diameter is 4