Đang chuẩn bị liên kết để tải về tài liệu:
Bài 4: Cây (Tree)

Sau bài học này, sinh viên có khả năng: .Trình bày được định nghĩa cây (Tree) .Cài đặt được cây nhị phân .Vận dụng cây nhị phân vào các bài toán (tính toán, cây gia phả .) | Câu hỏi kiểm tra Trình bày cách khai báo cấu trúc của một danh sách liên kết ? Trả lời typedef struct node { node *next; int info; } node; // Khai báo kiểu con trỏ chỉ đến nút typedef struct node *list; Bài 4. CÂY (TREE) CBGD: Trần Việt Khánh MỤC TIÊU Sau bài học này, sinh viên có khả năng: Trình bày được định nghĩa cây (Tree) Cài đặt được cây nhị phân Vận dụng cây nhị phân vào các bài toán (tính toán, cây gia phả .) NỘI DUNG I/ Định nghĩa II/ Cài đặt Tree (cây) Khai báo cấu trúc của một cây nhị phân Các tác vụ trên cây nhị phân I/ Định nghĩa Tree (cây nhị phân): là cây mà mỗi nút có tối đa là 2 con (con trái và con phải). Hình vẽ minh họa cây nhị phân (Tree) II/ Cài đặt Tree (cây nhị phân) 1. Khai báo cấu trúc cây nhị phân // Khai báo cấu trúc của một Tree typedef struct node { node *left ,*right; int data; } node; // Khai báo kiểu con trỏ left, right chỉ đến các nút con typedef struct node *tree; Khởi tạo cây rỗng void CreateTree(tree &t) { t=NULL; } 2. Các tác vụ trên Tree . | Câu hỏi kiểm tra Trình bày cách khai báo cấu trúc của một danh sách liên kết ? Trả lời typedef struct node { node *next; int info; } node; // Khai báo kiểu con trỏ chỉ đến nút typedef struct node *list; Bài 4. CÂY (TREE) CBGD: Trần Việt Khánh MỤC TIÊU Sau bài học này, sinh viên có khả năng: Trình bày được định nghĩa cây (Tree) Cài đặt được cây nhị phân Vận dụng cây nhị phân vào các bài toán (tính toán, cây gia phả .) NỘI DUNG I/ Định nghĩa II/ Cài đặt Tree (cây) Khai báo cấu trúc của một cây nhị phân Các tác vụ trên cây nhị phân I/ Định nghĩa Tree (cây nhị phân): là cây mà mỗi nút có tối đa là 2 con (con trái và con phải). Hình vẽ minh họa cây nhị phân (Tree) II/ Cài đặt Tree (cây nhị phân) 1. Khai báo cấu trúc cây nhị phân // Khai báo cấu trúc của một Tree typedef struct node { node *left ,*right; int data; } node; // Khai báo kiểu con trỏ left, right chỉ đến các nút con typedef struct node *tree; Khởi tạo cây rỗng void CreateTree(tree &t) { t=NULL; } 2. Các tác vụ trên Tree (cây nhị phân) Kiểm tra cây có bị rỗng không bool EmptyTree(tree t) { return ( t == NULL); } Tìm kiếm một phần tử x trong cây tree SearchTree(tree t, int x) { if(xdata) SearchTree(t->left,x); else if(x>t->data) SearchTree(t->right,x); else return t; } Hình vẽ minh họa đoạn code trên Giả sử nút cần tìm là x = 8 //Chèn một phần tử x vào cây (Tree) void InsertTree(tree &t, int x) { if(t==NULL) // !EmptyTree(t) { t = (tree) malloc(sizeof(node)); t->data = x; t->left = NULL; t->right = NULL; } else if(xdata) InsertTree(t->left,x); else InsertTree(t->right,x); } Hình vẽ minh họa đoạn code trên // Xóa phần tử x ra khỏi cây void Del (tree &p, tree &q) { if(p->right !=NULL) Del(p->right,q); else { q->data = p->data; q = p; p = q->left; } } void DeleteTree (tree &t, int x) { tree q; if( xdata ) DeleteTree(t->left,x); else if ( x>t->data) DeleteTree(t->right,x); else { q = t; if (t ->right = = NULL) t = t ->left; else if (t->left == NULL) t = t ->right; else Del(t->left,q) ; free (q); } } Giả sử nút cần xóa là x=10 In cây void LNR(tree t,int muc) { coutleft,muc); coutdata; LNR(t->right,muc); muc--; } } void LRN(tree t,int muc) { coutleft,muc); LRN(t->right,muc); muc--; coutdata; } } void NLR(tree t,int muc) { coutdata; muc++; NLR(t->left,muc); NLR(t->right,muc); muc--; } } Viết chương trình áp dụng cây nhị phân nhập một dãy số nguyên khác 0. Thực hiện: In các nút trên cây ra màn hình. Tỉnh tổng các nút trên cây. Thêm một nút vào cây. Xóa một nút ra khỏi cây. 2. Có thể áp dụng Tree (cây nhị phân) để lập cây gia phả( dòng họ và bà con, ). BÀI TẬP CHÂN THÀNH CẢM ƠN !