Trees 34. Explain the following terms: trees, root, descendants, ancestors, leav
ID: 3723553 • Letter: T
Question
Trees 34. Explain the following terms: trees, root, descendants, ancestors, leaves, siblings, 35. Given a tree, identify the [root | leaves tree height | tree size]. Given a tree, 36. Explain how to store a binary tree using an [array linked structure]. For an parent, child, depth, node height, tree height, full tree, complete tree, balanced tree. label each node with its [depth | height]. Given a tree, identify if it is [full| complete | balanced]. array, explain how to find the child/parent of a given node based only on the index of that element. For a linked structure, write the code for a node. Can you generalize the idea to k-ary trees? 7. Explain how to represent trees using "first-child next-sibling" approach. Be able to convert between different representations. 38. Write a recursive method to calculate the [size | height] of a tree.Explanation / Answer
Answer(38) Algorithm: size(tree)
Algorithm: Height
Program:
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;//data part of node
struct node* left;//left pointer
struct node* right;//right pointer
};
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));//creating new node using malloc function which is pre define.
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Computes the number of nodes in a tree. */
int size(struct node* nodePtr)
{
if (nodePtr==NULL)
return 0;
else
return(size(nodePtr->left) + 1 + size(nodePtr->right));
}
/* Driver program to test size function*/
/*finding height of the tree*/
int height(struct node* node){
if (node==NULL) return 0;
else {
/* compute the depth of each subtree */
int lDepth = height(node->left);
int rDepth = height(node->right);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Size of the tree is %d", size(root));
printf(" Height of the tree is %d", height(root));
getchar();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.