Bài tập Binary Tree Search - Cây nhị phân tìm kiếm trong C++

Một bài tập nho nhỏ về cây nhị phân tìm kiếm

| Yêu cầu

Cho cây nhị phân các số nguyên với các giá trị giả sử không trùng nhau.

Viết chương trình thực hiện các yêu cầu sau:

Nhập giá trị trong cây.
Xuất giá trị trong cây theo thứ tự NLR.
Xuất giá trị trong cây theo thứ tự LNR.
Xuất giá trị trong cây theo thứ tự LRN.
Tính tổng giá trị các nút trong cây.
Tính tổng giá trị các nút lá trong cây.
Tìm giá trị lớn nhất trong cây.
Tính chiều cao của cây.
In ra các nút ở mức k của cây theo thứ tự LNR.
Tính tống các nút ở mức k của cây.
Đếm số lượng nút trong cây.
Đếm số lượng nút lá trong cây
Đếm số lượng nút có đúng 1 con trong cây
Xuất ra giá trị và mức của các nút trong cây theo thứ tự LNR.
In ra mức của nút có giá trị k. Nếu không có giá trị k xuất ra thông báo:"Khong co nut k".
Tìm nút chứa giá trị k và xuất ra mức và chiều cao và bậc tại nút đó. Biết k là một giá trị thuộc cây nhị phân.
Xóa một node có giá trị k trong cây nhị phân.

| Code

Cấu trúc dữ liệu của một nút

struct NODE

{

int data;

struct NODE* pLeft;

struct NODE* pRight;

};

Cấu trúc dữ liệu của cây

typedef NODE* TREE;

Prototype

void CreateTree(TREE&);

NODE* CreateNode(int);

void InsertNode(TREE&, NODE*);

void Input(TREE&);

void OutputNLR(TREE);

void OutputLNR(TREE);

void OutputLRN(TREE);

int SumOfAllNodes(TREE root, int& sum);

int SumOfLeafNodes(TREE root, int& sum);

int MaxNode(TREE);

int MinNode(TREE);

int HeightNode(TREE);

void OutputLevel_K_LNR(TREE root, int level, int i);

int SumOfLevelNode(TREE root, int level, int i, int& sum);

int CountAllNodes(TREE root, int& count);

int CountLeafNodes(TREE root, int& count);

int CountOneChildNode(TREE root, int& count);

void OutputValueAndLevel_LNR_AllNode(TREE root, int level);

NODE* SearchNode(TREE root, int k);

int GetLevel(TREE root, NODE* p, int level);

int GetDegree(TREE root);

void DeleteNode(TREE& root, int k);

void ReplaceNode(TREE& p, TREE& root);

Tạo một cây rỗng

void CreateTree(TREE& root)

{

root = NULL;

}

Tạo một nút có trường data bằng x

NODE* CreateNode(int x)

{

NODE* p = new NODE;

if (p == NULL)

return NULL;

else

{

p->data = x;

p->pLeft = p->pRight = NULL;

return p;

}

Thêm một nút vào cây nhị phân

void InsertNode(TREE& root, NODE* p)

{

if (root == NULL)

root = p;

else

{

if (p->data < root->data)

InsertNode(root->pLeft, p);

else if (p->data > root->data)

InsertNode(root->pRight, p);

else

return;

}

Nhập giá trị cho cây

// cau 1: Nhap gia tri cho cay

void Input(TREE& root)

{

CreateTree(root);

cout << "Nhap so nut: ";

int n;

cin >> n;

for (int i = 0; i < n; i++)

{

int x;

cout << "Nhap x: ";

cin >> x;

NODE* p = CreateNode(x);

InsertNode(root, p);

}

Xuất giá trị trong cây nhị phân theo thứ tự NLR

// cau 2: Xuat gia tri NLR

void OutputNLR(TREE root)

{

if (root != NULL)

{

cout << setw(5) << root->data;

OutputNLR(root->pLeft);

OutputNLR(root->pRight);

}

Xuất giá trị trong cây nhị phân theo thứ tự LNR

// cau 3: Xuat gia tri LNR

void OutputLNR(TREE root)

{

if (root != NULL)

{

OutputLNR(root->pLeft);

cout << setw(5) << root->data;

OutputLNR(root->pRight);

}

Xuất giá trị trong cây nhị phân theo thứ tự LRN

// cau 4: Xuat gia tri LRN

void OutputLRN(TREE root)

{

if (root != NULL)

{

OutputLRN(root->pLeft);

OutputLRN(root->pRight);

cout << setw(5) << root->data;

}

Tính tổng giá trị các nút trong cây

// cau 5: Tong gia tri cac nut trong cay

int SumOfAllNodes(TREE root, int& sum)

{

if (root != NULL)

{

sum = sum + root->data;

SumOfAllNodes(root->pLeft, sum);

SumOfAllNodes(root->pRight, sum);

return sum;

}

return 0;

}

Tính tổng giá trị các nút lá trong cây

// cau 6: Tong gia tri cac nut LA trong cay

int SumOfLeafNodes(TREE root, int& sum)

{

if (root != NULL)

{

if (root->pLeft == NULL && root->pRight == NULL)

sum = sum + root->data;

SumOfLeafNodes(root->pLeft, sum);

SumOfLeafNodes(root->pRight, sum);

return sum;

}

return 0;

}

Tìm giá trị lớn nhất trong cây

// cau 7: Tim gia tri lon nhat trong cay

int MaxNode(TREE root)

{

if (root->pRight == NULL)

return root->data;

else return MaxNode(root->pRight);

}

Tìm giá trị nhỏ nhất trong cây

// Tim gia tri nho nhat trong cay

int MinNode(TREE root)

{

if (root->pLeft == NULL)

return root->data;

else return MinNode(root->pLeft);

}

Tính chiều cao của nút/root

// cau 8: Chieu cao cua nut

int HeightNode(TREE root)

{

if (root != NULL)

{

int a = HeightNode(root->pLeft);

int b = HeightNode(root->pRight);

if (a > b)

return a + 1;

return b + 1;

}

return 0;

}

In ra các nút ở mức K của cây theo thứ tự LNR

// cau 9: In ra cac nut o muc K cua cay theo LNR

void OutputLevel_K_LNR(TREE root, int level, int i)

{

if (root != NULL)

{

OutputLevel_K_LNR(root->pLeft, level, i + 1);

if (level == i)

cout << setw(5) << root->data;

OutputLevel_K_LNR(root->pRight, level, i + 1);

}

Tính tổng giá trị các nút ở mức K của cây

// cau 10: Tong cac nut o muc K cua cay

int SumOfLevelNode(TREE root, int level, int i, int& sum)

{

if (root != NULL)

{

if (level == i)

sum = sum + root->data;

SumOfLevelNode(root->pLeft, level, i + 1, sum);

SumOfLevelNode(root->pRight, level, i + 1, sum);

return sum;

}

return 0;

}

Đếm số lượng các nút trong cây

// cau 11: Dem so luong nut trong cay

int CountAllNodes(TREE root, int& count)

{

if (root != NULL)

{

count++;

CountAllNodes(root->pLeft, count);

CountAllNodes(root->pRight, count);

return count;

}

return 0;

}

Đếm số lượng các nút lá trong cây

// cau 12: Dem so luong nut la trong cay

int CountLeafNodes(TREE root, int& count)

{

if (root != NULL)

{

if (root->pLeft == NULL && root->pRight == NULL)

count++;

CountLeafNodes(root->pLeft, count);

CountLeafNodes(root->pRight, count);

return count;

}

return 0;

}

Đếm số lượng nút có đúng 1 con trong cây

// cau 13: Dem so luong nut co dung 1 con trong cay

int CountOneChildNode(TREE root, int& count)

{

if (root != NULL)

{

if ((root->pLeft == NULL && root->pRight != NULL) || (root->pLeft != NULL && root->pRight == NULL))

count++;

CountOneChildNode(root->pLeft, count);

CountOneChildNode(root->pRight, count);

return count;

}

return 0;

}

Xuất ra các giá trị và mức tương ứng của các nút trong cây theo thứ tự LNR

// cau 14: Xuat ra gia tri va muc cua cac nut trong cay theo thu tu LNR

void OutputValueAndLevel_LNR_AllNode(TREE root, int level)

{

if (root != NULL)

{

OutputValueAndLevel_LNR_AllNode(root->pLeft, level + 1);

cout << "\tGia tri: " << root->data << "\tMuc: " << level << endl;

OutputValueAndLevel_LNR_AllNode(root->pRight, level + 1);

}

Lấy mức (level) của nút bất kỳ

// cau 15: Muc cua node

int GetLevel(TREE root, NODE* p, int level)

{

if (root != NULL)

{

if (root->data == p->data) //&& level == i)

return level;

else if (root->data > p->data)

return GetLevel(root->pLeft, p, level + 1);

else return GetLevel(root->pRight, p, level + 1);

}

return 0;

}

Tìm 1 nút có khoá bằng k trên cây

// cau 16

// Tim nut co gia tri k

NODE* SearchNode(TREE root, int k)

{

if (root != NULL)

{

if (root->data == k)

return root;

else if (root->data > k)

return SearchNode(root->pLeft, k);

else return SearchNode(root->pRight, k);

}

return NULL;

}

Lấy bặc (degree) của nút bất kỳ

// Tim bac cua nut

int GetDegree(TREE root)

{

if (root->pLeft != NULL && root->pRight != NULL)

return 2;

if ((root->pLeft == NULL && root->pRight != NULL) || (root->pLeft != NULL && root->pRight == NULL))

return 1;

return 0;

}

Xoá một nút có giá trị k trên cây

// cau 17: Xoa mot nut co gia tri k

void DeleteNode(TREE& root, int k)

{

if (root != NULL)

{

if (root->data > k)

DeleteNode(root->pLeft, k);

else if (root->data < k)

DeleteNode(root->pRight, k);

else

{

NODE* p = root;

if (root->pLeft == NULL)

root = root->pRight;

else if (root->pRight == NULL)

root = root->pLeft;

else ReplaceNode(p, root->pRight);

delete p;

}

Tìm phần tử thế mạng

// Tim phan tu the mang

void ReplaceNode(TREE& p, TREE& root)

{

if (root->pLeft != NULL)

ReplaceNode(p, root->pLeft);

else

{

p->data = root->data;

p = root;

root = root->pRight;

}

Main.cpp

#include<iostream>

#include <iomanip>

using namespace std;

int main()

{

TREE root;

cout << "1. Nhap gia tri cho cay\n";

Input(root);

cout << "2. Output NLR: ";

OutputNLR(root);

cout << endl;

cout << "3. Output LNR: ";

OutputLNR(root);

cout << endl;

cout << "4. Output LRN: ";

OutputLRN(root);

cout << endl;

int sumNodes = 0, sumLeafNodes = 0;

cout << "5. Tong gia tri cac nut trong cay: " << SumOfAllNodes(root, sumNodes) << endl;

cout << "6. Tong gia tri cac nut la trong cay: " << SumOfLeafNodes(root, sumLeafNodes) << endl;

cout << "7. Gia tri lon nhat trong cay: " << MaxNode(root) << endl;

cout << "8. Chieu cao cua cay: " << HeightNode(root) << endl;

cout << "9. Nhap level K: ";

int level;

cin >> level;

cout << "Cac nut o muc " << level << " co gia tri la: ";

OutputLevel_K_LNR(root, level, 0);

cout << endl;

int sumLevel = 0;

cout << "10. Tong cac nut o muc " << level << " cua cay: " << SumOfLevelNode(root, level, 0, sumLevel) << endl;

int countNode = 0, countLeaf = 0, countOneChild = 0;

cout << "11. So luong nut trong cay: " << CountAllNodes(root, countNode) << endl;

cout << "12. So luong nut la trong cay: " << CountLeafNodes(root, countLeaf) << endl;

cout << "13. So luong nut co dung 1 con trong cay: " << CountOneChildNode(root, countOneChild) << endl;

cout << "14. Gia tri cua cac nut va muc tuong ung:\n";

OutputValueAndLevel_LNR_AllNode(root, 0);

cout << "15+16. Nhap gia tri cua nut can tim: ";

int x;

cin >> x;

NODE* p = SearchNode(root, x);

if (p != NULL)

{

cout << "\tMuc cua nut: " << GetLevel(root, p, 0) << endl;

cout << "\tChieu cao cua nut: " << HeightNode(p) << endl;

cout << "\tBac cua nut: " << GetDegree(p) << endl;

} else cout << "Khong co nut co gia tri tren.\n";

cout << "17. Nhap gia tri cua nut can xoa: ";

int k;

cin >> k;

DeleteNode(root, k);

cout << "Output LNR: ";

OutputLNR(root);

cout << endl;

system("pause");

return 0;

}

Search

xuixaicat