3 KiB
3 KiB
Trees
A general tree is a data structure where each node can have zero or more children. Each node has exactly one parent except for the root that has no parent.
std::vector<TreeNode*> stack;
Definition
A tree T is defined by a root r and a (possibly empty) list of subtrees T^1, T^2, ..., T^n where n \geq 0. Each subtree is itself a general tree according to the same definition.
Diagram
TreeNode
|------------------|
| Data |
| l1 l2 |
|------------------|
/ \
/ \
|--------------| |----------------------------|
| Data | | Data |
| l1 l2 | | l1 l2 l3 |
|--------------| |----------------------------|
/ \ / / \
/ |--------| |------| |------| |----------|
|------| | Data | | Data | | Data | | Data |
| Data | | l1 | |------| |------| | l1 l2 |
|------| |--------| |----------|
/ / \
|------| / \
| Data | |------| |------|
|------| | Data | | Data |
|------| | l1 |
|------|
/
/
|------|
| Data |
|------|
Trees are traversed starting at the root. Traversals are often recursive because of the recursive nature of trees. It is bad practice to expose a reference of any node externally. However, in this lab you have the following publicly exposed:
TreeNode* rootvoid add Child()TreeNode* getRoot()TreeNode* findNode()collection(TreeNode*) getChildren()
Python-like pseudocode for Level-Order Traversal:
LOT(root):
# q is a queue of TreeNode references
q;
while q is not empty:
node = q.dequeue()
visit node
for each child of ode:
q.enqueue(child)
LOT_ReportLevels(root):
# result is a list of lists of TreeNode references
result;
# q is a queue of TreeNode refs
q;
while q is not empty:
# level is a list of TreeNode references
level;
# levelSize is q.size(?)
# incomplete