[URI Online Judge] – 1195 – Binary Search Tree

In computer science, a binary search tree (BST), which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
  • Both the left and right subtrees must also be binary search trees.

The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

For this problem, you will receive many set of numbers and from each set you must to build the BST equivalent. For example, an imput with the sequence of numbers: 8 3 10 14 6 4 13 7 1 will result in the following binary search tree:

Input

The input file contains many test cases. The first line of input contains an integer C (C ≤ 1000), indicating the number of test cases that follow. Each test case contains two lines. The first line contains a number N(1 ≤ N ≤ 500) indicating the amount of numbers that will form each one of the trees. The second line contains the N distinct non-negative numbers, each one separated by a space.

Output

For each input set, you should print the message “Case n:”, where n is the sequential test case number, followed by 3 lines with the pre-order, in-order, post-order transversal for the current tree formatted according to the given example.

Note: None space must be printed after the last number of each line and the program should print a blank line after each test case, even after the last test case.

Sample Input Sample Output
2
3
5 2 7
9
8 3 10 14 6 4 13 7 1
Case 1:
Pre.: 5 2 7
In..: 2 5 7
Post: 2 7 5

Case 2:
Pre.: 8 3 1 6 4 7 10 14 13
In..: 1 3 4 6 7 8 10 13 14
Post: 1 4 7 6 3 13 14 10 8

Solution:

#include <iostream>
#include <cstdlib>
 
using namespace std;
 
struct node {
 int value;
 node *left_node;
 node *right_node;
};
 
void insert_node(node *tree, node *new_node){
 if (new_node->value > tree->value){
 if (tree->right_node == NULL) tree->right_node = new_node;
 else insert_node(tree->right_node, new_node);
 } else {
 if (tree->left_node == NULL) tree->left_node = new_node;
 else insert_node(tree->left_node, new_node);
 }
}
 
void pre_print_node(node *tree){
 cout << " " << tree->value;
 if (tree->left_node != NULL) pre_print_node(tree->left_node);
 if (tree->right_node != NULL) pre_print_node(tree->right_node);
}
 
void in_print_node(node *tree){
 if (tree->left_node != NULL) in_print_node(tree->left_node);
 cout << " " << tree->value;
 if (tree->right_node != NULL) in_print_node(tree->right_node);
}
 
void post_print_node(node *tree){
 if (tree->left_node != NULL) post_print_node(tree->left_node);
 if (tree->right_node != NULL) post_print_node(tree->right_node);
 cout << " " << tree->value;
}
 
int main(){
 int c, n, i, value, nn = 0;
 
 cin >> n;
 
 while (++nn <= n){
 cin >> c;
 cin >> value;
 
 node *tree = (node *)malloc(sizeof(node));;
 tree->value = value;
 tree->left_node = NULL;
 tree->right_node = NULL;
 
 for (i = 0; i < c - 1; i++){
 cin >> value;
 
 node *new_node = (node *)malloc(sizeof(node));
 new_node->value = value;
 new_node->left_node = NULL;
 new_node->right_node = NULL;
 
 insert_node(tree, new_node);
 }
 
 cout << "Case " << nn << ":" << endl;
 cout << "Pre.:";
 pre_print_node(tree);
 cout << endl << "In..:";
 in_print_node(tree);
 cout << endl << "Post:";
 post_print_node(tree);
 cout << endl << endl;
 }
 
 return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s