Explore BrainMass
Share

Implementing Operations on Binary Trees

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

Consider the following definition of a Binary Tree structure:

typedef struct BTnode *node;
struct BTnode {
int key;
node left;
node right;
};

1. Write a function in C programming language that can find and return the height of a Binary Tree.
2. Write a function in C programming language that can find and return the cost of the most expensive path from the root of a Binary Tree to a leaf.
3. Write a function in C programming language that finds if a particular Binary Tree is balanced.

More explanations are provided in the attached document.

© BrainMass Inc. brainmass.com October 25, 2018, 6:09 am ad1c9bdddf
https://brainmass.com/computer-science/trees/implementing-operations-binary-trees-450363

Attachments

Solution Preview

Please find attached 450363.c containing just the function implementations. Code has been commented well, but even without that logic is quite clear as it is based on recursion. This implementation makes use of an auxiliary function min_height in determining whether a tree is balanced as per the given criteria or not.

#include <stdio.h>

/* Binary Tree structure */

typedef struct BTnode *node;
struct BTnode {
int key;
node left;
node right;
};

/*
* This function finds and returns the height of a Binary Tree.
*
* The height of a binary tree is the length of the longest path from root of
* the Binary Tree to a leaf.
*
* This implementation considers that the height of a null tree is 0 and that of
* a single node tree is 1.
*/

int height (node root)
{
if (root == (node) NULL)
return 0;
else
{
...

Solution Summary

Attached solution contains just the function implementations. Code has been commented well, but even without that logic is quite clear as it is based on recursion. This implementation makes use of an auxiliary function min_height in determining whether a tree is balanced as per the given criteria or not.

$2.19
See Also This Related BrainMass Solution

Java Binary Search Tree Solution

Dear OTA -

I need a Java solution named TestGRE.java with a main method to test a Student Graduate Record Examination Score Managment System using BinarySearchTree java classes.

The solution should use the attached Student class.

Also, sample input that can be used is contained in the attached StudData.dat file.

The TestGRE should return the following when run from the command line:

C:JavaBinSearchTree>java TestGRE
Please Enter a valid FileName: StudData.dat

Choose an operation:
1: contains (string)
2: remove (string)
3: add (string)
4: print (traversal order)
9: stop Testing

Enter choice: 4
Choose a traversal order:
1: Preorder
2: Inorder
3: Postorder
3
The tree in Postorder is:
Brown in NJ earns 89 verbal, and 67 quantitative.
Arnold in VA earns 77 verbal, and 88 quantitative.
Thompson in NY earns 99 verbal, and 99 quantitative.
John in VA earns 89 verbal, and 89 quantitative.
Conner in NY earns 98 verbal, and 100 quantitative.
Smith in MD earns 89 verbal, and 89 quantitative.

Choose an operation:
1: contains (string)
2: remove (string)
3: add (string)
4: print (traversal order)
9: stop Testing

Enter choice: 2
Enter Student's Name to remove: Arnold
Verbal Score: 77
Quantitative Score: 88
State: VA
remove(Arnold, 77, 88, VA) returns true

Choose an operation:
1: contains (string)
2: remove (string)
3: add (string)
4: print (traversal order)
9: stop Testing

Enter choice: 4
Choose a traversal order:
1: Preorder
2: Inorder
3: Postorder
3
The tree in Postorder is:
Brown in NJ earns 89 verbal, and 67 quantitative.
Thompson in NY earns 99 verbal, and 99 quantitative.
John in VA earns 89 verbal, and 89 quantitative.
Conner in NY earns 98 verbal, and 100 quantitative.
Smith in MD earns 89 verbal, and 89 quantitative.

Choose an operation:
1: contains (string)
2: remove (string)
3: add (string)
4: print (traversal order)
9: stop Testing

Enter choice: 3
Enter Student's Name to add: Arnold
Verbal Score: 77
Quantitative Score: 78
State: CT

Choose an operation:
1: contains (string)
2: remove (string)
3: add (string)
4: print (traversal order)
9: stop Testing

Enter choice: 4
Choose a traversal order:
1: Preorder
2: Inorder
3: Postorder
2
The tree in Inorder is:
Arnold in CT earns 77 verbal, and 78 quantitative.
Brown in NJ earns 89 verbal, and 67 quantitative.
John in VA earns 89 verbal, and 89 quantitative.
Thompson in NY earns 99 verbal, and 99 quantitative.
Smith in MD earns 89 verbal, and 89 quantitative.
Conner in NY earns 98 verbal, and 100 quantitative.

Choose an operation:
1: contains (string)
2: remove (string)
3: add (string)
4: print (traversal order)
9: stop Testing

Enter choice: 9

C:JavaBinSearchTree>

Now I just need the following missing code to test this system, and to make this all work:

import java.util.*;
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.File;
import java.io.IOException;

public class TestGRE
{
public static void main(String[] args) throws IOException
{

....

}

View Full Posting Details