[Cấu trúc dữ liệu] Cài đặt thuật toán Cây (Tree ADT) trong C++

Thảo luận trong 'C/C++/C#' bắt đầu bởi Trương Minh Dương, 18/11/15.

Lượt xem: 549

  1. Trương Minh Dương

    Trương Minh Dương Đầy tớ nhân dân

    Bài trước, mình đã giới thiệu tới các bạn các thuật toán đệ quy từ đơn giản đến phức tạp. Tiếp theo là một cấu trúc dữ liệu khác khá phức tạp là Bài toán xây dựng Cây (Tree ADT). Cây là một CTDL gồm nút gốc, các nút lá và đường đi. Để giải quyết bài toán này chúng ta cần tìm hiểu một số khái niệm cơ bản sau.

    • Path (đường đi): một chuỗi các nút u(1)...u(k) trong đó u(i) là nút cha của u(i+1) (∀1 < i < k) là một đường đi từ nút u(1) đến nút u(k) với độ dài (k-1)
    • Ancestor (tổ tiên): Nút u là tổ tiên của nút v nếu có một đường đi xuất phát từ nút u đến nút v
    • Descendant (con cháu): Nút u là con cháu của nút v nếu nút v là tổ tiên của nút u
    • Sibling (anh em): Nút u và nút v được gọi là anh em nếu chúng có cùng nút cha.
    • Leaf (Nút lá): Là nút không có nút con cháu
    • Độ cao của nút v là đường đi dài nhất tính từ nút v đến nút lá cộng thêm 1
    • Độ sâu của nút v là đường đi dài nhất tính từ nút gốc đến nút v cộng thêm 1
    • Giá trị của nút v là thông tin lưu trữ ở trong nút đó
    Trong bài viết này mình sẽ hướng dẫn các bạn cài đặt thuật toán viết cây (Tree ADT) trong C++ từ một file dữ liệu cho trước. Đồng thời sẽ cài đặt các bài toán con như: Xóa 1 nút của cây, xóa cây, thêm nột nút vào cây, tìm kiếm dữ liệu trong cây, tính độ sâu, tính chiều cao của cây, tìm nút cha của một nút bất kì, tính tổng các giá trị của cây,...

    Ý tưởng thuật toán:

    -Chúng ta sẽ tạo ra một file dữ liệu, trong đó chứa giá trị của các nút tương ứng. Sau đó sẽ viết 1 hàm chèn lần lượt các giá trị vào cây.

    Các bạn có thể xem hình dưới để có thể được ý tưởng thuật toán trong bài cài đặt cây trong C++ (Tree ADT)

    [​IMG]


    Giả sử mình có một file dữ liệu như này:

    Mã:
    3 2 1 9 -1
    2 -1
    1 6 7 8 -1
    6 4 -1
    4 -1
    7 -1
    8 5 10 -1
    5 -1
    10 -1
    9 -1
    -1
    Đầu tiên là code chèn các giá trị đó thành một cây theo đúng ý tưởng nhé !!!

    Để là được bài toán này, chúng ta cần khai báo một cấu trúc dữ liệu (struct). Khai báo con trỏ trỏ đến các nút con của một nút cha.

    Mã:
    struct Node{
        int data;
        Node* LeftMostChild; //Nút bên phải nhất
        Node* RightSibling; // Nút bên trái
    };
    
    Node* root; // Khởi tạo nút gốc

    Hàm đọc dữ liệu từ một file txt có sẵn

    Mã:
    void readData(char* fn){
        FILE* f = fopen(fn,"r");
        while(1){
            int v;
            fscanf(f,"%d ",&v);
            if(v==-1) break;
            Node* pv = find(v,root);
            if (pv == NULL){
            pv = new Node;
            pv->data = v;
            pv->LeftMostChild = NULL;
            pv->RightSibling = NULL;
            root = pv;
            }
        while(1){
                int u;
                fscanf(f,"%d ",&u);
                if (u == -1) break;
                insert(u,pv);      
            }
        }  
        fclose(f);
    }
    Hàm chèn giá trị


    http://www.mediafire.com/?nh5g8be463brqnb

    Mã:
    void insert(int u, Node* pv){
        Node* q = new Node;
        q->data = u;
        q->LeftMostChild = NULL;
        q->RightSibling = NULL;
        if (pv->LeftMostChild == NULL){
                pv->LeftMostChild = q;
                return;
        }
        Node* p = pv->LeftMostChild;
        while (p->RightSibling != NULL){
                p = p->RightSibling;
        }
        p->RightSibling = q;
    }
    Hàm tìm kiếm một phần tử trong cây:

    Mã:
    Node* find(int x, Node* r){
        if(r == NULL)return NULL;
        if(r->data == x)return r;
        Node* p = r->LeftMostChild;
        while (p != NULL){
            Node* q = find (x, p);
            if (q != NULL) return q;
            p = p->RightSibling;
        }
        return NULL;
    }
    Hàm đếm các nút trong cây:

    Mã:
    int count (Node* r){
        if (r == NULL) return 0;
        int c = 1;
        Node* p = r->LeftMostChild;
        while(p!=NULL){
            c = c + count(p);
            p = p->RightSibling;
        }
        return c;
    }
    Hàm đếm nút lá trong cây:

    Mã:
    int countLeaves(Node* r){
        if (r == NULL) return 0;
        Node* p = r->LeftMostChild;
        int c = 0;
        if (p != NULL) c = 1;
        while (p != NULL){
            c = c + countLeaves(p);
            p = p->RightSibling;  
        }
        return c;
    }
    Hàm tính tổng giá trị các nút trong cây:

    Mã:
    int sum (Node* r){
        if (r == NULL) return 0;
        Node* p = r->LeftMostChild;
        int s = r->data;
        while(p! = NULL){
            s = s + sum(p);
            p = p->RightSibling;
        }
        return s;
    }

    Hàm tính độ cao của 2 nút bất kì:

    Mã:
    int height (Node* p, Node* r){
        if (p == NULL) return 0;
        if (p == r) return 1;
        int h = 0;
        Node* q = p-> LeftMostChild;
        while (q != NULL) {
            int hq = height(q,p);
            h = h < hq ? hq : h;
            q = q->RightSibling;
        }
        return h+1;
    }

    Hàm tính độ sâu của một nút bất kì:

    Mã:
    int depthbeta(Node* p, Node* q, int h){
        if (q == NULL) return -1;
        Node* qi = q->LeftMostChild;
        while (qi != NULL){
            if (qi == p) return h+1;
            qi = qi->RightSibling;
        }
        qi = q->LeftMostChild;
        while (qi != NULL){
            int hi = depthbeta(p,qi,h+1);
            if (hi > 0) return hi;
            qi = qi->RightSibling;
        }
        return -1;
    }
    
    int depth(Node* p, Node* r){
        if (p == NULL) return 0;
        if (p == r) return 1;
        return depthbeta(p,r,1);
    }
    Hàm tìm nút cha của một nút:

    Mã:
    int parents(Node* p, Node* r){
        if (p == NULL) return -1;
        if (r == NULL) return -1;
        Node* q = r->LeftMostChild;
        while (q != NULL){
            if (q == p) return r->data;
            q = q->RightSibling;
        }
      
        q = r->LeftMostChild;
        while (q != NULL){
            int h = parents(p,q);
            if (h > 0) return h;
            q = q->RightSibling;
        }  
    }
    Hàm duyệt cây theo tứ tự giữa

    Mã:
    void inorder (Node* r){
        if (r == NULL) return;
        Node* p = r->LeftMostChild;
        inorder(p);
        printf ("%d  ", r->data);
        Node* p2;
        if (p != NULL){
            p2 = p->RightSibling;
            while (p2 != NULL){
            inorder(p2);
            p2 = p2->RightSibling;
            }
        }  
    }
    Code hoàn chỉnh của bài cài đặt cây dữ liệu (Tree ADT):

    Mã:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct Node{
        int data;
        Node* LeftMostChild;
        Node* RightSibling;
    };
    
    Node* root;
    
    Node* find(int x, Node* r){
        if(r == NULL)return NULL;
        if(r->data == x)return r;
        Node* p = r->LeftMostChild;
        while (p != NULL){
            Node* q = find (x, p);
            if (q != NULL) return q;
            p = p->RightSibling;
        }
        return NULL;
    }
    
    void insert(int u, Node* pv){
        Node* q = new Node;
        q->data = u;
        q->LeftMostChild = NULL;
        q->RightSibling = NULL;
        if (pv->LeftMostChild == NULL){
                pv->LeftMostChild = q;
                return;
        }
        Node* p = pv->LeftMostChild;
        while (p->RightSibling != NULL){
                p = p->RightSibling;
        }
        p->RightSibling = q;
    }
    
    void readData(char* fn){
        FILE* f = fopen(fn,"r");
        while(1){
            int v;
            fscanf(f,"%d ",&v);
            if(v==-1) break;
            Node* pv = find(v,root);
            if (pv == NULL){
            pv = new Node;
            pv->data = v;
            pv->LeftMostChild = NULL;
            pv->RightSibling = NULL;
            root = pv;
            }
        while(1){
                int u;
                fscanf(f,"%d ",&u);
                if (u == -1) break;
                insert(u,pv);      
            }
        }
          
        fclose(f);
    }
    
    int count (Node* r){
        if (r == NULL) return 0;
        int c = 1;
        Node* p = r->LeftMostChild;
        while(p!=NULL){
            c = c + count(p);
            p = p->RightSibling;
        }
        return c;
    }
    
    int countLeaves(Node* r){
        if (r == NULL) return 0;
        Node* p = r->LeftMostChild;
        int c = 0;
        if (p != NULL) c = 1;
        while (p != NULL){
            c = c + countLeaves(p);
            p = p->RightSibling;  
        }
        return c;
    }
    
    int sum (Node* r){
        if (r == NULL) return 0;
        Node* p = r->LeftMostChild;
        int s = r->data;
        while(p! = NULL){
            s = s + sum(p);
            p = p->RightSibling;
        }
        return s;
    }
    
    int height (Node* p, Node* r){
        if (p == NULL) return 0;
        if (p == r) return 1;
        int h = 0;
        Node* q = p-> LeftMostChild;
        while (q != NULL) {
            int hq = height(q,p);
            h = h < hq ? hq : h;
            q = q->RightSibling;
        }
        return h+1;
    }
    
    int depthbeta(Node* p, Node* q, int h){
        if (q == NULL) return -1;
        Node* qi = q->LeftMostChild;
        while (qi != NULL){
            if (qi == p) return h+1;
            qi = qi->RightSibling;
        }
        qi = q->LeftMostChild;
        while (qi != NULL){
            int hi = depthbeta(p,qi,h+1);
            if (hi > 0) return hi;
            qi = qi->RightSibling;
        }
        return -1;
    }
    
    int depth(Node* p, Node* r){
        if (p == NULL) return 0;
        if (p == r) return 1;
        return depthbeta(p,r,1);
    }
    
    void print (Node* r){
        if (r == NULL) return;
        printf ("%d: ",r->data);
        Node* p = r->LeftMostChild;
        while (p != NULL){
            printf ("%d",p->data);
            p = p->RightSibling;
        }
        printf ("n");             
        p = r->LeftMostChild;
        while (p != NULL){
            print (p);
            p = p->RightSibling;
        }
    }
    
    int parents(Node* p, Node* r){
        if (p == NULL) return -1;
        if (r == NULL) return -1;
        Node* q = r->LeftMostChild;
        while (q != NULL){
            if (q == p) return r->data;
            q = q->RightSibling;
        }
      
        q = r->LeftMostChild;
        while (q != NULL){
            int h = parents(p,q);
            if (h > 0) return h;
            q = q->RightSibling;
        }  
    }
    
    void inorder (Node* r){
        if (r == NULL) return;
        Node* p = r->LeftMostChild;
        inorder(p);
        printf ("%d  ", r->data);
        Node* p2;
        if (p != NULL){
            p2 = p->RightSibling;
            while (p2 != NULL){
            inorder(p2);
            p2 = p2->RightSibling;
            }
        }  
    }
    
    int main(int argc, char ** argv){
        char* filename = argv[1];
        readData(filename);
        print(root);
        printf("Number of Node is: %dn",count(root));
        printf("Number of Lead is: %dn",countLeaves(root));
        printf("Sum: %dn",sum(root));
        printf("Height: %dn",height(find(8,root),root));
        printf("Depth: %dn",depth(find(7,root),root));
        for (int x = 1; x <= 10; x++){
            Node* p = find (x,root);
        printf("Parents of %d is %d", x, parents(p, root));
        printf ("n");
        }
      
        inorder(root);
    }

    LƯU Ý: Đây là code mình viết trên trình Notepad++ và sử dụng Cygwin (Phần mềm giả lập Linux) để dịch chương trình. Các bạn có thể theo dõi cách sử dụng Cygwin và cách sử dụng Cygwin để dịch chương trình C/C++ tại đây:

    http://minhduongit.com/huong-dan-su-dung-cygwin-dich-chuong-trinh-cc-bang-cygwin/

    Chúc các bạn học tập tốt !!!
     
    DOWNLOAD BẢN ĐẦY ĐỦ NHẤT TẠI ĐÂY
    download now
    LINK FSHARE Hoặc LINK SHARE.VNN.VN

    Bình Luận Bằng Facebook

Chia sẻ trang này

Text Link: |Ban iPhone cu |Jailbreak iOS 9.3.3 |Tai lieu Swift Tieng Viet |Tao Boot USB |Antamedia Hotspot 4 Full Crack |Proshow Producer 7 Full Crack |Chu ky mau dep |Kiem tien tren mang |Ghost win 7 Full Soft |Ghost win 10 Full Soft |Ghost win XP Full Soft |Game Offline cho PC |Game Sex Offline |Game nhap vai luyen level |Game ban sung Offline |Game dan tran Offline |Game nhap vai hay |Hack Asphalt 8 |Hack ban ga 5 |Hack ban ga 6 |Game dua xe Offline |Tool tăng view Youtube |Kiếm tiền trên Youtube |SEO đề xuất Youtube |Kháng cáo Youtube |Lắp đặt internet viettel giá rẻ |Đăng ký cáp quang viettel miễn phí |lắp đặt Cáp Quang Viettel tại TPHCM |FPlus 4.8 Full Crack |GPlus 4.7 Full Crack |Poke Map |Táo Quân 2017 |Hài Tết 2017 |Sitemap