Cây nhị phân trong C/C++ Binary Tree – Cấu trúc dữ liệu và giải thuật

0
9845
cay nhi phan binary tree cai dat bang con tro code c

Cây nhị phân trong C/C++ là một dạng cấu trúc dữ liệu quan trọng. Cách duyệt cây, cách thao tác với binary tree là nội dung code mình chia sẻ với bạn trong bài viết này.

1. Cây nhị phân là gì?

Định nghĩa: Cây nhị phân (hay còn gọi là Binary Tree) là cây rỗng hoặc cây có tối đa hai nút con, trong đó thứ tự của cây được phân biệt thứ tự rõ ràng. Một nút gọi là con trái, một nút gọi là con phải.

Cây nhị phân khác với cây nhị phân tìm kiếm ở chỗ, nó không phân biệt lớn nhỏ. Phần tử có thể nằm ở bất kì vị trí nào trong cây.

Một số phép toán thường dùng trên cấu trúc cây nhị phân:

  • Tạo cây rỗng
  • Kiểm tra cây rỗng
  • Xác định con trái của một nút
  • Xác đinh con phải của một nút
  • Kiểm tra nút lá
  • Xác định số nút của cây
  • Tạo cây mới từ hai cây có sẵn
  • Tìm một đỉnh có khóa x trên cây

Có hai cách thường được sử dụng để biểu diễn cây nhị phân:

  • Biểu diễn bằng mảng
  • Biểu diễn bằng con trỏ

Nhưng thường để dễ thao tác, người ta sẽ sử dụng con trỏ trong C hoặc C++ để biếu diễn. Bài viết này mình sử dụng cách này.

2. Cài đặt cây nhị phân trong C/C++

Mình sẽ sử dụng ngôn ngữ C để viết nhé!
Ngôn ngữ C và C++ chỉ khác nhau một chút về câu lệnh nhập xuất, khai báo con trỏ. Nếu bạn muốn code khác ngôn ngữ mình chia sẻ. Chỉ cần đổi một chút là được, quan trọng là hiểu về mặt thuật toán.

Chú ý lỗi hiển thị
Dấu & bị tự chuyển thành & amp;

2.1 Khai báo cấu trúc cây nhị phân

#include<stdlib.h>
#include<stdio.h>
// Hai dong ben tren la khai bao thu vien trong C
typedef int item; //kieu item la kieu nguyen
struct Node
{
     item key; //truong key cua du lieu, ban dat ten la gì thi tuy
     Node *Left; // Con tro trái
     Node *Right; // con tro phai
};
typedef Node *Tree;  //cay

Một node sẽ gồm key để lưu dữ liệu, tiếp theo là con trỏ trái và con trỏ phải dùng để biểu diễn con trái và con phái.

2.2 Hàm tạo một Node

Tạo một node có giá trị x cấu trúc cây nhị phân. Hàm này sẽ giúp bạn tạo một node để chèn phần tử vào Cây.

Node* makeNode(Node *p, item x) // chen 1 Node vao cay
{
    p = (Node *) malloc(sizeof(Node)); // cap bo nho cho con tro.
   // p = new Node*;  // cap bo nho cho con tro voi C++
    p->key = x;
    p->Left = p->Right = NULL;
    return p;   // ok
}

Vì nó là một node đơn, nên ta sẽ truyền giá trị cho node. Hai con trái và phải đều đặt giá trị NULL ( trống ).

2.3 Nhập dữ liệu cho cây nhị phân – Create Binary Tree

Hàm nhập dữ liệu từ bàn phím khá quan trọng. Các bài kiểm tra và bài tập ứng dụng thấp của cây nhị phân đều sử dụng hàm này.

Điều kiện nhập của mình ở đây là nếu nhập bằng 0 thì sẽ kết thúc nhập. Thứ tự nhập như sau:

Nhập node gốc trước, nếu node này bằng 0 thì kết thúc nhập ( return NULL );
Nếu khác 0, gọi đệ quy nhập con bên trái
Gọi đệ quy nhập con phải.
Trả về node vừa nhập: Return P.

// Ham nhap du lieu key tu ban phim 
Node*  CreateTree(Node *p,item x)   
{   
        printf("Node: "); scanf("%d", &x);
        if (x==0)return NULL;
      	p=	makeNode(p,x);
		printf("Nhap con trai cua node %d: ",x);
        p->Left=CreateTree(p->Left,x);
        printf("Nhap con phai cua node %d: ",x);
        p->Right=CreateTree(p->Right,x);
	return p;	    
}

3. Các phép duyệt cây

Có 3 phương pháp duyệt cây đó là:

  1. Duyệt theo thứ tự trước: PreOder ( N -L – R)
  2. Duyêt theo thứ tự giữa: InOder ( L – N – R)
  3. Duyệt theo thứ tự sau: PostOrder ( L – R – N)

Ví dụ cây nhị phân ở đầu bài viết:

cay nhi phan binary tree

Kết quả duyệt trước: 1 2 4 8 9 5 10 11 3 6 13 7 14
Kết quả duyệt giữa: 8 4 9 2 10 5 11 1 6 13 3 14 7
Kết quả duyệt sau: 8 9 4 10 11 5 2 13 6 14 7 3 1

3.1 Duyệt theo thứ tự trước

Duyệt theo thứ tự trước Preoder: Theo thứ tự Node – Left – Right ( N – L – R )
Tức là sẽ duyệt gốc trước, sau đó duyệt con trái, rồi con phải.

Code C:

//duyet theo thu tu truoc
void NLR(Tree T)
{
     if(T!=NULL)
     {printf("%d   ",T->key);
      NLR(T->Left);  // de quy duyet con trai
      NLR(T->Right); // De quy duyet con phai
     }
}

3.2 Duyệt theo thứ tự giữa – Inoder

Cách duyệt: Left – Node – Right ( LNR) tức là chúng ta sẽ duyệt con trái, sau đó duyệt gốc, rồi duyệt con phải.

Code C:

// Duyet theo LNR thu tu giua
void LNR(Tree T)
{
     if(T!=NULL)
     {
      LNR(T->Left);
      printf("%d   ",T->key);//duyet goc
      LNR(T->Right);
     }
}

3.3 Duyệt theo thứ tự sau PostOder

Thăm các gốc lần lượt theo thứ tự như sau: Con trái, con phải, rồi mới tới gốc. Left – Right – Node ( LRN)

Code:

//duyet theo thu tu sau
void LRN(Tree T)
{
     if(T!=NULL)
     {
      LRN(T->Left);
      LRN(T->Right);
	  printf("%d   ",T->key);
     }
}

4. Các hàm khác trên cây nhị phân

Giới thiệu thêm một số hàm thường dùng đối với cây nhị phân. Đây có thể là câu hỏi thêm, bài tập ứng dụng hoặc cũng sử dụng trong nhiều trường hợp riêng.

4.1 Hàm tìm kiếm node có khóa x trên cây

Thuật toán mình sử dụng:

Nếu Key tại Node T = x thì return T.
Nếu T = NULL return NULL
Khai báo Tree P. Gọi đệ quy tìm con trái. Nếu con trái không có, tìm con phải.

 // tim nut co key x
Node* searchKey(Tree T, item x)    
{  Tree p;
    if (T->key==x)return T;
    if(T==NULL) return NULL;
    p=searchKey(T->Left,x);
    if(p==NULL)searchKey(T->Right,x);

4.2 Trả về con trái, con phải, kiểm tra node lá, đếm số node

Hàm trả về con trái, hàm trả về con phải:

Node * leftChild(Tree T){
	if(T!=NULL)return T->Left;
	else return NULL;
} 
Node * rightChild(Tree T){
	if(T!=NULL)return T->Right;
	else return NULL;
}   

Hàm kiểm tra Node lá, đếm số node trên cây.
Node là là node không có con.

Code hoàn chỉnh một bài toán về cây nhị phân cơ bản:

int isLeaf(Tree T){
	if(T!=NULL)
		return (T->Left==NULL && T->Right==NULL);
	else return NULL;
}

// Dem so node tren cay
int numberNode(Tree T){
	
	if(T==NULL)return 0;
	else return (1+numberNode(leftChild(T))+numberNode(rightChild(T)));
}

Hàm kiểm tra số node trên cây nhị phân. Gọi đệ quy cho con trái, gọi đệ quy cho con phải là được.

Ngoài ra còn có hàm

#include<stdlib.h>
#include<stdio.h>
typedef int item; //kieu item la kieu nguyen
struct Node
{
     item key; //truong key cua du lieu
     Node *Left, *Right; //con trai va con phai
};
typedef Node *Tree;  //cay
  
Node* makeNode(Node *p, item x) // chen 1 Node vao cay
{
    p = (Node *) malloc(sizeof(Node));
    p->key = x;
    p->Left = p->Right = NULL;
    return p;   // ok
}

Node*  CreateTree(Node *p,item x)        // nhap cay
{   
        printf("Node: "); scanf("%d", &x);
        if (x==0)return NULL;
      	p=	makeNode(p,x);
		printf("Nhap con trai cua node %d: ",x);
        p->Left=CreateTree(p->Left,x);
        printf("Nhap con phai cua node %d: ",x);
        p->Right=CreateTree(p->Right,x);
	return p;	    
}
  
// Duyet theo LNR thu tu giua
void LNR(Tree T)
{
     if(T!=NULL)
     {
      LNR(T->Left);
      printf("%d   ",T->key);//duyet goc
      LNR(T->Right);
     }
}
void NLR(Tree T)//duyet theo thu tu truoc
{
     if(T!=NULL)
     {printf("%d   ",T->key);
      NLR(T->Left);
      NLR(T->Right);
     }
}
void LRN(Tree T)//duyet theo thu tu sau
{
     if(T!=NULL)
     {
      LRN(T->Left);
      LRN(T->Right);
	  printf("%d   ",T->key);
     }
}
  
Node* searchKey(Tree T, item x)     // tim nut co key x
{  Tree p;
    if (T->key==x)return T;
    if(T==NULL) return NULL;
    p=searchKey(T->Left,x);
    if(p==NULL)searchKey(T->Right,x);
    
}
Node * leftChild(Tree T){
	if(T!=NULL)return T->Left;
	else return NULL;
} 
Node * rightChild(Tree T){
	if(T!=NULL)return T->Right;
	else return NULL;
}   
int isLeaf(Tree T){
	if(T!=NULL)
		return (T->Left==NULL&&T->Right==NULL);
	else return NULL;
}
int numberNode(Tree T){
	
	if(T==NULL)return 0;
	else return (1+numberNode(leftChild(T))+numberNode(rightChild(T)));
}
int main()
{
    Tree T;
    T=NULL; //Tao cay rong
    Node *p=NULL;item x;
	printf("Nhap 0 de chuyen sang nhap node khac hoac thoat"); 
    T=CreateTree(p,x); //Nhap cay
    	printf("Duyet cay theo thu tu giua LNR: \n");
    		LNR(T);
    		printf("\n");
		  		 printf("Duyet cay theo thu tu truoc NLR: \n");
   			 NLR(T);
   			 printf("\n");

    	    printf("Duyet cay theo thu tu sau LRN: \n");
   			LRN(T);
   			printf("\n");
//    Node *P;
//    
//    printf("Nhap vao key can tim: ");
//    scanf("%d", &x);
//    P = searchKey(T, x);
//    if (P != NULL) printf("Tim thay key %d\n", P->key);
//    else printf("Key %d khong co trong cay\n", x);
//  
//    if (delKey(T, x)) printf("Xoa thanh cong\n");
//    else printf("Khong tim thay key %d can xoan", x);
//    printf("Duyet cay theo thu tu giua: \n");
//    LNR(T);
//    printf("\n");
//}while(chon!=4);
    return 0;
}

LEAVE A REPLY

Please enter your comment!
Please enter your name here