| |
| /**** |
| Copyright (C) 1996 McGill University. |
| Copyright (C) 1996 McCAT System Group. |
| Copyright (C) 1996 ACAPS Benchmark Administrator |
| benadmin@acaps.cs.mcgill.ca |
| |
| This program is free software; you can redistribute it and/or modify |
| it provided this copyright notice is maintained. |
| |
| This program is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. |
| ****/ |
| |
| /***************************************************************************/ |
| /* */ |
| /* Filename : bintree.c */ |
| /* */ |
| /* Author : Frederic Bergeron (91 485 12) */ |
| /* */ |
| /* Date : 1996/09/26 */ |
| /* */ |
| /***************************************************************************/ |
| |
| |
| #include "bintree.h" |
| |
| |
| /***************************************************************************/ |
| struct binaryTree* createBinaryTree( int newValue ) |
| /***************************************************************************/ |
| { |
| struct binaryTree* newTree = NULL; |
| |
| newTree = (struct binaryTree*) malloc( sizeof( struct binaryTree ) ); |
| newTree->value = newValue; |
| newTree->left = newTree->right = NULL; |
| |
| return newTree; |
| } |
| /***************************************************************************/ |
| |
| |
| /***************************************************************************/ |
| void printBinaryTree( struct binaryTree* tree ) |
| /***************************************************************************/ |
| { |
| if ( tree == NULL ) |
| printf( "X" ); |
| else { |
| printf( "(%d <L ", tree->value ); |
| printBinaryTree( tree->left ); |
| printf( " L> <R " ); |
| printBinaryTree( tree->right ); |
| printf( " R>)\n" ); |
| } |
| } |
| /***************************************************************************/ |
| |
| |
| /***************************************************************************/ |
| void printSortedBinaryTree( struct binaryTree* tree ) |
| /***************************************************************************/ |
| { |
| if ( tree ) { |
| printSortedBinaryTree( tree->left ); |
| printf( "%d ", tree->value ); |
| printSortedBinaryTree( tree->right ); |
| } |
| } |
| /***************************************************************************/ |
| |
| |
| /***************************************************************************/ |
| struct binaryTree* insertSortedBinaryTree( int newValue, |
| struct binaryTree** sortedTree ) |
| /***************************************************************************/ |
| { |
| struct binaryTree* newTree = createBinaryTree( newValue ); |
| struct binaryTree* temp = NULL; |
| int done = FALSE; |
| |
| if ( *sortedTree == NULL ) |
| *sortedTree = newTree; |
| else { |
| temp = *sortedTree; |
| |
| do { |
| if ( newValue < temp->value ) |
| if ( temp->left == NULL ) { |
| temp->left = newTree; |
| done = TRUE; |
| } |
| else |
| temp = temp->left; |
| else if ( newValue > temp->value ) |
| if ( temp->right == NULL ) { |
| temp->right = newTree; |
| done = TRUE; |
| } |
| else |
| temp = temp->right; |
| else |
| done = TRUE; |
| } while ( !done ); |
| } |
| |
| return newTree; |
| } |
| /***************************************************************************/ |
| |
| |
| /***************************************************************************/ |
| double getArithmeticMeanBinaryTree( struct binaryTree* tree ) |
| /**************************************************************************************************************/ |
| { |
| return (double) getSumBinaryTree( tree ) / |
| (double) getSizeBinaryTree( tree ); |
| } |
| /**************************************************************************************************************/ |
| |
| |
| /**************************************************************************************************************/ |
| double getArithmeticMeanOptimized( struct binaryTree* tree) |
| /**************************************************************************************************************/ |
| { |
| double sum = 0.0, count = 0.0; |
| |
| getArithmeticMeanOptimizedRecurs( tree, &sum, &count ); |
| |
| return sum / count; |
| } |
| /**************************************************************************************************************/ |
| |
| |
| /**************************************************************************************************************/ |
| void getArithmeticMeanOptimizedRecurs( struct binaryTree* tree, |
| double* sum, |
| double* count ) |
| /**************************************************************************************************************/ |
| { |
| if ( tree ) { |
| *sum = *sum + tree->value; |
| *count = *count + 1; |
| getArithmeticMeanOptimizedRecurs( tree->left, sum, count ); |
| getArithmeticMeanOptimizedRecurs( tree->right, sum, count ); |
| } |
| } |
| /**************************************************************************************************************/ |
| |
| |
| /**************************************************************************************************************/ |
| int memberOfBinaryTree( struct binaryTree* tree, int searchedValue ) |
| /**************************************************************************************************************/ |
| { |
| int found = FALSE; |
| |
| memberOfBinaryTreeRecurs( tree, searchedValue, &found ); |
| |
| return found; |
| } |
| /**************************************************************************************************************/ |
| |
| |
| /*************************************************************************************************************/ |
| void memberOfBinaryTreeRecurs( struct binaryTree* tree, |
| int searchedValue, |
| int* found ) |
| /*************************************************************************************************************/ |
| { |
| if (tree) { |
| |
| if (tree->value == searchedValue) |
| *found = TRUE; |
| else { |
| memberOfBinaryTreeRecurs( tree->left, searchedValue, found ); |
| if ( ! (*found) ) |
| memberOfBinaryTreeRecurs( tree->right, searchedValue, found ); |
| |
| } |
| } |
| } |
| /*************************************************************************************************************/ |
| |
| |
| /**************************************************************************************************************/ |
| int memberOfSortedBinaryTree( struct binaryTree* tree, int searchedValue ) |
| /**************************************************************************************************************/ |
| { |
| struct binaryTree* seeker = tree; |
| int found = FALSE; |
| |
| while ((!found) && (seeker)) { |
| if (searchedValue < seeker->value) |
| seeker = seeker->left; |
| else if (searchedValue > seeker->value) |
| seeker = seeker->right; |
| else |
| found = TRUE; |
| } |
| |
| return found; |
| } |
| /**************************************************************************************************************/ |
| |
| |
| /**************************************************************************************************************/ |
| int getSizeBinaryTree( struct binaryTree* tree ) |
| /**************************************************************************************************************/ |
| { |
| if ( tree ) |
| return 1 + |
| getSizeBinaryTree( tree->left ) + |
| getSizeBinaryTree( tree->right ); |
| else |
| return 0; |
| } |
| /**************************************************************************************************************/ |
| |
| |
| /**************************************************************************************************************/ |
| double getSumBinaryTree( struct binaryTree* tree ) |
| /**************************************************************************************************************/ |
| { |
| if ( tree ) |
| return (double) tree->value + |
| getSumBinaryTree( tree->left ) + |
| getSumBinaryTree( tree->right ); |
| else |
| return (double) 0; |
| } |
| /**************************************************************************************************************/ |
| |
| |
