Data Structures: Standard Trees

What is a standard tree?

A standard tree is a Tree implementation without any restrictions, except those all trees by definition must obey to. In common practice, they are just used to store hierarchical un-ordered data.

What are the operations it requires?

Apart of implementing operations required by Tree abstract data type, following operations are added by standard tree:

Operation	Arguments	Returns	Description
getHeight		ULONG	Gets number of edges from root node to most distant descendant
createRootNode	DATA	NODE	Sets tree root node.
createNode	DATA, PARENT_NODE	NODE	Creates node, child of another, and adds it to tree.
removeNode	NODE		Removes node from tree and moves its children to parent node.
removeBranch	NODE		Removes node from tree along with its children.

And a NODE whose operations are:

Operation	Arguments	Returns	Description
setData	DATA	void	Sets value inside node
getData		DATA	Gets value from node.
setParent	NODE	void	Sets node's parent.
getParent		NODE	Gets node's parent.
getChildren		EDGES	Gets node's children.
addChild	NODE	void	Adds child node.
hasChild	NODE	boolean	Checks if node has child node.
removeChild	NODE	void	Removes child node.
removeChildren		void	Removes all child nodes.
isDescendantOf	NODE	void	Checks if node is descendant of another.
isAncestorOf	NODE	void	Checks if node is ancestor of another.
getRoot		NODE	Navigates through node's ancestors until root node is found and returns latter.
getAncestors		LIST[NODE]	Navigates recursively through node's parents in order to get all ancestors.
getDescendants		LIST[NODE]	Navigates recursively through node's children in order to get all descendants.
getSize		ULONG	Gets number of node descendants.
getHeight		ULONG	Gets number of edges from the current node to most distant ancestor.
getDepth		ULONG	Gets number of edges from the current node to most distant descendant

Regarding implementation chosen for "LIST[NODE]" above, following data structures should be used:

Dynamic Array implementing List: fastest to generate and iterate

Regarding implementation chosen to store NODE's children, which reflects into "EDGES" above, following data structures can be used:

Dynamic Array implementing List of NODE: very fast to iterate, very slow to search a value/node into. To be used if value inside node is not unique!
Hash Table implementing Set of NODE: quite fast to iterate, very fast to search a value/node into. To be used if value inside node is unique!

If Hash Table implementing Set solution is chosen, two more operations can be generalized for standard tree, both executed in constant O(1) time:

Operation	Arguments	Returns	Description
contains	DATA	boolean	Checks if tree contains a node whose value equals that of input.
search	DATA	VERTEX	Searches tree for a node whose value equals that of input.

What are the methods to traverse a standard tree?

Depending on when a NODE is visited during traversal, following methods are in most common usage:

pre order: visitation is performed BEFORE node children are recursed. Algorithm:
function preOrder(NODE, VISITOR) VISITOR(NODE) for each CHILD @ NODE preOrder(CHILD, VISITOR)
post order: visitation is performed AFTER node children are recursed. Algorithm:
function postOrder(NODE, VISITOR) for each CHILD @ NODE postOrder(CHILD, VISITOR) VISITOR(NODE)
level order: visitation is performed by depth levels compared to source node. Algorithm:
function levelOrder(NODE, VISITOR) define QUEUE push NODE to QUEUE while QUEUE is not empty pop HEAD_NODE from QUEUE VISITOR(HEAD_NODE); for each CHILD @ HEAD_NODE push CHILD to QUEUE