TỔ TIÊN CHUNG GẦN NHẤT


Giả sử khóa p và q có trên cây T. Thuật toán tìm tổ tiên chung gần nhất được thể hiện như sau:

Code:

int NearRoot(Tree T, int p, int q) {
   if((T->info >=p && T->info <= q) || (T->info >=q && T->info <= p))
      return T->info;
   else
      if(T->info < p && T->info < q)
         return NearRoot(T->Right,p,q);
      else
         return NearRoot(T->Left,p,q);
}

Đây là ý tưởng của bạn Trương Mỹ Thu Thảo.

Chương trình mẫu tham khảo.

Code:

/* Chuong trinh minh hoa cay nhi phan tim kiem */
#include "conio.h"
#include "stdio.h"

//Cau truc cua Node
typedef struct Node {
   int info;
   Node *Left;
   Node *Right;
}Node;
//Dinh nghia cay nhi phan
typedef Node *Tree;
//Khoi tao Node
Node *MakeNode(int x) {
   Node *p = new Node;
   p->info = x;
   p->Left = NULL;
   p->Right = NULL;
   return p;
}
//Them 1 node vao cay tim kiem nhi phan
void InsertNode(Tree *T, Node *p) {
   if (p->info < (*T)->info ) {
      if((*T)->Left)
         InsertNode(&(*T)->Left,p);
      else
         (*T)->Left = p;
   }
   else
   if (p->info > (*T)->info){
      if((*T)->Right)
         InsertNode(&(*T)->Right,p);
      else
         (*T)->Right = p;
   }
}
//Thu tuc them node cho cay ban dau
void PushNode(Tree *T, int x) {
   Tree p = MakeNode(x);
   if (*T == NULL)
      *T = p;
   else
      InsertNode(&*T,p);
}
//Nhap cac Node vao cay
void InputTree(Tree *T) {
   int x;
   printf("Nhap vao cac phan tu trong cay nhi phan tim kiem.\n");
   printf("Nhap so 0 thi ket thuc: ");
   do {
      scanf("%d",&x);
      if (x != 0)
         PushNode(&*T,x);
   } while(x != 0);
}
// Viet ham tim kiem theo de quy
char Search(Tree T,int x) {
   if(T==NULL)
      return 0;
   else
      if(T->info == x)
         return 1;
      else
         if(x > T->info)
            return Search(T->Right,x);
         else
            return Search(T->Left,x);
}
//To tien chung gan nhat
int NearRoot(Tree T, int p, int q) {
   if((T->info >=p && T->info <= q) || (T->info >=q && T->info <= p))
      return T->info;
   else
      if(T->info < p && T->info < q)
         return NearRoot(T->Right,p,q);
      else
         return NearRoot(T->Left,p,q);
}
//Chuong trinh chinh
void main() {
   Tree T = NULL;   //Khoi tao cay ban dau
   int p, q;
   clrscr();
   InputTree(&T);
   printf("Nhap p = ");
   scanf("%d",&p);
   printf("Nhap q = ");
   scanf("%d",&q);
   if( T == NULL||!Search(T,p)||!Search(T,q))
      printf("p va q khong co to tien chung");
   else
      printf("p va q co to tien chung gan nhat la: %d", NearRoot(T,p,q));
   getch();
}