#include <tree.h>
This implementation stores nodes indexed by ID (a single integer). The root will always have ID 0, but the IDs of other nodes are not in any particular order. The tree structure is obtained by asking any particular node what the IDs of its parent or children are.
Access to the tree is simple: give the Tree a node ID and it will return a pointer to the node with that ID.
** If you have build problems: remember that since Tree is a class template, when using your own TreeNodes in a Tree, you'll run into linker errors if you don't do an explicit instantiation of Tree<YourTreeNode>. To deal with this, you will need to do two things:
If you are still having problems:
TreeNode constructors: the default one, which takes no arguments, and the one which takes an int (ID). MyNode::MyNode(const MyNode& other) : TreeNode(other) {
// your copy code
} WriteData is a const function.
Public Member Functions | |
| Tree () | |
| ~Tree () | |
| Tree (const Tree< T > &other) | |
| Copy constructor. It will do a deep copy of all of the TreeNodes. | |
| void | clear () |
| Return the tree to a state as if it were just constructed by Tree(). | |
| T * | root () |
| Get a pointer to the root node. | |
| const T * | root () const |
| int | size () const |
| Get the total number of nodes in the tree. | |
| T * | node (int id) |
| Get a node specified by the given index. | |
| const T * | node (int id) const |
| T * | add_node (const T &new_node) |
| Insert a copy of the given node into the tree. | |
| T * | add_node () |
| Insert a blank node into the tree. | |
| void | ReadFromStream (istream &input_stream) |
| Reads a tree from the stream. | |
| void | WriteToStream (ostream &output_stream) const |
| Write the tree to a stream. | |
| void | DeleteNode (int node_id) |
| Frees a node, and all of its children, from the tree. | |
| PreorderIterator | BeginPreorder () const |
| Start of a preorder depth-first traversal. | |
| const PreorderIterator & | EndPreorder () const |
| End of a preorder depth-first traversal. | |
| PostorderIterator | BeginPostorder () const |
| Start of a postorder depth-first traversal. | |
| const PostorderIterator & | EndPostorder () const |
| End of a postorder depth-first traversal. | |
| BreadthFirstIterator | BeginBreadthFirst () const |
| Start of a breadth-first traversal. | |
| const BreadthFirstIterator & | EndBreadthFirst () const |
| End of a breadth-first traversal. | |
Classes | |
| class | BreadthFirstIterator |
| Breadth-first iterator for Trees. More... | |
| class | Iterator |
| An iterator for Trees. More... | |
| class | PostorderIterator |
| class | PreorderIterator |
| Preorder depth-first iterator for Trees. More... | |
| Tree | ( | ) |
| ~Tree | ( | ) |
| void clear | ( | ) |
Return the tree to a state as if it were just constructed by Tree().
| T* root | ( | ) | [inline] |
Get a pointer to the root node.
| const T* root | ( | ) | const [inline] |
| int size | ( | ) | const [inline] |
Get the total number of nodes in the tree.
| T * node | ( | int | id | ) |
Get a node specified by the given index.
Returns NULL if the node is not found.
| const T * node | ( | int | id | ) | const |
| T * add_node | ( | const T & | new_node | ) |
Insert a copy of the given node into the tree.
Returns a pointer to the newly-added node in the tree.
If the new node's ID is uninitialized or invalid, it will be assigned a new unique ID. The returned pointer is a pointer to the newly-added node, so the user should call set_parent() and so forth in order to link the new node to the tree.
If the new node's ID is valid, but the tree does not contain a node with that ID, a new node will be created. The user still needs to link it to the tree manually via set_parent() and set_child().
If there already is a node in the tree with the same ID as new_node.id() (call it N), this will call N.Combine(new_node). In this case, the already-existing tree structure will be used (no need to call set_parent() and so forth, since the node is already there).
If you are having problems with this, i.e., you are calling add_node() but the data seems to not be copied into the tree, make sure that you have provided a copy constructor for your TreeNode.
| T * add_node | ( | ) |
Insert a blank node into the tree.
Returns a pointer to the newly added node. The resulting node will have no parent/child pointers, so it is not actually linked to the tree. It is up to the caller to link it to the tree by calling TreeNode::add_child() and TreeNode::set_parent().
| void ReadFromStream | ( | istream & | input_stream | ) |
Reads a tree from the stream.
File format:
Aborts if the stream is bad. Recall that the root of the tree always has ID 0.
| void WriteToStream | ( | ostream & | output_stream | ) | const |
Write the tree to a stream.
Aborts if the stream is bad. See ReadFromStream for the format.
| void DeleteNode | ( | int | node_id | ) |
Frees a node, and all of its children, from the tree.
| Tree< T >::PreorderIterator BeginPreorder | ( | ) | const |
Start of a preorder depth-first traversal.
| const Tree< T >::PreorderIterator & EndPreorder | ( | ) | const |
End of a preorder depth-first traversal.
| Tree< T >::PostorderIterator BeginPostorder | ( | ) | const |
Start of a postorder depth-first traversal.
| const Tree< T >::PostorderIterator & EndPostorder | ( | ) | const |
End of a postorder depth-first traversal.
| Tree< T >::BreadthFirstIterator BeginBreadthFirst | ( | ) | const |
Start of a breadth-first traversal.
| const Tree< T >::BreadthFirstIterator & EndBreadthFirst | ( | ) | const |
End of a breadth-first traversal.
1.5.1