TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu 1: Chương 4B - Huỳnh Cao Thế Cường

Cây nhị phân là cây rỗng hoặc là cây mà mỗi nút có tối đa hai nút con. Các nút con của cây được phân biệt thứ tự rõ ràng, một nút con gọi là nút con trái và một nút con gọi là nút con phải. Trong chương này sẽ cung cấp cho người học những kiến thức về cây nhị phân (binary trees) và cách cài đặt cây nhị phân. . | CẤU TRÚC DỮ LIỆU 1 Giảng viên phụ trách: HUỲNH CAO THẾ CƯỜNG Bộ môn Tin học email: hctcuong@ TRƯỜNG ĐẠI HỌC AN GIANG KHOA KỸ THUẬT- CÔNG NGHỆ - MÔI TRƯỜNG CÂY NHỊ PHÂN (BINARY TREES) Định nghĩa Cây nhị phân là cây rỗng hoặc là cây mà mỗi nút có tối đa hai nút con. Các nút con của cây được phân biệt thứ tự rõ ràng một nút con gọi là nút con trái một nút con gọi là nút con phải. Ta qui ước vẽ nút con trái bên trái nút cha và nút con phải bên phải nút cha, mỗi nút con được nối với nút cha của nó bởi một đoạn thẳng. Cây nhị phân Cây nhị phân Cây nhị phân Duyệt cây nhị phân Duyệt tiền tự (Node-Left-Right): duyệt nút gốc, duyệt tiền tự con trái rồi duyệt tiền tự con phải. Duyệt trung tự (Left-Node-Right): duyệt trung tự con trái rồi đến nút gốc sau đó là duyệt trung tự con phải. Duyệt hậu tự (Left-Right-Node): duyệt hậu tự con trái rồi duyệt hậu tự con phải sau đó là nút gốc. Cây nhị phân Cài đặt cây nhị phân typedef TData; typedef struct Tnode { TData Data; //nhãn TNode* left TNode* right; }; typedef TNode* TTree; Cài đặt cây nhị phân Tạo cây rỗng : Cây rỗng là một cây là không chứa một nút nào cả. void MakeNullTree(TTree *T) { (*T)=NULL; } Kiểm tra cây rỗng int EmptyTree(TTree T) { return T==NULL; } Cài đặt cây nhị phân Xác định con trái của một nút TTree LeftChild(TTree n) { if (n!=NULL) return n->left; else return NULL; } Xác định con phải của một nút TTree RightChild(Ttree n) { if (n!=NULL) return n->right; else return NULL; } Cài đặt cây nhị phân Kiểm tra nút lá: Nếu nút là nút lá thì nó không có bất kỳ một con nào cả nên khi đó con trái và con phải của nó cùng bằng nil int IsLeaf(TTree n) { if(n!=NULL) return(LeftChild(n)==NULL) &&(RightChild(n)==NULL); else return NULL; } Cài đặt cây nhị phân Xác định số nút của cây int nb_nodes(TTree T) { if(EmptyTree(T)) return 0; else return 1 + nb_nodes(LeftChild(T)) + nb_nodes(RightChild(T)); } Cài đặt cây nhị phân Tạo cây mới từ hai cây có sẵn TTree Create2(Tdata v, TTree l, TTree r) { TTree N; N=(TNode*)malloc(sizeof(TNode)); N->Data=v; N->left=l; N->right=r; return N; } Cài đặt cây nhị phân Thủ tục duyệt tiền tự void PreOrder(TTree T) { printf("%c ",T->Data); if (LeftChild(T)!=NULL) PreOrder(LeftChild(T)); if (RightChild(T)!=NULL) PreOrder(RightChild(T)); } Cài đặt cây nhị phân Thủ tục duyệt trung tự void InOrder(TTree T) { if (LeftChild(T)=!NULL) InOrder(LeftChild(T)); printf("%c ",T->data); if (RightChild(T)!=NULL) InOrder(RightChild(T)); } Cài đặt cây nhị phân Thủ tục duyệt hậu tự void PosOrder(TTree T) { if (LeftChild(T)!=NULL) PosOrder(LeftChild(T)); if (RightChild(T)!=NULL) PosOrder(RightChild(T)); printf("%c ",T->data); } Cảm ơn !

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu
• Giải thuật
• Cơ sở dữ liệu
• Cấu trúc cây
• Cây nhị phân
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp