kết quả từ 1 tới 2 trên 2

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

  1. #1
    Ðến Từ
    Bình Định
    Thành Viên Thứ: 219047
    Giới tính: Nam
    Bài gửi
    1.249

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

    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;
       }
    }
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 254013
    Giới tính: Nam
    Bài gửi
    165

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

    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; }
    Cái này sai không ?

Nhãn