Các thao tác cơ bản trên cây nhị phân (Binary Tree)

1. Biểu diễn cây nhị phân

Cây nhị phân là một cấu trúc dữ liệu bao gồm các nút được kết nối với nhau theo quan hệ cha con với mỗi nút cha có tối đa 2 nút con. Mỗi nút của cây nhị phân sẽ lưu các thông tin sau:

• • Giá trị lưu tại nút đó. Giá trị này có thể là bất kỳ kiểu dữ liệu nào. Ví dụ, cây nhị phân lưu trữ các số nguyên thì kiểu dữ liệu là int.
  • Địa chỉ nút gốc của cây con bên trái.
  • Địa chỉ nút gốc của cây con bên phải.

Chúng ta có thể sử dụng danh sách liên kết để biểu diễn cây nhị phân. Đầu tiên, cần định nghĩa một nút trong cấu trúc dữ liệu dạng cây.

struct tNode{
	int data;
	tNode *pLeft, *pRight;
};

Để lưu trữ cây, chúng ta chỉ cần xác định nút gốc của cây.

tNode *root;

2. Các thao tác trên cây nhị phân

Có nhiều thao tác trên cây nhị phân như:

• • Chèn một nút mới vào cây nhị phân
  • Xóa một nút ra khỏi cây nhị phân
  • Duyệt cây nhị phân
  • Tìm kiếm trên cây nhị phân
  • …

Chèn một nút mới vào cây nhị phân để làm con của nút p

void insertNode(tNode *p, int value){
	tNode *node = newNode(value);
	if (p->pLeft == NULL){
		p->pLeft = node;
	}else if (p->pRight == NULL) {
		p->pRight = node;
	}else{
		node->pLeft = p->pLeft;
		p->pLeft = node;
	}
}

Chèn nút mới vào vị trí gốc của cây

void insertNewRoot(int value){
	tNode *node = newNode(value);
	node->pLeft = root;
	root = node;
}

Duyệt cây nhị phân

Có 3 kiểu duyệt chính có thể áp dụng trên cây nhị phân:

• • Duyệt theo thứ tự trước NodeLeftRight (NLR)
  • Duyệt theo thứ tự giữa LeftNodeRight (LNR)
  • Duyệt theo thứ tự sau LeftRightNode (LRN)

Duyệt theo thứ tự trước (NLR)

Xử lý nút đang duyệt trước, sau đó mới duyệt đến các cây con bên trái và bên phải.

void NLR(tNode *root){
	if(root!=NULL){
			if(root!=NULL){
				cout<<root->data<<" ";
			}
			NLR(root->pLeft);
			NLR(root->pRight);
	}
}

Duyệt theo thứ tự giữa (LNR)

Xử lý cây con bên trái trước, rồi mới xử lý nút đang duyệt, cuối cùng xử lý cây con bên phải.

void LNR(tNode *root){
	if(root!=NULL){
		LNR(root->pLeft);
		if(root!=NULL){
			cout<<root->data<<" ";
		}
		LNR(root->pRight);
	}
}

Duyệt theo thứ tự sau (LRN)

Xử lý cây con bên trái trước, rồi xử lý cây con bên phải, cuối cùng mới xử lý nút đang duyệt.

void LRN(tNode *root){
	if(root!=NULL){
		LRN(root->pLeft);
		LRN(root->pRight);
		if(root!=NULL){
			cout<<root->data<<" ";
		}
	}
}

3. Ví dụ chương trình C++ thao tác với cây nhị phân

Cho cây nhị phân như hình bên dưới.

Chương trình C++ thao tác với cây nhị phân như hình trên

#include <iostream>
using namespace std;

struct tNode{
	int data;
	tNode *pLeft, *pRight;
};

tNode *root;

//create new node
tNode *newNode(int data){
	tNode *node = new tNode;
	node->data = data;
	node->pLeft = NULL;
	node->pRight = NULL;
	return node;
}

//insert new Node into tree
void insertNode(tNode *p, int value){
	tNode *node = newNode(value);
	if (p->pLeft == NULL){
		p->pLeft = node;
	}else if (p->pRight == NULL) {
		p->pRight = node;
	}else{
		node->pLeft = p->pLeft;
		p->pLeft = node;
	}
}

//insert new Node into root
void insertNewRoot(int value){
	tNode *node = newNode(value);
	node->pLeft = root;
	root = node;
}

void NLR(tNode *root){
	if(root!=NULL){
			if(root!=NULL){
				cout<<root->data<<" ";
			}
			NLR(root->pLeft);
			NLR(root->pRight);
	}
}

void LNR(tNode *root){
	if(root!=NULL){
		LNR(root->pLeft);
		if(root!=NULL){
			cout<<root->data<<" ";
		}
		LNR(root->pRight);
	}
}

void LRN(tNode *root){
	if(root!=NULL){
		LRN(root->pLeft);
		LRN(root->pRight);
		if(root!=NULL){
			cout<<root->data<<" ";
		}
	}
}

int main()
{
	//create Nodes
	root = newNode(1);
	tNode *node2 = newNode(2);
	tNode *node3 = newNode(3);
	tNode *node4 = newNode(4);
	tNode *node5 = newNode(5);
	tNode *node6 = newNode(6);
	tNode *node7 = newNode(7);
	//assign childnodes
	root->pLeft = node2;
	root->pRight = node3;
	node2->pLeft = node4;
	node2->pRight = node5;
	node5->pLeft = node6;
	node5->pRight = node7;
	//traverse binary tree with NLR
	cout<<"traverse tree with NLR:";
	NLR(root);
	//traverse tree LNR
	cout<<"\ntraverse tree with LNR:";
	LNR(root);
	//traverse tree LRN
	cout<<"\ntraverse tree with LRN:";
	LRN(root);
	//insert new Node into tree
	insertNode(node2, 9);
	//traverse binary tree with NLR after insert new Node
	cout<<"\ntraverse tree with NLR:";
	NLR(root);
	system("pause");
}

Kết quả

traverse tree with NLR:1 2 4 5 6 7 3
traverse tree with LNR:4 2 6 5 7 1 3
traverse tree with LRN:4 6 7 5 2 3 1
traverse tree with NLR:1 2 9 4 5 6 7 3

4. Bài tập cây nhị phân

Cho một cây nhị phân như hình bên dưới:

Viết chương trình C++ với các yêu cầu sau:

a. Tạo cây nhị phân như hình trên.

b. Duyệt cây nhị phân trên theo thứ tự NLR, LNR, LRN.

c. Chèn một nút mới lưu data = 8 làm con bên trái của nút có data = 2. Đồng thời, nút có data = 4 làm con của nút mới lưu data = 8.

d. Tìm nút lưu trữ giá trị data = 5 trong cây nhị phân trên.