Bài tập thực hành Môn Câu trúc dữ liệu giải thuật | Trường Đại học Công nghiệp Thành phố Hồ Chí Minh

typedef int DataType; struct Node { Node* Left; Node* Right; DataType Data; }
Implement the following functions for binary search tree (BST):
1. Init function to init an empty BST
2. CreateNode function has an input parameter to allocate memory,
store the input value and return the address of the memory of the tree node.
3. InsertNodes function to insert each element in array into the BST
4. CountNodes function to count the number of nodes in the BST and return the result. For example: Test Result Node* root; 4 Init(root); int n = 4; DataType V[] = {4,1,2,3}; InsertNodes(root,V,n); int c = CountNodes(root);
cout << c << endl; #include typedef int DataType; struct Node { Node* Left; Node* Right; DataType Data; };
// Function to initialize an empty BST void Init(Node*& root) {
root = nullptr; // Set root pointer to null to indicate an empty tree }
// Function to create a new node with given data
Node* CreateNode(DataType value) { Node* newNode = new Node; newNode->Data = value; newNode->Left = nullptr; newNode->Right = nullptr; return newNode; }
// Function to insert a single node into BST
Node* InsertNode(Node*& root, DataType value) {
// If the tree is empty, create a new node as the root if (root == nullptr) { root = CreateNode(value); } else {
// Otherwise, traverse the tree to find the appropriate position
if (value < root->Data) {
root->Left = InsertNode(root->Left, value);
} else if (value > root->Data) {
root->Right = InsertNode(root->Right, value); } } return root; }
// Function to insert multiple nodes from an array into BST
void InsertNodes(Node*& root, DataType V[], int n) {
for (int i = 0; i < n; ++i) { InsertNode(root, V[i]); } }
// Function to count the number of nodes in the BST int CountNodes(Node* root) { if (root == nullptr) { return 0; }
return 1 + CountNodes(root->Left) + CountNodes(root->Right); } Tes Expected Got t Node* root; 4 4 Init(root); int n = 4; DataType V[] = {4,1,2,3}; InsertNodes(root,V,n); int c = CountNodes(root);
cout << c << endl; Node* root; 5 5 Init(root); int n = 5; DataType V[] = {3,1,9,2,4}; InsertNodes(root,V,n); int c = CountNodes(root);
cout << c << endl; Node* root; 9 9 Init(root); int n = 10;
DataType V[] = {45,15,79,10,20,55,45,90,12,50}; InsertNodes(root,V,n); int c = CountNodes(root);
cout << c << endl; Node* root; 10 1 Init(root); 0 int n = 10;
DataType V[] = {1, 5, 8, 9, 13, 15, 38, 45, 46, 47}; InsertNodes(root,V,n); int c = CountNodes(root);
cout << c << endl; Passed all tests!