โปรแกรม C++ เพื่อค้นหาบรรพบุรุษร่วมที่ต่ำที่สุดในแผนผังการค้นหาแบบไบนารี

ต้นไม้ไบนารีที่มีลูกไม่เกินสองคน ระบุว่าเป็นลูกซ้ายและขวา นี่คือโปรแกรม C++ เพื่อค้นหาบรรพบุรุษร่วมที่ต่ำที่สุดในไบนารีทรี

อัลกอริทึม

Begin Create a structure n to declare data d, a left child pointer l and a right child pointer r.
   Create a function to create newnode. Call a function LCA() to Find lowest common ancestor in a binary tree:
   Assume node n1 and n2 present in the tree.
   If root is null, then return.
      If root is not null there are two cases.
         a) If both n1 and n2 are smaller than root, then LCA lies in left.
         b) If both n1 and n2 are greater than root, then LCA lies in right.
End.

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

#include<iostream>
using namespace std;
struct n {
   int d;
   struct n* l, *r;
}*p = NULL;
struct n* newnode(int d) {
   p = new n;
   p->d= d;
   p->l = p->r = NULL;
   return(p);
}
struct n *LCA(struct n* root, int n1, int n2) {
   if (root == NULL)
      return NULL;
   if (root->d > n1 && root->d > n2)
      return LCA(root->l, n1, n2);
   if (root->d< n1 && root->d < n2)
      return LCA(root->r, n1, n2);
      return root;
}
int main() {
   n* root = newnode(9);
   root->l = newnode(7);
   root->r = newnode(10);
   root->l->l = newnode(6);
   root->r->l= newnode(8);
   root->r->r = newnode(19);
   root->r->l->r = newnode(4);
   root->r->r->r = newnode(20);
   int n1 = 20, n2 = 4;
   struct n *t = LCA(root, n1, n2);
   cout<<"Lowest Common Ancestor of 20 and 4 is:" <<t->d<<endl;
   n1 = 7, n2 = 6;
   t = LCA(root, n1, n2);
   cout<<"Lowest Common Ancestor of 7 and 6 is:" << t->d<<endl;
}

ผลลัพธ์

Lowest Common Ancestor of 20 and 4 is:9
Lowest Common Ancestor of 7 and 6 is:7