class BinaryTreeNode<T>

package polygonal.ds

implements Collection<T>

@:directlyUsed

A binary tree

A tree data structure in which each node has at most two child nodes.

Example:

var o = new polygonal.ds.BinaryTreeNode<Int>(0);
o.setLeft(1);
o.setRight(2);
o.left.setLeft(3);
o.left.left.setRight(4);
trace(o); //outputs:

[ BinaryTree val=0 size=5 depth=0 height=4
  0
  L---1
  |   L---3
  |   |   R---4
  R---2
]

Constructor

new (val:T)

Creates a new BinaryTreeNode object storing val.

Variables

@:value(HashKey.next())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.

left:BinaryTreeNode<T>

The left child node or null if this node has no left child.

parent:BinaryTreeNode<T>

The parent node or null if this node has no parent.

right:BinaryTreeNode<T>

The right child node or null if this node has no right child.

read onlysize:Int

Recursively counts the number of nodes in this subtree (including this node).

val:T

The node's data.

Methods

@:value({ gc : false })clear (gc:Bool = false):Void

Removes all child nodes.

Parameters:

gc

if true, all nodes and elements of this subtree are recursively nullified so the garbage collector can reclaim used memory.

@:value({ copier : null, byRef : true })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.

contains (val:T):Bool

Returns true if the subtree rooted at this node contains val.

inlinedepth ():Int

Calculates the depth of this node.

The depth is defined as the length of the path from the root node to this node.

The root node is at depth 0.

free ():Void

Destroys this object by explicitly nullifying all nodes, pointers and elements for GC'ing used resources.

Improves GC efficiency/performance (optional).

height ():Int

Computes the height of this subtree.

The height is defined as the path from the root node to the deepest node in a tree.

A tree with only a root node has a height of one.

@:value({ userData : null, iterative : false, process : null })inorder (?process:BinaryTreeNode<T> ‑> Dynamic ‑> Bool, iterative:Bool = false, ?userData:Dynamic):Void

Performs a recursive inorder traversal.

An inorder traversal performs the following steps:

  1. Traverse the left subtree of the node
  2. Visit the node
  3. Traverse the right subtree of the node

Parameters:

process

a function that is invoked on every traversed node. If omitted, element.visit() is used instead.
In this case all elements have to implement Visitable.
The first argument holds a reference to the current node, while the second argument stores custom data specified by the userData parameter (default is null). Once process returns false, the traversal stops immediately and no further nodes are examined.

iterative

if true, an iterative traversal is used (default traversal style is recursive).

userData

custom data that is passed to every visited node via process or element.visit(). If omitted, null is used.

inlineisEmpty ():Bool

Unsupported operation; always returns false.

inlineiter (f:T ‑> Void, ?tmpStack:Array<BinaryTreeNode<T>>):BinaryTreeNode<T>

Calls 'f` on all elements in preorder.

iterator ():Itr<T>

Returns a new BinaryTreeNodeIterator 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:

http://haxe.org/ref/iterators

@:value({ userData : null, iterative : false, process : null })postorder (?process:BinaryTreeNode<T> ‑> Dynamic ‑> Bool, iterative:Bool = false, ?userData:Dynamic):Void

Performs a recursive postorder traversal.

A postorder traversal performs the following steps:

  1. Traverse the left subtree of the node
  2. Traverse the right subtree of the node
  3. Visit the node

Parameters:

process

a function that is invoked on every traversed node. If omitted, element.visit() is used instead.
In this case all elements have to implement Visitable.
The first argument holds a reference to the current node, while the second argument stores custom data specified by the userData parameter (default is null). Once process returns false, the traversal stops immediately and no further nodes are examined.

iterative

if true, an iterative traversal is used (default traversal style is recursive).

userData

custom data that is passed to every visited node via process or element.visit(). If omitted, null is used.

@:value({ userData : null, iterative : false, process : null })preorder (?process:BinaryTreeNode<T> ‑> Dynamic ‑> Bool, iterative:Bool = false, ?userData:Dynamic):Void

Performs a recursive preorder traversal.

A preorder traversal performs the following steps:

  1. Visit the node
  2. Traverse the left subtree of the node
  3. Traverse the right subtree of the node

Parameters:

process

a function that is invoked on every traversed node. If omitted, element.visit() is used instead.
In this case all elements have to implement Visitable.
The first argument holds a reference to the current node, while the second argument stores custom data specified by the userData parameter (default is null). Once process returns false, the traversal stops immediately and no further nodes are examined.

iterative

if true, an iterative traversal is used (default traversal style is recursive).

userData

custom data that is passed to every visited node via process or element.visit(). If omitted, null is used.

remove (val:T):Bool

Runs a recursive preorder traversal that removes all occurrences of val.

Tree nodes are not rearranged, so if a node storing val is removed, the subtree rooted at that node is unlinked and lost.

Returns:

true if at least one occurrence of val was removed.

inlinesetLeft (val:T):BinaryTreeNode<T>

Adds a left child node storing val.

If a left child exists, only the element is updated to val.

inlinesetRight (val:T):BinaryTreeNode<T>

Adds a right child node storing val.

If a right child exists, only the element is updated to val.

toArray ():Array<T>

Returns an array containing all elements in this subtree.

The elements are added by applying a preorder traversal.

toString ():String

Prints out all elements.

inlineunlink ():BinaryTreeNode<T>

Disconnects this node from this subtree.