Java Reference
In-Depth Information
depth of a node
The length of the path from the root to a node in a tree. (652)
first child /next sibling method
A general tree implementation in which each
node keeps two links per item: one to the leftmost child (if it is not a leaf )
and one to its right sibling (if it is not the rightmost sibling). (653)
height of a node
The length of the path from a node to the deepest leaf in a
tree. (652)
inorder traversal
The current node is processed between recursive calls. (667)
leaf
A tree node that has no children. (652)
level-order traversal
Nodes are visited top to bottom, left to right. Level-order
traversal is implemented by using a queue. The traversal is breadth first.
(678)
parent
and
child
Parents and children are naturally defined. A directed edge
connects the parent to the child. (652)
postorder tree traversal
Work at a node is performed after its children are
evaluated. The traversal takes constant time per node. (656)
preorder tree traversal
Work at a node is performed before its children are
processed. The traversal takes constant time per node. (656)
proper ancestor
and
proper descendant
On a path from node
u
to node
v,
if
,
then
u
is a proper ancestor of
v
and
v
is a proper descendant of
u
. (653)
siblings
Nodes with the same parents. (653)
size of a node
The number of descendants a node has (including the node
itself ). (653)
tree
Defined nonrecursively, a set of nodes and the directed edges that connect
them. Defined recursively, a tree is either empty or consists of a root and
zero or more subtrees. (652)
uv
≠
Allowing a node to be in two trees simultaneously is generally a bad idea
because changes to a subtree may inadvertently cause changes in multiple
subtrees.
1.
Failing to check for empty trees is a common error. If this failure is part of
a recursive algorithm, the program will likely crash.
2.
A common error when working with trees is thinking iteratively instead
of recursively. Design algorithms recursively first. Then convert them to
iterative algorithms, if appropriate.
3.
Search WWH ::
Custom Search