class BinaryTreeInterface
1: // Created by Frank M. Carrano and Timothy M. Henry.
2: // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
4: // Listing 15-1.
6: /** Interface for the ADT binary tree.
7: @file BinaryTreeInterface.h */
8: #ifndef BINARY_TREE_INTERFACE_
9: #define BINARY_TREE_INTERFACE_
10: #include "NotFoundException.h"
12: template<class ItemType>
13: class BinaryTreeInterface
14: {
15: public:
16: /** Tests whether this binary tree is empty.
17: @return True if the binary tree is empty, or false if not. */
18: virtual bool isEmpty() const = 0;
19:
20: /** Gets the height of this binary tree.
21: @return The height of the binary tree. */
22: virtual int getHeight() const = 0;
23:
24: /** Gets the number of nodes in this binary tree.
25: @return The number of nodes in the binary tree. */
26: virtual int getNumberOfNodes() const = 0;
27:
28: /** Gets the data that is in the root of this binary tree.
29: @pre The binary tree is not empty.
30: @post The root's data has been returned, and the binary tree is unchanged.
31: @return The data in the root of the binary tree. */
32: virtual ItemType getRootData() const = 0;
33:
34: /** Replaces the data in the root of this binary tree with the given data,
35: if the tree is not empty. However, if the tree is empty, inserts a new
36: root node containing the given data into the tree.
37: @pre None.
38: @post The data in the root of the binary tree is as given.
39: @param newData The data for the root. */
40: virtual void setRootData(const ItemType& newData) = 0;
41:
42: /** Adds the given data to this binary tree.
43: @param newData The data to add to the binary tree.
44: @post The binary tree contains the new data.
45: @return True if the addition is successful, or false if not. */
46: virtual bool add(const ItemType& newData) = 0;
47:
48: /** Removes the specified data from this binary tree.
49: @param target The data to remove from the binary tree.
50: @return True if the removal is successful, or false if not. */
51: virtual bool remove(const ItemType& target) = 0;
52:
53: /** Removes all data from this binary tree. */
54: virtual void clear() = 0;
55:
56: /** Retrieves the specified data from this binary tree.
57: @post The desired data has been returned, and the binary tree
58: is unchanged. If no such data was found, an exception is thrown.
59: @param target The data to locate.
60: @return The data in the binary tree that matches the given data.*/
61: virtual ItemType getEntry(const ItemType& target) const = 0;
62:
63: /** Tests whether the specified data occurs in this binary tree.
64: @post The binary tree is unchanged.
65: @param target The data to find.
66: @return True if data matching the target occurs in the tree, or false if not. */
67: virtual bool contains(const ItemType& target) const = 0;
68:
69: /** Traverses this binary tree in preorder (inorder, postorder) and
70: calls the function visit once for each node.
71: @param visit A client-defined function that performs an operation on
72: either each visited node or its data. */
73: virtual void preorderTraverse(void visit(ItemType&)) const = 0;
74: virtual void inorderTraverse(void visit(ItemType&)) const = 0;
75: virtual void postorderTraverse(void visit(ItemType&)) const = 0;
76:
77: /** Destroys this tree and frees its assigned memory. */
78: virtual ~BinaryTreeInterface() { }
79: }; // end BinaryTreeInterface
80: #endif