III. Project
Given an adjacency matrix
1- Check if the adjacency matrix represents a m-ary unrooted tree m>=2. Otherwise
terminate.
2- Allow the user to choose a node as the root.
3- Convert the m-ary tree in the adjacency matrix to a binary tree in a binary tree data
structure taking the node chosen by the user as the root.
4- If the tree is not balanced, traverse the tree inorder and insert the traversed nodes in a
Balanced Binary search tree (AVL tree).
5- Traverse the final AVL tree in preorder, inorder and postorder fashions.
Answers
Answer:
Given an ancestor matrix mat[n][n] where Ancestor matrix is defined as below.
mat[i][j] = 1 if i is ancestor of j
mat[i][j] = 0, otherwise
Construct a Binary Tree from given ancestor matrix where all its values of nodes are from 0 to n-1.
It may be assumed that the input provided the program is valid and tree can be constructed out of it.
Many Binary trees can be constructed from one input. The program will construct any one of them.
Examples:
Input: 0 1 1
0 0 0
0 0 0
Output: Root of one of the below trees.
0 0
/ \ OR / \
1 2 2 1
Input: 0 0 0 0 0 0
1 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
1 1 1 1 1 0
Output: Root of one of the below trees.
5 5 5
/ \ / \ / \
1 2 OR 2 1 OR 1 2 OR ....
/ \ / / / \ / \ /
0 4 3 3 0 4 4 0 3
There are different possible outputs because ancestor
matrix doesn't store that which child is left and which
is right.
This problem is mainly reverse of below problem.