A tree structure
Example:
var root = new polygonal.ds.TreeNode<Int>(0); //create the root of the tree
var builder = new polygonal.ds.TreeBuilder<Int>(root);
builder.appendChild(1);
builder.down();
builder.appendChild(2);
builder.up();
builder.appendChild(3);
trace(root); //outputs:
[ Tree size=4 depth=0 height=3
0
+--- 1
| +--- 2
+--- 3
]
Constructor
Variables
children:TreeNode<T>
The node's children or null if this node has no children.
This is a doubly linked list of TreeNode objects and children points to the first child.
read onlykey:Int = HashKey.next()
A unique identifier for this object.
A hash table transforms this key into an index of an array element by using a hash function.
Methods
appendNode (node:TreeNode<T>):TreeNode<T>
Unlinks node and appends node as a child to this node.
Returns:
this node.
childIterator ():Itr<T>
Returns a new ChildTreeIterator object to iterate over all direct children (excluding this node).
In contrast to this.iterator(), this method is not recursive.
See:
clear (gc:Bool = false):Void
Removes all child nodes.
Parameters:
gc | if true, recursively nullifies this subtree so the garbage collector can reclaim used memory. |
|---|
clone (byRef:Bool = true, ?copier:T ‑> T):Collection<T>
Creates and returns a shallow copy (structure only - default) or deep copy (structure & elements) of this node and its subtree.
If byRef is true, primitive elements are copied by value whereas objects are copied by reference.
If byRef is false, the copier function is used for copying elements. If omitted, clone() is called on each element assuming all elements implement Cloneable.
depth ():Int
Calculates the depth of this node within this tree.
The depth is defined as the length of the path from the root node to this node.
The root node is at depth 0.
find (val:T):TreeNode<T>
Recursively finds the first occurrence of the node storing val in this tree.
Returns:
the node storing val or null if such a node does not exist.
free ():Void
Destroys this object by explicitly nullifying all nodes, pointers and elements for GC'ing used resources.
Improves GC efficiency/performance (optional).
inlinegetChildAt (i:Int):TreeNode<T>
Returns the child at index i or null if the node has no children.
inlinegetSiblingIndex ():Int
Returns the sibling index of this node.
The first sibling equals index 0, the last sibling equals index this.numChildren() - 1.
height ():Int
Calculates the height of this tree, assuming this is the root node of this tree.
The height is defined as the length of the path from the root node to the deepest node in the tree.
A tree with one node has a height of one.
insertAfterChild (child:TreeNode<T>, node:TreeNode<T>):TreeNode<T>
Unlinks node and appends node to the specified child node.
Returns:
this node.
insertBeforeChild (child:TreeNode<T>, node:TreeNode<T>):TreeNode<T>
Unlinks node and prepends node to the specified child node.
Returns:
this node.
insertChildAt (node:TreeNode<T>, i:Int):TreeNode<T>
Unlinks node and inserts node at the index position i.
Returns:
this node.
inlineiter (f:T ‑> Void, ?tmpStack:Array<TreeNode<T>>):TreeNode<T>
Calls 'f` on all elements in preorder.
iterator ():Itr<T>
Returns a new TreeIterator object to iterate over all elements contained in the nodes of this subtree (including this node).
The elements are visited by using a preorder traversal.
See:
levelorder (process:TreeNode<T> ‑> Dynamic ‑> Bool, userData:Dynamic):TreeNode<T>
Performs a queue-based, iterative level-order traversal. In a level-order traversal all nodes of a tree are processed by depth: first the root, then the children of the root, etc.
Parameters:
process | a function that is invoked on every traversed node.
The first argument holds a reference to the current node, while the second argument stores custom data specified by the |
|---|---|
userData | custom data that is passed to every visited node via |
Returns:
this node.
postorder (process:TreeNode<T> ‑> Dynamic ‑> Bool, userData:Dynamic, iterative:Bool = false):TreeNode<T>
Performs a recursive postorder traversal. A postorder traversal performs the following steps:
- Traverse the left subtree of the node
- Traverse the right subtree of the node
- Visit the node
Parameters:
process | a function that is invoked on every traversed node.
The first argument holds a reference to the current node, while the second argument stores custom data specified by the |
|---|---|
userData | custom data that is passed to every visited node via |
iterative | if true, an iterative traversal is used (default traversal style is recursive). |
Returns:
this node.
preorder (process:TreeNode<T> ‑> Bool ‑> Dynamic ‑> Bool, userData:Dynamic, preflight:Bool = false, iterative:Bool = false):TreeNode<T>
Performs a recursive preorder traversal.
A preorder traversal performs the following steps:
- Visit the node
- Traverse the left subtree of the node
- Traverse the right subtree of the node
Parameters:
process | a function that is invoked on every traversed node.
The first argument holds a reference to the current node, the second arguments stores the preflight flag and the third argument stores custom data specified by the |
|---|---|
userData | custom data that is passed to every visited node via |
preflight | if true, an extra traversal is performed before the actual traversal runs.
The first pass visits all elements and calls |
iterative | if true, an iterative traversal is used (default traversal style is recursive). |
Returns:
this node.
prependNode (node:TreeNode<T>):TreeNode<T>
Unlinks node and prepends node as a child of this node.
Returns:
this node.
remove (val:T):Bool
Runs a recursive preorder traversal that removes all nodes storing val.
Tree nodes are not rearranged, so if a node stores val, the complete subtree rooted at that node is unlinked.
Returns:
true if at least one occurrence of val was removed.
removeChildAt (i:Int):TreeNode<T>
Removes the child at index i and returns the child.
Returns:
this node.
removeChildren (i:Int = 0, n:Int = -1):TreeNode<T>
Removes n children starting at the specified index i in the range [i, i + n].
If n is -1, n is set to this.numChildren() - i.
Returns:
this node.
serialize (?node:TreeNode<T>, ?list:Array<{v:T, c:Bool}>):Array<{v:T, c:Bool}>
Serializes this tree.
The tree can be rebuild by calling this.unserialize().
Parameters:
node | the root of the tree. |
|---|
Returns:
a flattened tree.
See:
setChildIndex (node:TreeNode<T>, i:Int):TreeNode<T>
Changes the index of the child node to i.
Returns:
this node.
setFirst ():TreeNode<T>
Successively swaps this node with previous siblings until it reached the head of the sibling list.
Returns:
this node.
setLast ():TreeNode<T>
Successively swaps this node with next siblings until it reached the tail of the sibling list.
Returns:
this node.
sort (?cmp:T ‑> T ‑> Int, useInsertionSort:Bool = false):TreeNode<T>
Sorts the children of this node using the merge sort algorithm.
Parameters:
cmp | a comparison function.
If null, the elements are compared using |
|---|---|
useInsertionSort | if true, the dense array is sorted using the insertion sort algorithm. This is faster for nearly sorted lists. |
Returns:
this node.
swapChildren (a:TreeNode<T>, b:TreeNode<T>):TreeNode<T>
Swaps the child a with child b by swapping their values.
Returns:
this node.
swapChildrenAt (i:Int, j:Int):TreeNode<T>
Swaps the child at index i with the child at index j by swapping their values.
Returns:
this node.
toArray ():Array<T>
Returns an array containing all elements in the tree rooted at this node.
The elements are collected using a preorder traversal.
unserialize (list:Array<{v:T, c:Bool}>):TreeNode<T>
Unserializes a given list into a TreeNode structure.
First create a dummy node which will be the root of the unserialized tree, then call this.unserialize().
Example:
var root = new polygonal.ds.TreeNode<String>(null);
root.unserialize(mySerializedTree);
Parameters:
list | the flattened tree |
|---|
Returns:
the root of the tree.