[go: up one dir, main page]
Scribd
Upload
36 views2 pages

Binary Search Tree Lab Report

The document is a lab report detailing the implementation of a Binary Search Tree (BST) in C++, using a specific set of integers. It describes the structure of the BST, the functions implemented, and the challenges faced during the coding process, particularly with recursive functions. The report also notes a bug related to the size tracking of the tree and reflects on lessons learned from the implementation experience.

Uploaded by

e.song200
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
36 views2 pages

Binary Search Tree Lab Report

The document is a lab report detailing the implementation of a Binary Search Tree (BST) in C++, using a specific set of integers. It describes the structure of the BST, the functions implemented, and the challenges faced during the coding process, particularly with recursive functions. The report also notes a bug related to the size tracking of the tree and reflects on lessons learned from the implementation experience.

Uploaded by

e.song200
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Ethan Song

Gentry-Kolen

COMSC-210

12 April 2020

Binary Search Tree Lab Report

Assignment Description: For this lab, you will create an implementation of a binary search tree

(BST), using preorder traversal on the following set: { 8, 4, 2, 5, 12, 29 }.

Discussion:

• Solution Description: This program implements a BinarySearchTree (BST) class in C++,

consisting of a Node structure with pointers to other Nodes. This structure-pointer

relationship comprises of the entire tree. Functions include recursive add, remove,

contains, and preorder traversal/print functions, along with a getSize() function.

• Chart:

BST

+ Node: struct
• + data: int
• + left: Node
• + right: Node
• + Node(int)
+ root: Node
+ size: int
+ BST()
+ add(int): void
+ add(struct Node*, int): void
+ remove(int): struct Node*
+ remove(struct Node*, int): struct Node*
+ printPreOrder(struct Node*): void
+ contains(int): bool
+ contains(struct Node*, int): bool
+ getSize(): int
• Major Implementation Issues: The most difficult parts of the program to implement

included the recursive add and remove functions, since it was tricky to both handle

where the pointers are pointed while analyzing the recursive nature of each function.

• Screen Shot:

Known Bugs/Errors:

• The size of the tree is determined by a global size tracking variable which is incremented

and decremented whenever the non-recursive add and remove functions are called,

respectively. Therefore, an empty tree with size 0 can have a negative size value if the

remove functions is called.

Lessons Learned:

• What Went Well: The implementation of the tree went smoothly, and the result of this

lab came a fully functioning BST with proper add, remove, search, and print functions.

• What would you do differently next time: Next Time, I would try to plan out the

implementation structure more, for example using pen and paper, rather than jumping

to code too quickly.

You might also like