Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.9 kB
4
Indexable
Never
Name of Program: main
-----------------------------------------------------------------------------
Welcome to our C++ program of Binary Search Trees!
Our program takes in an input file (provided are int-input1.txt, float-input1.txt, and
string-input1.txt) and creates a BST. User will select an appropriate type for the values
represented in the files (int, float, or string).
User may: insert(i), delete(d), retrieve(r), length(l), in-order(n), pre-order(p),
post-order(o), getNumSingleParent(s), getNumLeafNodes(f), getSumOfSubtrees(t), and quit(q).
-----------------------------------------------------------------------------
Input Parameters:
Takes in an input file through txt file.
Tree type.
-----------------------------------------------------------------------------
Needed Files:
BinaryTree.h, BinaryTree.cpp, Main.cpp, Makefile, int-input1.txt, float-input1.txt
string-input1.txt
-----------------------------------------------------------------------------
getNumLeafNodes FUNCTION PSEUDO AND BIG O:
PSEUDO CODE:
take in node

traverse the bst, if root is null on left and right return
n + 1

else, go through the right roots, return getNumLeafNodes for left if right node is null
else, go through the left roots, return getNumLeafNodes for right if left node is null

else, continue through the BST, return recursively right and left

BIG O:
O(n) because you must traverse the BST on one side of the root

-----------------------------------------------------------------------------
getNumSingleParent FUNCTION PSEUDO AND BIG O:
PSEUDO CODE:
take in node

declare count to 0

if tree is not null, check to see if left is not null, right is null OR left is null, right is
NOT null, increase count if this condition is true

continue to traverse the list, setting count to the tree on the right and tree on th eleft

return count

BIG O:
O(n) because you must traverse the tree to check if each node is null

-----------------------------------------------------------------------------
getSumOfSubTrees FUNCTION PSEUDO AND BIG O:
PSEUDO CODE:
take in tree

declare counters for the left and right, set to 0

find left, call getSumOfSubTrees on the left side with count
find right, call getSumOfSubTrees on the right side with count

declare count and set to tree key value + right + left

return count

else return 0

BIG O:
O(n), to find the number of subtrees use recursion to count
the number of nodes in range

-----------------------------------------------------------------------------
CODERS:
Luan Ho ( lqh24430@uga.edu )
- Worked on BinaryTree.h, BinaryTree.cpp, Main.cpp, Makefile, README.txt
Tommy Nguyen ( thn94465@uga.edu )
- Worked on BinaryTree.h, BinaryTree.cpp, Main.cpp, Makefile, README.txt
-----------------------------------------------------------------------------
How to Compile:
make
-----------------------------------------------------------------------------
How to Run:
main FILEINPUTHERE.TXT