Unit 6 Study Guide and Review: Useful Examples and C++ Glossary
6a. Describe and code the binary tree structure
- How do you define a binary tree?
- How do you search a binary tree?
A binary tree structure is essentially a series of nodes that each have two branches. The parent node (root of the tree) has two children and each of those children have up to two children. There are a number of characteristics of a binary tree, which include root of the tree, as well as depth, size and base type of the tree. The bottom of the tree is empty. When you define a tree, you can define it in sets of three nodes(the parent and two children) or as a vector of nodes. For more information on binary trees, refer to this page.
6b. Code special data structures
- What are the different data structures available and what are the benefits and drawbacks of each?
There are many different types of data structures. Each of these structures essentially has the same purpose: to store data. Which data structure you use will be based on which data structure behaves as you need it to behave. Do you need the size of the structure to change? Do you need to be able to add to the end of the structure? Maybe you need to add to the beginning of the structure. These behaviors will dictate which data structure you use. For more information about data structures, refer to this page.
6c. Describe and code the container class objects
- How do you declare an instance of each of the different container types?
- What are the methods for each container type?
Whether it is a vector or an array, or any of the other data structures, you need to know how to declare them. Do you need to set the size, as in an array, does it require a deque container, as in a stack, or do you allocate memory? For more information about data structures, refer to this page.
6d. Describe and code the vector container
- How do you declare a vector?
- How do you add and remove items from a vector?
- How do you search a vector?
The vector class is a container, but it is usually explored separately, because it is such a useful structure. The greatest benefit of a vector over an array is the ability to resize the array, improving efficiency and improved memory management. For more information about vectors review this page and this page.
Unit 6 Vocabulary
This vocabulary list includes terms that might help you with the review items above and some terms you should be familiar with to be successful in completing the final exam for the course.
Try to think of the reason why each term is included.
- Array class
- Binary tree
- Container class
- Data structures
- Deque class
- Forward_list class
- Heterogeneous tree
- Left subtree
- List class
- Maps
- Multimap
- Multiset class
- Priority_queue class
- Queue class
- Recursion
- Right subtree
- Set class
- Stack class
- Unordered_map
- Unordered_multimap
- Unordered_multiset class
- Unordered_set class
- Vector class