Duyệt Cây Nhị Phân Tìm Kiếm Trong C/C++ - Lập Trình Từ Đầu

Vấn đề sau khi nhập các node vào cây đó là việc duyệt cây. Khác với cấu trúc dữ liệu khác, ở trong cấu trúc dữ liệu cây ta sẽ có nhiều cách khác nhau để duyệt một cây. Trong bài này tôi sẽ đưa ra 3 phương pháp duyệt cây đó là:

• Duyệt cây theo tiền thứ tự
• Duyệt cây theo trung thứ tự
• Duyệt cây theo hậu thứ tự

Chú ý: Mọi thao tác duyệt cây đều có sử dụng phương pháp đệ quy!

1.Duyệt cây theo tiền thứ tự – NLR

Duyệt cây theo tiền thứ tự hay duyệt theo Node – Left – Right (NLR) là việc ban đầu thực hiện ghé thăm node gốc, tiếp sau đó ghé thăm đến cây con trái và cuối cùng là ghé thăm cây con phải.

void NLR(Tree root){     if (root!=NULL){         //xu ly node goc         printf("%d \t",root->data);         //su dung de quy de duyet tiep cay con trai         NLR(root->left);         //su dung de quy de duyet tiep cay con phai         NLR(root->right);     } } 2.Duyệt cây theo trung thứ tự – LNR

Duyệt cây theo trung thứ tự hay duyệt theo Left – Node – Right là việc ban đầu sẽ ghé thăm cây con trái, tiếp theo ghé thăm đến node gốc và cuối cùng là ghé thăm cây con phải.

void LNR(Tree root){     if (root!=NULL){         //su dung de quy de duyet tiep cay con trai         LNR(root->left);         //xu ly node goc         printf("%d \t",root->data);         //su dung de quy de duyet tiep cay con phai         LNR(root->right);     } } 3. Duyệt cây theo hậu thứ tự – LRN

Việc duyệt cây theo hậu thứ tự hay duyệt theo Left – Right -Node là việc ban đầu sẽ ghé thăm cây con trái, tiếp theo ghé thăm đến cây con phải và cuối cùng mới thực hiện ghé thăm node gốc.

void LRN(Tree root){     if (root!=NULL){         //su dung de quy de duyet tiep cay con trai         LRN(root->left);         //su dung de quy de duyet tiep cay con phai         LRN(root->right);         //xu ly node goc         printf("%d \t",root->data);     } } 4.Chương trình hoàn chỉnh duyệt cây theo NLR – LNR – LRN

Trước khi đến với chương trình duyệt cây, đầu tiên bạn hay đảm bảo đã có thể thêm các node vào cây trước! Sau đó ta có thể hoàn toàn sử dụng 1 trong 3 phương pháp ở trên (tùy vào yêu cầu) để duyệt cây nhị phân!

#include <stdio.h> #include <stdlib.h> typedef struct Node{ //khai bao du lieu cua node co kieu du lieu int int data; //khai bao con tro den cay con trai Node* left; //khai bao con tro den cay con phai Node* right; }; typedef struct Node* Tree; Tree root; void Init (Tree &root){ //gan node goc ve NULL root = NULL; } Node* CreateNode (int x){ //tao node moi Node* p = new Node; //neu cay nhi phan khong rong if (p != NULL){ //gan cay con trai va cay con phai mac dinh bang NULL p->left = NULL; p->right = NULL; //gan data bang x p->data = x; } //tra ve node p return p; } int InsertNode(Tree &root, Node*p){ //neu node root khac rong thi thuc hien them vao cay if (root != NULL){ //neu 2 data cua 2 node bang nhau thi ket thuc if (root->data==p->data){ return 0; } //neu khoa cua root lon hon khoa cua p thi goi de quy trai if (root->data > p->data){ return InsertNode(root->left, p); } else{//neu khoa cua root nho hon khoa cua p thi goi de quy phai return InsertNode(root->right,p); } }else { //truong hop neu node root la rong thi them node p vao node root root = p; } } void Input(Tree &root){ int n; printf ("NHAP SO LUONG NODE CAN THEM: "); scanf("%d",&n); for(int i=1; i<=n;i++){ int x; printf ("NHAP DATA CUA NODE %d: ",i); scanf("%d",&x); //tao node p co data = x Node* p = CreateNode(x); //them node p co data x vao trong cay InsertNode(root, p); } } void NLR(Tree root){ if (root!=NULL){ //xu ly node goc printf("%d \t",root->data); //su dung de quy de duyet tiep cay con trai NLR(root->left); //su dung de quy de duyet tiep cay con phai NLR(root->right); } } void LNR(Tree root){ if (root!=NULL){ //su dung de quy de duyet tiep cay con trai LNR(root->left); //xy ly node goc printf("%d \t",root->data); //su dung de quy de duyet tiep cay con phai LNR(root->right); } } void LRN(Tree root){ if (root!=NULL){ //su dung de quy de duyet tiep cay con trai LRN(root->left); //su dung de quy de duyet tiep cay con phai LRN(root->right); //xu ly node goc printf("%d \t",root->data); } } int main(){ //tao cay voi node goc la root Tree root; //khoi tao cay Init(root); //nhap n phan tu vao cay Input(root); //duyet cay theo NLR printf("Duyet cay theo NLR\n"); NLR(root); //duyet cay theo LNR printf("\nDuyet cay theo LNR\n"); LNR(root); //duyet cay theo LRN printf("\nDuyet cay theo LRN\n"); LRN(root); }

NHAP SO LUONG NODE CAN THEM: 5 NHAP DATA CUA NODE 1: 66 NHAP DATA CUA NODE 2: 9 NHAP DATA CUA NODE 3: 2 NHAP DATA CUA NODE 4: 9 NHAP DATA CUA NODE 5: 55 Duyet cay theo NLR 66 9 2 55 Duyet cay theo LNR 2 9 55 66 Duyet cay theo LRN 2 55 9 66