Assignment 5 [PDF]

Zitiervorschau

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

25

#include #include #include 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]) {

2513

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 data left); preOrder(root->right); } } void inOrder(Node* root) { if (root != NULL) { inOrder(root->left); cout data right); } } void postOrder(Node* root) { if (root != NULL) { postOrder(root->left); postOrder(root->right); cout data > 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