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. CountLeafNodes function to count the number of leaf nodes in the BST and return the result. For example: Test Result Node* root; 1 Init(root); int n = 4; DataType V[] = {4,1,2,3}; InsertNodes(root,V,n); int c = CountLeafNodes(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 leaf nodes in the BST
int CountLeafNodes(Node* root) { if (root == nullptr) { return 0; }
if (root->Left == nullptr && root->Right == nullptr) {
return 1; // This node is a leaf }
// Recursively count leaf nodes in left and right subtrees
return CountLeafNodes(root->Left) + CountLeafNodes(root->Right); } Go Tes Expected t t Node* root; 1 1 Init(root); int n = 4; DataType V[] = {4,1,2,3}; InsertNodes(root,V,n); int c = CountLeafNodes(root);
cout << c << endl; Passed all tests!