Tài nguyên

Các ý kiến mới nhất

Hỗ trợ trực tuyến

  • (Trần Văn Luân)
  • (Nguyễn Đăng Nhật Quang)
  • (Trần Đức Anh)

Điều tra ý kiến

Bạn thấy trang này như thế nào?
Đẹp
Bình thường
Sơ sài
Ý kiến khác

Thống kê

  • truy cập   (chi tiết)
    trong hôm nay
  • lượt xem
    trong hôm nay
  • thành viên
  • Ảnh ngẫu nhiên

    Hinh0023.jpg Hinh0022.jpg Hinh0015.jpg

    Thành viên trực tuyến

    0 khách và 0 thành viên

    Cây nhị phân

    Nhấn vào đây để tải về
    Báo tài liệu có sai sót
    Nhắn tin cho tác giả
    (Tài liệu chưa được thẩm định)
    Nguồn: st
    Người gửi: Trần Đức Anh (trang riêng)
    Ngày gửi: 09h:51' 18-09-2011
    Dung lượng: 1.4 MB
    Số lượt tải: 4
    Số lượt thích: 0 người
    CÂY NHỊ PHÂN TÌM KIẾM
    TMT
    1
    Nội dung
    Các khái niệm
    Đặc điểm
    Hình dạng
    Các khái niệm
    Định nghĩa kiểu dữ liệu
    Các lưu ý khi cài đặt
    Các thao tác
    2
    Các khái niệm
    Bậc của một nút: là số cây con của nút đó.
    Nút gốc: là nút không có nút cha.
    Nút lá: là nút có bậc bằng 0.
    Nút nhánh: là nút có bậc khác 0 và không phải là gốc.
    3
    Các khái niệm (tt)
    Độ dài đường đi từ gốc đến nút x: là số nhánh cần đi qua kể từ gốc đến x.
    Độ cao của cây: Độ dài đường đi từ gốc đến nút lá ở mức thấp nhất.
    4
    Đặc điểm cây nhị phân tìm kiếm
    Là cây nhị phân
    Giá trị của một node bất kỳ luôn lớn hơn giá trị của tất cả các node bên trái và nhỏ hơn giá trị tất cả các node bên phải
    Nút có giá trị nhỏ nhất nằm ở trái nhất của cây
    Nút có giá trị lớn nhất nằm ở phải nhất của cây
    7
    3
    36
    1
    6
    15
    40
    23
    4
    5
    Nút
    Định nghĩa kiểu dữ liệu
    typedef struct TNODE
    {
    Key;
    struct TNODE *pLeft, *pRight;
    } *TREE;
    Giá trị
    Trỏ trái
    Trỏ phải
    TNODE
    Key
    pLeft
    pRight
    6
    Ví dụ khai báo cây nhị phân biểu diễn các node là số nguyên
    typedef struct TNODE
    {
    int Key;
    struct TNODE *pLeft, *pRight;
    } *TREE;
    7
    Các lưu ý khi cài đặt
    Bước 1: Khai báo kiễu dữ liệu biểu diễn cây
    Bước 2: Xây dựng hàm đưa dữ liệu (nhập) vào cây
    Bước 3: Xây dựng các thao tác duyệt, tìm kiếm, huỷ, …

    Các lưu ý khác:
    1. Trước khi tạo node mới phải xin cấp phát vùng nhớ.
    2. Trước khi tạo cây mới phải khởi tạo cây rỗng.
    3. Trước khi kết thúc chương trình phải huỷ cây (giải phóng vùng nhớ).
    8
    Cấu trúc chương trình
    Khai báo cấu trúc cây
    Khởi tạo cây rỗng
    Xây dựng cây
    Các thao tác
    Hủy cây
    9
    Các thao tác
    1. Xây dựng cây
    2. Duyệt cây
    3. Cho biết các thông tin của cây
    4. Tìm kiếm
    5. Xoá node trên cây
    10
    Các thao tác
    1. Xây dựng cây
    2. Duyệt cây
    3. Cho biết các thông tin của cây
    4. Tìm kiếm
    5. Xoá node trên cây
    11
    40
    15
    4
    6
    1
    36
    3
    Xây dựng cây
    7
    Nếu node cần thêm < node đang xét thì thêm về bên trái.
    Ngược lại thì thêm về bên phải.
    12
    Xây dựng cây (tt)
    int ThemNut (TREE & t, int x)
    {
    if(t!=NULL)
    { if(x==t->Key) return 0;
    else
    {
    if(xKey) ThemNut(t->pLeft, x);
    else ThemNut(t->pRight, x);
    }
    }
    else
    {
    t=new TNODE;
    if(t==NULL) return -1;
    t->Key=x;
    t->pLeft=t->pRight=NULL;
    return 1;
    }
    }
    13
    Các thao tác
    1. Xây dựng cây
    2. Duyệt cây
    3. Cho biết các thông tin của cây
    4. Tìm kiếm
    5. Xoá node trên cây
    14
    Các thao tác
    1. Xây dựng cây
    2. Duyệt cây
    3. Cho biết các thông tin của cây
    4. Tìm kiếm
    5. Xoá node trên cây
    15
    Duyệt cây
    Thứ tự trước (NLR)
    Thứ tự giữa (LNR)
    Thứ tự sau (LRN)
    16
    NLR
    7 L7 R7
    7 3 L3 R3 36 L36 R36
    7 3 1 6 L6 36 15 R15 40
    7 3 1 6 4 36 15 23 40
    7
    3
    36
    1
    6
    15
    40
    23
    4
    17
    NLR
    Tại node t đang xét, nếu khác rỗng thì
    . In giá trị của t
    . Duyệt cây con bên trái của t theo thứ tự NLR
    . Duyệt cây con bên phải của t theo thứ tự NLR
    void NLR (TREE t)
    {
    if(t!=NULL)
    {
    cout<Key<<“ ”;
    NLR(t->pLeft);
    NLR(t->pRight);
    }
    }
    18
    BÀI TẬP
    Bài 1
    Hãy xây dựng cây nhị phân tìm kiếm theo thứ tự nhập sau:
    27 19 10 21 35 25 41 12 46 7
    Hãy duyệt cây trên theo thứ tự trước
    Bài 2
    Hãy xây dựng cây nhị phân tìm kiếm theo thứ tự nhập sau:
    H B C A E D Z M P T
    Hãy duyệt cây trên theo thứ tự trước
    Bài 3
    Hãy xây dựng cây nhị phân tìm kiếm theo thứ tự nhập sau:
    Huế Đà Nẵng Hà Nội Vĩnh Long Cần Thơ Sóc Trăng Nha Trang Đồng Nai Vũng Tàu An Giang Tiền Giang Bình Dương Hải Dương
    19
    LNR
    L7 7 R7
    L3 3 R3 7 L36 36 R36
    1 3 L6 6 7 15 R15 36 40
    1 3 4 6 7 15 23 36 40
    7
    3
    36
    1
    6
    15
    40
    23
    4
    20
    LNR
    Tại node t đang xét, nếu khác rỗng thì
    . Duyệt cây con bên trái của t theo thứ tự LNR
    . In giá trị của t
    . Duyệt cây con bên phải của t theo thứ tự LNR
    void LNR (TREE t)
    {
    if(t!=NULL)
    {
    LNR(t->pLeft);
    cout<Key<<“ “;
    LNR(t->pRight);
    }
    }
    21
    LRN
    L7 R7 7
    L3 R3 3 L36 R36 36 7
    1 L6 6 3 R15 15 40 36 7
    1 4 6 3 23 15 40 36 7
    7
    3
    36
    1
    6
    15
    40
    23
    4
    22
    LRN
    Tại node t đang xét, nếu khác rỗng thì
    . Duyệt cây con bên trái của t theo thứ tự LRN
    . Duyệt cây con bên phải của t theo thứ tự LRN
    . In giá trị của t
    void LRN (TREE t)
    {
    if(t!=NULL)
    {
    LRN(t->pLeft);
    LRN(t->pRight);
    cout<Key<<“ “;
    }
    }
    23
    BÀI TẬP
    Bài 4
    Hãy xây dựng cây nhị phân tìm kiếm theo thứ tự nhập sau:
    27 19 10 21 3 15 41 50 30 27
    Hãy duyệt cây trên theo thứ tự giữa
    Bài 5
    Hãy xây dựng cây nhị phân tìm kiếm theo thứ tự nhập sau:
    H B C A E D T M X O
    Hãy duyệt cây trên theo thứ tự sau
    24
    Vấn đề cần quan tâm
    Xây dựng cây từ kết quả duyệt theo thứ tự trước (NLR)
    Chọn giá trị đầu tiên làm node gốc.
    Lần lượt đưa các giá trị còn lại từ trái sang phải vào cây theo nguyên tắc xây dựng cây.
    Xây dựng cây từ kết quả duyệt theo thứ tự sau (LRN)
    Chọn giá trị cuối cùng làm node gốc.
    Lần lượt đưa các giá trị còn lại từ phải sang trái vào cây theo nguyên tắc xây dựng cây.
    25
    Vấn đề cần quan tâm (tt)
    Xây dựng cây từ kết quả duyệt theo thứ tự giữa (LNR)
    Gọi r: Số lượng giá trị cho trước.
    Gọi m = r div 2: Giá trị ở giữa.
    Chọn giá trị thứ m làm node gốc.
    Lần lượt đưa các giá trị bắt đầu từ vị trí m-1 lùi về trái vào cây theo nguyên tắc xây dựng cây.
    Lần lượt đưa các giá trị bắt đầu từ vị trí m+1 đến cuối vào cây theo nguyên tắc xây dựng cây.
    26
    BÀI TẬP
    Bài 6
    Hãy vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự Left-Right-Node thì được dãy sau: 1, 4, 7, 5, 3, 16, 18, 15, 29, 25, 30, 20, 8.
    Hãy duyệt cây T trên theo thứ tự Node-Left-Right.
    Cây T có chiều cao là bao nhiêu? Tìm các đường đi từ gốc có độ dài là 4 trên cây
    27
    BÀI TẬP
    Bài 7
    Hãy vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự Node-Left-Right thì được dãy sau: 9, 4, 1, 3, 8, 6, 5, 7, 10, 14, 12, 13, 16, 19.
    Hãy duyệt cây T trên theo thứ tự Left-Right-Node.
    Liệt kê các nút lá của cây. Liệt kê các nút nhánh của cây.
    28
    CÀI ĐẶT
    void Nhap(TREE &t)
    {
    int x;
    do{
    cout<<“Nhap gia tri: “;
    cin>>x;
    int kq=ThemNut(t, x);
    if(kq==0||kq==-1)
    break;
    }while (true);
    }
    29
    CÀI ĐẶT
    void main()
    {
    TREE t;
    t=NULL;
    Nhap(t);
    cout<<“Duyet cay theo thu tu giua: “;
    LNR(t);

    Huy(t);
    }
    30
    Các thao tác
    1. Xây dựng cây
    2. Duyệt cây
    3. Cho biết các thông tin của cây
    4. Tìm kiếm
    5. Xoá node trên cây
    31
    Các thao tác
    1. Xây dựng cây
    2. Duyệt cây
    3. Cho biết các thông tin của cây
    4. Tìm kiếm
    5. Xoá node trên cây
    32
    Cho biết các thông tin của cây
    Số node lá (node bậc 0)
    Số node có 1 cây con (node bậc 1)
    Số node chỉ có 1 cây con phải
    Số node có 1 cây con trái
    Số node 2 cây con (node bậc 2)
    Độ cao của cây
    Số node của cây
    Các node trên từng mức của cây
    Độ dài đường đi từ gốc đến node x
    33
    Số node lá
    Nếu node t khác rỗng thì
    . Nếu node t có bậc 0 thì
    Trả về 1
    . Ngược lại
    Trả về Số node lá cây trái t
    + Số node lá cây phải t
    Nếu node t rỗng thì
    Trả về 0
    34
    Số node lá (tt)
    int DemNutLa (TREE t)
    {
    if(t)
    {
    if(t->pLeft==NULL && t->pRight==NULL)
    return 1;
    else
    return DemNutLa(t->pLeft)+DemNutLa(t->pRight);
    }
    else
    return 0;
    }
    35
    Số node có 1 cây con
    Nếu node t khác rỗng thì
    d=Số node bậc 1 của cây trái t
    + Số node bậc 1 của cây phải t
    Nếu node t có bậc 1 thì trả về d+1
    Ngược lại trả về d
    Nếu node t rỗng thì
    Trả về 0
    36
    Số node có 1 cây con
    int DemNut1Con(TREE t)
    {
    if(t)
    {
    int d=DemNut1Con(t->pLeft)+DemNut1Con(t->pRight);
    if((t->pLeft!=NULL&&t->pRight==NULL)
    ||(t->pLeft==NULL&&t->pRight!=NULL))
    return d+1;
    else
    return d;
    }
    else
    return 0;
    }
    37
    Số node chỉ có 1 cây con phải
    Nếu node t khác rỗng thì
    d = Số node chỉ có 1 cây con phải của cây con trái t
    + Số node chỉ có 1 cây con phải của cây con phải t
    Nếu node t chỉ có 1 cây con phải thì trả về d+1
    Ngược lại trả về d
    Nếu node t rỗng thì
    Trả về 0
    38
    Số node có 1 cây con phải
    int DemNut1ConPhai(TREE t)
    {
    if(t)
    {
    int d=DemNut1ConPhai(t->pLeft)
    +DemNut1ConPhai(t->pRight);
    if(t->pLeft==NULL && t->pRight!=NULL)
    return d+1;
    else
    return d;
    }
    else
    return 0;
    }
    39
    Số node chỉ có 1 cây con trái
    40
    Số node có 2 cây con
    41
    Độ cao của cây
    int DoCaoCay(TREE t)
    {
    if(t)
    {
    int t1=DoCaoCay(t->pLeft);
    int t2=DoCaoCay(t->pRight);
    return Max(t1, t2)+1;
    }
    else
    return 0;
    }
    42
    Số node của cây
    43
    Các node trên từng mức
    Mức 2: 1 6 15 40
    7
    3
    36
    1
    6
    15
    40
    23
    4
    44
    Các node trên từng mức
    void InMuck(TREE t, int k, int m=0)
    {
    if(t)
    {
    if(m==k)
    {
    printf("%d ", t->Key);
    return;
    }
    else
    {
    m++;
    InMuck(t->pLeft, k,m);
    InMuck(t->pRight, k, m);
    }
    }
    }
    45
    In các node của tất cả mức
    46
    Độ dài đường đi từ gốc đến node x
    47
    Các thao tác
    1. Xây dựng cây
    2. Duyệt cây
    3. Cho biết các thông tin của cây
    4. Tìm kiếm
    5. Xoá node trên cây
    48
    Các thao tác
    1. Xây dựng cây
    2. Duyệt cây
    3. Cho biết các thông tin của cây
    4. Tìm kiếm
    5. Xoá node trên cây
    49
    Tìm kiếm
    Tìm x
    Tìm min
    Tìm min của cây con bên phải
    Tìm max
    Tìm max của cây con bên trái
    50
    Ví dụ tìm x = 23
    7
    3
    36
    1
    6
    15
    40
    23
    4
    51
    Tìm x
    TNODE * TimKiem(TREE t,int x)
    {
    if(t!=NULL)
    {
    if(t->Key==x) return t;
    if(xKey)
    return TimKiem(t->pLeft,x);
    else
    return TimKiem (t->pRight,x);
    }
    return NULL;
    }
    52
    Tìm min
    TNODE* Min(TREE t)
    {
    while(t->pLeft!=NULL)
    {
    t=t->pLeft;
    }
    return t;
    }
    53
    Min cây con bên phải
    54
    Tìm max
    55
    Tìm max cây con bên trái
    56
    Các thao tác
    1. Xây dựng cây
    2. Duyệt cây
    3. Cho biết các thông tin của cây
    4. Tìm kiếm
    5. Xoá node trên cây
    57
    Các thao tác
    1. Xây dựng cây
    2. Duyệt cây
    3. Cho biết các thông tin của cây
    4. Tìm kiếm
    5. Xoá node trên cây
    58
    Xóa node trên cây
    Node lá
    Node có 1 cây con
    Node có 2 cây con
    7
    3
    36
    1
    6
    15
    40
    23
    4
    59
    Xóa node lá
    Xóa 1
    Xóa 23
    7
    3
    36
    1
    6
    15
    40
    23
    4
    60
    Xóa node 1 cây con
    Xóa 6
    Xóa 15
    7
    3
    36
    1
    6
    15
    40
    23
    4
    4
    23
    61
    Xóa node 2 cây con
    Tìm node thế mạng
    Cách 1: Tìm node trái nhất của cây con phải
    Cách 2: Tìm node phải nhất của cây con trái

    Xóa 36 (Cách 2)
    7
    3
    36
    1
    6
    15
    40
    23
    4
    16
    23
    62
    Tìm node thế mạng
    void TimTheMang (TREE &pHuy,TREE & q)
    {
    if(q->pLeft)
    TimTheMang(pHuy, q->pLeft);
    else
    {
    pHuy->Key=q->Key;
    pHuy=q;
    q=q->pRight;
    }
    }
    63
    Xóa một node có giá trị x
    void HuyNut (TREE & t, int x)
    {
    if(t!=NULL)
    { if(xKey) HuyNut(t->pLeft,x);
    else{
    if(x>t->Key) HuyNut(t->pRight,x);
    else{
    TNODE * pHuy=t;
    if(t->pLeft==NULL) t=t->pRight;
    else
    if(t->pRight==NULL) t=t->pLeft;
    else TimTheMang(pHuy,t->pRight);
    delete pHuy;
    }
    }

    }
    }
    64
    Huỷ toàn bộ cây
    Nếu node khác rỗng
    Hủy cây bên trái t
    Hủy cây bên phải t
    Hủy node t
    65
    Cho dãy số theo thứ tự nhập từ trái sang phải như sau: 20 15 35 30 11 13 17 36 47 16 38 28 14
    Hãy vẽ cây nhị phân tìm kiếm cho dãy số trên.
    Hãy cho biết kết quả duyệt cây trên theo thứ tự trước, giữa và sau.
    Cho biết độ cao của cây, các nút lá, các nút có bậc 2.
    Vẽ lại cây sau khi thêm nút: 25 và 91
    Trình bày từng bước và vẽ lại cây sau khi lần lượt xoá các nút: 11 và 35
    66
     
    Gửi ý kiến