รอบความยาวสูงสุดที่สามารถเกิดขึ้นได้โดยการรวมสองโหนดของไบนารีทรีใน C++

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

สำหรับต้นไม้ด้านบน รอบความยาวสูงสุดคือ 1-2-3-4-7-6 หรือ 1-6-7-4-3-2-1 ยาว 6.

ป้อนข้อมูล − ต้นไม้

ผลผลิต − รอบความยาวสูงสุดคือ − 5

คำอธิบาย − ความสูงสูงสุดของทรีย่อยด้านซ้ายคือ 3 และทรีย่อยด้านขวาคือ 1 ความยาวของไซเคิลกลายเป็น 3+1+1=5 รอบคือ 1-2-3-4-6 หรือ 1-6-4-3-2

ป้อนข้อมูล − ต้นไม้

ผลผลิต − รอบความยาวสูงสุดคือ − 7

คำอธิบาย − ความสูงสูงสุดของทรีย่อยด้านซ้ายคือ 3 และแผนผังย่อยด้านขวาคือ 3 ความยาวของไซเคิลกลายเป็น 3+3+1=7 รอบคือ 5-4-2-1-8-7-6 หรือ 5-6-7-8-1-2-4-5

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• สร้างคลาส treenode ที่มีสมาชิกข้อมูลสาธารณะ − ข้อมูล int สำหรับน้ำหนักของโหนด ตัวชี้ treenode ซ้ายและขวาเพื่อชี้ไปยังโหนดอื่นๆ ดังกล่าว

• ฟังก์ชัน newNode(int data) รับข้อมูลเป็นพารามิเตอร์และสร้างโหนดที่มีตัวชี้ซ้ายและขวาเป็น NULL

• สร้างต้นไม้โดยเรียกใช้ฟังก์ชัน newnode()

• ฟังก์ชัน maxheight(treenode* root) ดึงรากของต้นไม้และคืนค่าความสูงสูงสุดของต้นไม้ที่รูท

• ฟังก์ชันนี้จะตรวจสอบว่ารูทเป็น NULL หรือไม่ หมายถึงความสูงเป็น 0 คืนค่า 0

• lheight และ rheight คำนวณความสูงของทรีย่อยซ้ายและขวาของโหนดรูท โดยเรียกซ้ำโดยเรียก maxheight(root->left); และ maxheight(root->right);

• ส่งคืนค่าสูงสุดที่ได้จากการเปรียบเทียบ lheight และ rheight

• ภายใน main เราเก็บค่าความสูงสูงสุดของทรีย่อยด้านซ้ายและแผนผังย่อยด้านขวาของ treeNode

• ตอนนี้ รอบความยาวสูงสุดคือผลรวมของทั้ง maxlheight +maxrheight+1 สำหรับการรวมรูทด้วย

• พิมพ์ความยาวของรอบเป็นผล.

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
//class for tree
class treenode{
public:
   int data;
   treenode* left;
   treenode* right;
};
//find maximum height between left and right subtree of current root
int maxheight(treenode* root){
   if (root == NULL)
      return 0;
   else{
      int lheight = maxheight(root->left);
      int rheight = maxheight(root->right);
      //find maximum height
      if (lheight > rheight)
         return(lheight + 1);
      else
         return(rheight + 1);
      }
   }
   //creating a node of tree
   treenode* newNode(int data){
      treenode* Node = new treenode();
      Node->data = data;
      Node->left = NULL;
      Node->right = NULL;
      return(Node);
}
int main(){
   treenode *root = newNode(6);
   root->left = newNode(8);
   root->right = newNode(9);
   root->left->left = newNode(4);
   root->left->right = newNode(5);
   root->left->right->right = newNode(7);
   root->left->right->right->left = newNode(2);
   int maxlheight=maxheight(root->left);
   int maxrheight=maxheight(root->right);
   int maxlheight=maxDepth(root->left);
   int maxrheight=maxDepth(root->right);
   cout << "Maximum length cycle: " << maxlheight+maxrheight+1;
   return 0;
}

ผลลัพธ์

Maximum length cycle: 6