Code cơ bản trong cây nhị phân tìm kiếm

aloxinh_nb · 5/12/14

Cây nhị phân là cấu trúc dữ liệu dùng để lưu trữ một tập các dữ liệu có cùng kiểu và các dữ liệu này được lưu trữ không liên tiếp trong bộ nhớ. Mỗi nút (phần tử) trên cây sẽ giữ địa chỉ của nút con bên trái và địa chỉ của nút con bên phải , khi đó chỉ cần biết địa chỉ nút gốc (nút không là con của bất kỳ nút nào ) là có thể truy xuất đến tất cả các nút.

Danh sách liên kết đơn là trường hợp đặc biệt của cây nhị phân mà tất cả các nút chỉ con trái hoặc tất cả các nút chỉ con phải.

Ưu khuyết điểm của cây nhị phân.

Ưu điểm: Có được ưu điểm của danh sách liên kết như là: Thao tác hủy hoặc chèn rất nhanh , có thể cấp phát thêm nút hoặc thu hồi bộ nhớ đã cấp phát cho nút và kích thước cây không bị giới hạn bởi 64 KB.

Có thêm ưu điểm khác là tìm kiếm nhanh (trong khi danh sách liên kết tìm kiếm chậm).

Nhược điểm: Tốn thêm bộ nhớ để lưu trữ địa chỉ nút con trái, con phải.

**** Code xử lý trong cây nhị phân.

I- Khai báo cấu trúc của 1 nút

Mã:

struct node
{
   int data;//Noi dung cua nut
   node *letf , *right;//Dia chi nut trai , nut phai
};
typedef node *nodeptr

II - Khởi tạo cây

Mã:

void init_tree(nodeptr &root)
{
   root = NUll;
}

III - Kiểm tra cây rỗng

Mã:

int empty_tree(nodeptr root)
{
   if(root == NULL)   return 1;

   else return 0;
}

IV - Tạo 1 nút cho cây

Mã:

nodeptr make_node(int x)
{
   noteptr p = new node; 
   p->data = x;
   p->left = p->right = NULL;
   return p;
}

V - Chèn 1 nút vào cây có sẵn

Mã:

nodeptr insert_node(nodeptr &root , int x)
{
   nodeptr p =make_node(x) ;
   nodeptr q,f;
   if(root == NULL)
   {
      root = p;
   }
   else
   {
      root = q;
      f=NULL;
      while(q!=NULL)
      {
         f = q;
         if(x < q ->data)
         {
            q = q->left;
         }
         else
         {
            q = q->right;
         }
      }
      if(x < f->data)
      {
         f->left = p;
      }
      else
      {
         f->right = p;
      }
   }
   return p;
}

VI - Tìm kiếm

Mã:

nodeptr search_node(nodeptr root , int x)
{
   nodeptr p = root;
   while(p!=NULL)
   {
      if(p->data == x)          return p;
      else if(x < p->data)           p = p->left;
               else          p = p->right;
   }
   return NULL;
}

VII - Hàm hủy 1 nút của cây

Mã:

int del_node(nodeptr &root, int x)
{
   nodeptr p, q, f;
   p = root;
   f = NULL;
   while(p!=NULL)
   {
      if(p->data == x)     break;
      else
      {
         f = p;
         if(x<p->data)          p = p->left;
         else          p = p->right;
      }
   }
   if(p==NULL)         return 0;
   else
   {
      if(p->left !=NULL && p->right!=NULL)
      {
         q = p->right;
         f = p;
         while(q->left!=NULL)
         {
            f = q;
            q = q->left;
         }
         p->data = q->data;
         p = q;
      }
      if(p->left!=NULL)          q = p->left;
      else          q = p->right;
      if(p==root)         root = q;
      else
      {
          if(p=f->left)         f->left = q;
         else          f->right = q;
      }
      delete p;
      return 1;
   }
}

VIII - Hàm nhập dữ liệu vào cây

Mã:

void input_tree(nodeptr &root)
{
   int n,x;
   root = NULL;
   printf("\nSo phan tu: ");
   scanf("%d", &n);
   for(int i=1; i<=n; i++)
   {
      printf("Phan tu thu %d: ",i);
      scanf("%d", &x);
      insert_node(root, x);
   }
}

IX - Duyệt cây

//Có 3 cách duyệt cây

//Cách 1 : Node - Left - Right (NLR)
/*trong đó: Node là nút gốc(root)
Left là nút bên trái của nút gốc
Right là nút bên phải của nút gốc */\

Mã:

void NLR(nodeptr root)
{
   if(root!=NULL)
   {
      printf("%d", root->data);
      NLR(root->left);
      NLR(root->right);
   }
}

//Cách 2: Left -Node -Right

Mã:

void LNR(nodeptr root)

{
   if(root!=NULL)
   {
      LNR(root->left);
      printf("%d", root->data);
      LNR(root->right);
   }
}

//Cách 3: Left - Right -Node

Mã:

void LRN(nodeptr root)

{
   if(root!=NULL)
   {
      LNR(root->left);
      printf("%d", root->data);
      LNR(root->right);
   }
}

XX- Hàm hủy cây

Mã:

void del_tree(nodeptr &root)
{
   if(root!=NULL)
   {
      del_tree(root->left);
      del_tree(root->right);
      delete root;
      root = NULL;
   }
}

hieu.29.10.1996 · 23/5/16

Mã:

[COLOR=#000000]nodeptr insert_node(nodeptr &root , int x)[/COLOR]{
   nodeptr p =make_node(x) ;
   nodeptr q,f;
   if(root == NULL)
   {
      root = p;
   }
   else
   {
      root = q;
      f=NULL;
      while(q!=NULL)
      {
         f = q;
         if(x < q ->data)
         {
            q = q->left;
         }
         else
         {
            q = q->right;
         }
      }
      if(x < f->data)
      {
         f->left = p;
      }
      else
      {
         f->right = p;
      }
   }
   return p; [COLOR=#000000]}[/COLOR]

Cái này sai không ?

Code cơ bản trong cây nhị phân tìm kiếm

hieu.29.10.1996

Bài viết mới nhất

Thống kê

Bài viết được quan tâm nhiều