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