Homework week 5
Trees
1. Given a list of integer numbers: 2, 1, 10, 6, 3, 8, 7, 13, 20.
- Draw the binary search tree
- Draw the binary search tree after inserting values: 14, 0, 35
- Draw the binary search tree after deleting: 6, 13, 35
2. Given a list of integer numbers: 2, 1, 10, 6, 3, 8, 7, 13, 20.
- Draw the heap tree
- Draw the heap tree after inserting values: 14, 0, 35
- Draw the heap tree after deleting: 6, 13, 35
3. Given a tree, your task is to write a program with following functions
● Calculate the height of the tree.
● Write out the order of nodes following the preorder traversal.
● Write out the order of nodes following the postorder traversal.
● Check if the given tree is a binary tree? If yes, write out the order of nodes in inorder
traversal.
Input: Data come from the keyboard:
- The first line contains integer numbers N, M indicating the number of nodes, and edges,
respectively.
- M following lines each contains two integer numbers u, v indicating that u is the parent of
v.
Output: Data are written to the screen as following:
- The height of the tree
- The order of nodes in preorder traversal
- The order of nodes in postorder traversal
- The order of nodes in the inorder if the tree is binary. Otherwise, write the string ‘NOT
BINARY TREE’
Keyboard Screen
54 2
12 12453
13 45231
24 4 2513
25
#include <iostream>
#include <cmath>
#include <set>
using namespace std;
struct Node{
int data;
Node* left;
Node* right;
Node(int val) {
data = val;
this->left = NULL;
this->right = NULL;
}
};
Node* root = new Node(1);
bool isBinaryTree(int tree[][2], int n) {
int count;
for (int i = 0; i < n; i++) {
count = 0;
for (int j = i; j < n; j++) {
if (tree[j][0] == tree[i][0]) {
count++;
}
if (count > 3) return false;
}
}
return true;
}
Node* find(Node*p, int x) { // tim vi tri node x
if(p->data == x) {
return p;
} else {
if (p->left != NULL) {
find(p->left, x);
}
if (p->right != NULL) {
find(p->right, x);
}
}
}
void initBT(int tree[][2], int n) {
Node* p = root;
for (int i = 0; i < n; i++) {
p = find(root, tree[i][0]);
Node* newNode = new Node(tree[i][1]);
if (p->left == NULL) {
p->left = newNode;
} else {
p->right = newNode;
}
}
}
int height(Node* root) {
if (!root) {
return 0;
} else {
return 1 + max(height(root->left), height(root->right));
}
}
void preOrder(Node* root) {
if (root != NULL) {
cout << root->data << " ";
preOrder(root->left);
preOrder(root->right);
}
}
void inOrder(Node* root) {
if (root != NULL) {
inOrder(root->left);
cout << root->data << " ";
inOrder(root->right);
}
}
void postOrder(Node* root) {
if (root != NULL) {
postOrder(root->left);
postOrder(root->right);
cout << root->data << " ";
}
}
int main() {
int N, M; // N: so nut, M: so canh
cin >> N >> M;
int tree[100][2];
int n = N-1; // n: so nut (khong tinh nut 1)
// input
for (int i = 0; i < n; i++) {
cin >> tree[i][0] >> tree[i][1];
}
// check is binary tree
if (!isBinaryTree(tree, n)) {
cout << "NOT BINARY TREE\n";
return 0;
}
// neu la binary tree
initBT(tree, n);
preOrder(root);
cout << "\n";
inOrder(root);
cout << "\n";
postOrder(root);
cout << "\n";
return 0;
}
