3.5 Tree Code. Be sure to fully test and document all of your code. A. Write a p
ID: 3871967 • Letter: 3
Question
3.5 Tree Code. Be sure to fully test and document all of your code. A. Write a program to store a tree as an array. In your test program, be sure to print the array values, and to print the values in tree "format B. Write a function to add an element to an existing tree. C. Write a function to delete an element from an existing tree. D. Write a function to perform an "in-order" traversal on an existing tree. E. Write a function to perform an "pre-order traversal on an existing tree F. Write a function to perform an "post-order traversal on an existing tree. G. Write a function to perform an "level-order" traversal on an existing tree. H. Write a function to find the children of a specified node. I. Write a function to find the parent of a specified node. 3.6 Re-write the functions above using a vector from the + library.Explanation / Answer
chegg tree array
[Draft]This message hasn't been sent.
Saved on: Fri 9/29/2017 1:55 PM
To store a tree as an array, I have used some rules. Below examples will clarify them.
Input array: {1, 5, 5, 2, 2, -1, 3}
Output tree:
5
/
1 2
/ /
0 3 4
/
6
Index of -1 is 5. So 5 is root.
5 is present at indexes 1 and 2. So 1 and 2 are
children of 5.
1 is present at index 0, so 0 is child of 1.
2 is present at indexes 3 and 4. So 3 and 4 are
children of 2.
3 is present at index 6, so 6 is child of 3.
Following is the code for the same:
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int key;
struct Node *left, *right;
};
Node *newNode(int key)
{
Node *temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
void createNode(int parent[], int i, Node *created[], Node **root)
{
if (created[i] != NULL)
return;
created[i] = newNode(i);
if (parent[i] == -1)
{
*root = created[i];
return;
}
if (created[parent[i]] == NULL)
createNode(parent, parent[i], created, root);
Node *p = created[parent[i]];
if (p->left == NULL)
p->left = created[i];
else
p->right = created[i];
}
Node *createTree(int parent[], int n)
{
Node *created[n];
for (int i=0; i<n; i++)
created[i] = NULL;
Node *root = NULL;
for (int i=0; i<n; i++)
createNode(parent, i, created, &root);
return root;
}
void inorder(Node *root)
{
if (root != NULL)
{
inorder(root->left);
cout << root->key << " ";
inorder(root->right);
}
}
int main()
{
int parent[] = {1, 5, 5, 2, 2, -1, 3};
int n = sizeof parent / sizeof parent[0];
Node *root = createTree(parent, n);
cout << "Inorder Traversal is as follows: ";
inorder(root);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.