Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Cây tìm kiếm nhị phân - Cài đặt bằng con trỏ

Share

admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 35
Đến từ : Cần Thơ

Cây tìm kiếm nhị phân - Cài đặt bằng con trỏ

Bài gửi  admin on Mon Apr 05, 2010 11:34 am

CÂY TÌM KIẾM NHỊ PHÂN


1. Định nghĩa
Cây tìm kiếm nhị phân (TKNP) là cây nhị phân mà khoá tại mỗi nút cây lớn hơn khoá của tất cả các nút thuộc cây con bên trái và nhỏ hơn khoá của tất cả các nút thuộc cây con bên phải.

Lưu ý: dữ liệu lưu trữ tại mỗi nút có thể rất phức tạp như là một record chẳng hạn, trong trường hợp này khoá của nút được tính dựa trên một trường nào đó, ta gọi là trường khoá. Trường khoá phải chứa các giá trị có thể so sánh được, tức là nó phải lấy giá trị từ một tập hợp có thứ tự.

Qui ước: Cũng như tất cả các cấu trúc khác, ta coi cây rỗng là cây TKNP
Nhận xét:
- Trên cây TKNP không có hai nút cùng khoá.
- Cây con của một cây TKNP là cây TKNP.

2. Duyệt cây nhị phân
Ta có thể áp dụng các phép duyệt cây tổng quát để duyệt cây nhị phân. Tuy nhiên vì cây nhị phân là cấu trúc cây đặc biệt nên các phép duyệt cây nhị phân cũng đơn giản hơn. Có ba cách duyệt cây nhị phân thường dùng (xem kết hợp với hình III.13):
- Duyệt tiền tự (Node-Left-Right): duyệt nút gốc, duyệt tiền tự con trái rồi duyệt tiền tự con phải.
- Duyệt trung tự (Left-Node-Right): duyệt trung tự con trái rồi đến nút gốc sau đó là duyệt trung tự con phải.
- Duyệt hậu tự (Left-Right-Node): duyệt hậu tự con trái rồi duyệt hậu tự con phải sau đó là nút gốc.

3. Tìm kiếm một nút có khóa cho trước trên cây TKNP
Để tìm kiếm 1 nút có khoá x trên cây TKNP, ta tiến hành từ nút gốc bằng cách so sánh khoá của nút gốc với khoá x.
- Nếu nút gốc bằng NULL thì không có khoá x trên cây.
- Nếu x bằng khoá của nút gốc thì giải thuật dừng và ta đã tìm được nút chứa khoá x.
- Nếu x lớn hơn khoá của nút gốc thì ta tiến hành (một cách đệ qui) việc tìm khoá x trên cây con bên phải.
- Nếu x nhỏ hơn khoá của nút gốc thì ta tiến hành (một cách đệ qui) việc tìm khoá x trên cây con bên trái.

4. Cài đặt
Có nhiều cách cài đặt theo dữ liệu có cấu trúc, tùy vào sở thích và quan điểm của từng người về danh sách có đầu hoặc không đầu. Sau đây là chương trình rất đơn giản và dễ hiểu:

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;

//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(Node**k,Node*p) {
   if (p->info < (*k)->info ) {
      if((*k)->Left)
         InsertNode(&(*k)->Left,p);
      else
         (*k)->Left = p;
   }
   else
   if (p->info > (*k)->info){
      if((*k)->Right)
         InsertNode(&(*k)->Right,p);
      else
         (*k)->Right = p;
   }
}
//Thu tuc them node cho cay ban dau
void PushNode(Node**k,int x) {
   Node*p = MakeNode(x);
   if (*k == NULL)
      *k = p;
   else
      InsertNode(&*k,p);
}
//Nhap cac Node vao cay
void Tree(Node**k) {
   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(&*k,x);
   } while(x != 0);
}
//Duyet tien to
void NLR(Node* k) {
   if(k != NULL) {
      printf("%4d",k->info);
      NLR(k->Left);
      NLR(k->Right);
   }
}
//Duyet trung to
void LNR(Node* k) {
   if(k != NULL) {
      LNR(k->Left);
      printf("%4d",k->info);
      LNR(k->Right);
   }
}
//Duyet hau to
void LRN(Node* k) {
   if(k != NULL) {
      LRN(k->Left);
      LRN(k->Right);
      printf("%4d",k->info);
   }
}
//Ham tim kiem nhi phan neu tim thay tra ve 1 nguoc lai 0
char Search(Node*k,int x) {
   Node*temp = k;
   while (temp != NULL ) {
      if (temp -> info == x)
         return 1;
      else
      {
         if (temp -> info > x)
            temp = temp -> Left;
         else
            temp = temp -> Right;
      }
   }
   return 0;
}
//Chuong trinh chinh
void main() {
   Node* T = NULL;   //Khoi tao cay ban day
   int n;

   clrscr();
   Tree(&T);

   printf("\nGia tri cua cay khi duyet NLR.\n");
   NLR(T);

   printf("\nGia tri cua cay khi duyet LNR.\n");
   LNR(T);

   printf("\nGia tri cua cay khi duyet LRN.\n");
   LRN(T);

   printf("\nBan muon tim phan tu gi trong cay? ");
   scanf("%d",&n);
   if ( Search(T,n) == 0 )
      printf("\nPhan tu %d khong co trong cay nhi phan tim kiem.\n",n);
   else
      printf("\nPhan tu %d co trong cay nhi phan tim kiem.\n",n);

   getch();
}

Bạn có thể viết ngắn hơn:
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 *k,Node*p) {
   if (p->info < (*k)->info ) {
      if((*k)->Left)
         InsertNode(&(*k)->Left,p);
      else
         (*k)->Left = p;
   }
   else
   if (p->info > (*k)->info){
      if((*k)->Right)
         InsertNode(&(*k)->Right,p);
      else
         (*k)->Right = p;
   }
}
//Thu tuc them node cho cay ban dau
void PushNode(Tree *k,int x) {
   Tree p = MakeNode(x);
   if (*k == NULL)
      *k = p;
   else
      InsertNode(&*k,p);
}
//Nhap cac Node vao cay
void InputTree(Tree *k) {
   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(&*k,x);
   } while(x != 0);
}
//Duyet tien to
void NLR(Tree k) {
   if(k != NULL) {
      printf("%4d",k->info);
      NLR(k->Left);
      NLR(k->Right);
   }
}
//Duyet trung to
void LNR(Tree k) {
   if(k != NULL) {
      LNR(k->Left);
      printf("%4d",k->info);
      LNR(k->Right);
   }
}
//Duyet hau to
void LRN(Tree k) {
   if(k != NULL) {
      LRN(k->Left);
      LRN(k->Right);
      printf("%4d",k->info);
   }
}
//Ham tim kiem nhi phan neu tim thay tra ve 1 nguoc lai 0
char Search(Tree k,int x) {
   Tree temp = k;
   while (temp != NULL ) {
      if (temp -> info == x)
         return 1;
      else
      {
         if (temp -> info > x)
            temp = temp -> Left;
         else
            temp = temp -> Right;
      }
   }
   return 0;
}
//Chuong trinh chinh
void main() {
   Tree T = NULL;   //Khoi tao cay ban day
   int n;

   clrscr();
   InputTree(&T);

   printf("\nGia tri cua cay khi duyet NLR.\n");
   NLR(T);

   printf("\nGia tri cua cay khi duyet LNR.\n");
   LNR(T);

   printf("\nGia tri cua cay khi duyet LRN.\n");
   LRN(T);

   printf("\nBan muon tim phan tu gi trong cay? ");
   scanf("%d",&n);
   if ( Search(T,n) == 0 )
      printf("\nPhan tu %d khong co trong cay nhi phan tim kiem.\n",n);
   else
      printf("\nPhan tu %d co trong cay nhi phan tim kiem.\n",n);

   getch();
}


Được sửa bởi Admin ngày Mon Apr 19, 2010 8:22 am; sửa lần 3.

admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 35
Đến từ : Cần Thơ

SO SÁNH HAI ĐOẠN CODE PHÂN BIỆT SỰ GIỐNG NHAU VÀ KHÁC NHAU

Bài gửi  admin on Mon Apr 05, 2010 2:19 pm

CODE 1:
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;

//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(Node**k,Node*p) {
   if (p->info < (*k)->info ) {
      if((*k)->Left)
         InsertNode(&(*k)->Left,p);
      else
         (*k)->Left = p;
   }
   else
   if (p->info > (*k)->info){
      if((*k)->Right)
         InsertNode(&(*k)->Right,p);
      else
         (*k)->Right = p;
   }
}
//Thu tuc them node cho cay ban dau
void PushNode(Node**k,int x) {
   Node*p = MakeNode(x);
   if (*k == NULL)
      *k = p;
   else
      InsertNode(&*k,p);
}
//Nhap cac Node vao cay
void Tree(Node**k) {
   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(&*k,x);
   } while(x != 0);
}
//Duyet tien to
void NLR(Node* k) {
   if(k != NULL) {
      printf("%4d",k->info);
      NLR(k->Left);
      NLR(k->Right);
   }
}
//Duyet trung to
void LNR(Node* k) {
   if(k != NULL) {
      LNR(k->Left);
      printf("%4d",k->info);
      LNR(k->Right);
   }
}
//Duyet hau to
void LRN(Node* k) {
   if(k != NULL) {
      LRN(k->Left);
      LRN(k->Right);
      printf("%4d",k->info);
   }
}
//Ham tim kiem nhi phan neu tim thay tra ve 1 nguoc lai 0
char Search(Node*k,int x) {
   Node*temp = k;
   while (temp != NULL ) {
      if (temp -> info == x)
         return 1;
      else
      {
         if (temp -> info > x)
            temp = temp -> Left;
         else
            temp = temp -> Right;
      }
   }
   return 0;
}
//Chuong trinh chinh
void main() {
   Node* T = NULL;   //Khoi tao cay ban day
   int n;

   clrscr();
   Tree(&T);

   printf("\nGia tri cua cay khi duyet NLR.\n");
   NLR(T);

   printf("\nGia tri cua cay khi duyet LNR.\n");
   LNR(T);

   printf("\nGia tri cua cay khi duyet LRN.\n");
   LRN(T);

   printf("\nBan muon tim phan tu gi trong cay? ");
   scanf("%d",&n);
   if ( Search(T,n) == 0 )
      printf("\nPhan tu %d khong co trong cay nhi phan tim kiem.\n",n);
   else
      printf("\nPhan tu %d co trong cay nhi phan tim kiem.\n",n);

   getch();
}

CODE 2: code theo CTU.
Code:
/* Chuong trinh minh hoa cay nhi phan tim kiem */

#include "conio.h"
#include "stdio.h"
#include "alloc.h"

typedef int TData;
//Cau truc cua Node
typedef struct TNode{
   TData Data;
   TNode*Left;
   TNode*Right;
};
//Cau truc cay
typedef TNode * TTree;
//Khoi tao cay rong
void MakeNullTree(TTree *T)
{
   (*T) = NULL;
}
//Xac dinh con trai
TTree LeftChild(TTree n)
{
   if (n!=NULL)
      return n->Left;
   else
      return NULL;
}
//Xac dinh con phai
TTree RightChild(TTree n)
{
   if (n!=NULL)
      return n->Right;
   else return NULL;
}

//Duyet tien to
void PreOrder(TTree T)
{
   printf("%d ",T->Data);
   if (LeftChild(T)!=NULL)
      PreOrder(LeftChild(T));
   if(RightChild(T)!=NULL)
      PreOrder(RightChild(T));
}
//Duyet trung to
void InOrder(TTree T)
{
   if(LeftChild(T)!=NULL)
      InOrder(LeftChild(T));
   printf("%d ",T->Data);
   if(RightChild(T)!=NULL)
      InOrder(RightChild(T));
}
//Duyet hau to
void PosOrder(TTree T)
{
   if(LeftChild(T)!=NULL)
      PosOrder(LeftChild(T));
   if(RightChild(T)!=NULL)
      PosOrder(RightChild(T));
   printf("%d ",T->Data);
}
//Thu tuc them 1 khoa vao cay tim kiem nhi phan
void InsertNode(TTree *Root,TData x)
{
   if (*Root == NULL){ /* them nut moi chua khoa x */
      (*Root)=(TNode*)malloc(sizeof(TNode));
      (*Root)->Data = x;
      (*Root)->Left = NULL;
      (*Root)->Right = NULL;
   }
   else
   if (x < (*Root)->Data)
      InsertNode(&(*Root)->Left,x);
   else
   if (x>(*Root)->Data)
      InsertNode(&(*Root)->Right,x);
}
//Nhap cac Node vao cay
void Tree(TTree*k) {
   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)
         InsertNode(&*k,x);
   } while(x != 0);
}
//Ham tim kiem nhi phan neu tim thay tra ve 1 nguoc lai 0
int Search(TTree Root,TData x){
   if (Root == NULL)
      return 0; //khong tim thay khoa x
   else
   if (Root->Data == x) /* tim thay khoa x */
      return 1;
   else
   if (Root->Data < x) //tim thay tren cay nhi phan
      return Search(Root->Right,x); //tim ben phai
   else
      return Search(Root->Left,x);  //tim ben trai
}

//Chuong trinh chinh
void main() {
   TTree T;   //Khoi tao cay ban day
   int n;
   MakeNullTree(&T);
   clrscr();
   Tree(&T);

   printf("\nGia tri cua cay khi duyet NLR.\n");
   PreOrder(T);

   printf("\nGia tri cua cay khi duyet LNR.\n");
   InOrder(T);

   printf("\nGia tri cua cay khi duyet LRN.\n");
   PosOrder(T);

   printf("\nBan muon tim phan tu gi trong cay? ");
   scanf("%d",&n);
   if ( Search(T,n) == 0 )
      printf("\nPhan tu %d khong co trong cay nhi phan tim kiem.\n",n);
   else
      printf("\nPhan tu %d co trong cay nhi phan tim kiem.\n",n);

   getch();
}

Khi bạn hiểu và không nhầm lẫn về 2 đoạn code này, bạn đã hiểu phần nào về con trỏ. Mặc dù nó có nhiều biến hóa như thế nào nhưng nguyên lý nó vẫn là 1.

Các bạn cho mình vài comment nhé! Thanks


Được sửa bởi Admin ngày Mon Apr 05, 2010 3:22 pm; sửa lần 1.

admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 35
Đến từ : Cần Thơ

SO SÁNH HAI HÀM SEARCH

Bài gửi  admin on Mon Apr 05, 2010 2:39 pm

Trong CODE 1 ta có hàm Search không viết theo đệ quy như sau:
Code:
//Ham tim kiem nhi phan neu tim thay tra ve 1 nguoc lai 0
char Search(Node*k,int x) {
   Node*temp = k;
   while (temp != NULL ) {
      if (temp -> info == x)
         return 1;
      else
      {
         if (temp -> info > x)
            temp = temp -> Left;
         else
            temp = temp -> Right;
      }
   }
   return 0;
}

Trong CODE 2 ta có hàm Search viết theo đệ quy như sau:
Code:
//Ham tim kiem nhi phan neu tim thay tra ve 1 nguoc lai 0
int Search(TTree Root,TData x){
   if (Root == NULL)
      return 0; //khong tim thay khoa x
   else
   if (Root->Data == x) /* tim thay khoa x */
      return 1;
   else
   if (Root->Data < x) //tim thay tren cay nhi phan
      return Search(Root->Right,x); //tim ben phai
   else
      return Search(Root->Left,x);  //tim ben trai
}

Từ CODE 2 viết hàm tìm kiếm đệ quy cho CODE 1, và ngược lại từ CODE 1 viết hàm không đệ quy cho CODE 2.

Hãy chứng tỏ khả năng hiểu biết về cấu trúc dữ liệu của mình. Xin cho vài cái Comment nhé. Thanks!

ghhg
Nhập môn
Nhập môn

Tổng số bài gửi : 5
Points : 10
Join date : 29/07/2010

Re: Cây tìm kiếm nhị phân - Cài đặt bằng con trỏ

Bài gửi  ghhg on Fri Jul 30, 2010 8:46 pm

Xin hỏi em có đoạn code thêm phần tử X vào Cây viết bằng đệ qui, em muốn viết không đệ qui thì phải làm sao xin cho hướng giải quyết.



Code:
void InsertNode(KeyType X, Tree *T)
{
   if((*T)==NULL)
   {
      (*T)=(Node*)malloc(sizeof(Node));
      (*T)->Data=X;
      (*T)->Left=NULL;
      (*T)->Right=NULL;      
   }
   else if((*T)->Data==X)
         printf("\n Da co X\n");
       else if((*T)->Data>X)
            InsertNode(X,&(*T)->Left);
           else         
            InsertNode(X,&(*T)->Right);   
}

Sponsored content

Re: Cây tìm kiếm nhị phân - Cài đặt bằng con trỏ

Bài gửi  Sponsored content Today at 7:04 am


    Hôm nay: Fri Dec 09, 2016 7:04 am