Bài giảng bài 4: Cây (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); else if(x>t->data) SearchTree(t->right); else return t; } //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 ->ritght; else Del(t->left,q) ; free (q); } } Giả sử nút cần xóa là x=10 In cây void NLR(tree t) { if(t!=NULL) // !EmptyTree(t) { coutdata; NLR(t->left); NLR(t->right); } } void LNR(tree t) { if(t!=NULL)//!EmptyTree(t) { LNR(t->left); coutdata; LNR(t->right); } } void LRN(tree t) { if(t!=NULL) // !EmptyTree(t) { LRN(t->left); LRN(t->right); coutdata; } } 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. Sau đó in chúng ra màn hình dưới dạng cây. 2. Có thể áp dụng Tree (cây nhị phân) để lập cây gia phả họ hàng. BÀI TẬP