Java Reference
In-Depth Information
C
HAPTER
S
UMMARY
•
A tree is a set of nodes connected by edges that indicate the relationships among the nodes. The nodes are
arranged in levels that denote their hierarchy. At the top level is a single node called the root.
•
At each successive level of a tree are nodes that are the children of the nodes at the previous level. A node
with no children is called a leaf. A node that has children is the parent of those children. The root is the only
node with no parent. All other nodes have one parent each.
•
A node in a binary tree has at most two children. In an
n
-ary tree, a node can have up to
n
children. In a gen-
eral tree, a node can have any number of children.
•
The height of a tree is the number of levels in the tree. The height also equals the number of nodes along the
longest path between the root and a leaf.
•
All leaves in a full binary tree are on the same level, and every nonleaf has exactly two children.
•
A full tree of height
h
has 2
h
-
1 nodes, which is as many as it can contain.
•
A complete binary tree is full to its next-to-last level. Its leaves on the last level are filled from left to right.
•
The height of a binary tree with
n
nodes that is either complete or full is log
2
(
n
+ 1) rounded up.
•
You can traverse the nodes in a tree by visiting each node exactly once. Several traversal orders are possible.
A level-order traversal begins at the root and visits nodes from left to right, one level at a time. In a preorder
traversal, you visit the root before you visit nodes in the root's subtrees. In a postorder traversal, you visit the
root after you visit the root's subtrees. For a binary tree, an inorder traversal visits the nodes in the left sub-
tree, then the root, and finally the nodes in the right subtree. For a general tree, an inorder traversal is not
well defined.
•
An expression tree is a binary tree that represents an algebraic expression whose operators are binary. The
operands of the expression appear in the tree's leaves. Any parentheses in an expression do not appear in the
tree. You can use an expression tree to evaluate an algebraic expression.
•
A decision tree contains a question in each nonleaf. Each child of the nonleaf corresponds to one possible
response to the question. Within each of these children is either an additional question or a conclusion.
Nodes that are conclusions have no children, and so they are leaves. You can use a decision tree to create an
expert system.
•
A binary search tree is a binary tree whose nodes contain
Comparable
objects that are organized as follows:
•
The data in a node is greater than the data in the node's left subtree.
•
The data in a node is less than the data in the node's right subtree.
•
A search of a binary search tree can be as fast as O(log
n
) or as slow as O(
n
). The performance of the search
depends on the shape of the tree.
•
A heap is a complete binary tree whose nodes contain
Comparable
objects. The data in each node is no
smaller (or no larger) than the data in the node's descendants.
•
You can use a heap to implement a priority queue.
•
Certain rules form a grammar that describes an algebraic expression. A parse tree is a general tree that pictures
how these rules apply to a specific expression. You can use a parse tree to check the syntax of a given expression.
•
A game tree is a general decision tree that contains the possible moves for a game such as tic-tac-toe.
