We use a BinaryNode (Fig. 10–8, pp. 260–261):
How does a binary tree compare to a doubly linked list?
Version 8.01
(Recursively defined:) A binary tree is either empty or it consists of a root node, a left subtree, and a right subtree; both subtrees are binary trees.
The root of a subtree of a node.
A node having a child.
Child of the same parent.
The node which has no parent.
A node having no child.
A node that has at least one child. Could be any non-leaf node, including the root.
The number of lines (not nodes) on a path to the root. (The root’s depth is 0; its children have depth 1.)
All the nodes at a particular depth (say, 3).
The depth of the deepest node; the maximum depth of nodes in the tree.
The descandants of a node include itself, its children, and their descendants.
A descendant of a node, except the node itself.
The ancestors of a node include itself, its parent, and its parent’s ancestors.
An ancestor of a node, except the node itself.
Each internal node has one child; does it matter on which side?
Each internal node has two children; all leaves at the same depth. (Usually called “complete”)
The size of a binary tree of height h:
Conversely: if size = n, then:
Key point: For a perfect binary tree, the height is Θ(log n).
We use a BinaryNode (Fig. 10–8, pp. 260–261):
How does a binary tree compare to a doubly linked list?
Internal nodes represent questions:
Leaves represent answers:
Learning from a mistake: the program asks for a new question which can discriminate the answer it gave from the correct answer, and splits the answer node as follows:
(See diagram WHICH IS TO BE ADDED)
The first three (of four) traversals are recursive, following the structure of the tree:
Preorder (root first): root, left, right. More precisely:
if tree is empty
do nothing
else
visit root
preorder left subtree
preorder right subtreePostorder (root last): left, right, root.
The implementations (BinaryNode.java, Figures 10-15, 16, and 17, pp. 266–267) focus on building a string representation and treat the base case strangely because we cannot call a method on null.
(There is a way to avoid this: represent the empty tree as an object.)
An iterative version of preorder uses a stack (Fig. 10–18, p. 267–268). Note that even though a stack is used, it seems to be more efficient than the recursive method, because it pushes only the roots of the subtrees, not a complete call frame — but is it really more efficient? Significantly more?
Ugly, but let’s look at it, because guess what? if we replace stack with queue, we get a method for level order traversal. (Figure 10–19, p. 268) In level order, we visit the nodes in order of depth:
- All nodes on level 0 (the root)
- All nodes on level 1 left to right
- All nodes on level 2 left to right
- …
Is there another way to do this without using a queue? …
Definition: a general tree consists of a node (the root) and zero or more subtrees, where each subtree is a general tree.
(We should say also: the subtrees are disjoint. That is, no subtree contains any element which is also in another subtree.)
Thus, general tree, too, is recursively defined; but the base case is not when the tree is empty: it’s when the node has zero subtrees.
Differences from binary tree:
Root node with a list or array or set of children.
“First child, next sibling” representation2 uses less space than representation 1:
This general tree
is represented as
A
/
G → E → C
/ /
B D → Fwhich is really (or can represent — show how) a binary tree, but with the left child (/) interpreted as “first child”, and the right child (→) interpreted as “next sibling”.
Thus for every general tree, there is an “equivalent” binary tree.
But the converse is not true, that is, it is not true that for every binary tree, there is an equivalent general tree. First, there is no general tree equivalent to the empty binary tree. Second, general trees could not distinguish between a node with a single child on the left or on the right. Considered as binary trees, these are different:
Minimax algorithm used in game playing (chess, checkers, etc.), and real-life conflicts, such as war.
The “game tree” is not explicitly built up in memory as a data structure, but illustrates the strategy; if it’s in memory at all, it’s implicit in the stack of recursive procedure calls.
The computer (X) plays against the human (O).
Idea of minimax:
score is positive for X winning, zero or negative for O winning.
X tries to maximize score; O tries to minimize it.
On each move, then, X picks the best move (that leads to the highest score), fully aware of what O might do on the next move, what X might do on the move after that, and so on.
This kind of thinking leads to a “game tree” (Figures 10–29 and 10–31, pp. 276 and 278).
The game tree can be implemented by mutually recursive methods.
It is not stored in memory, except for the branches being currently explored. It would consume too much memory.
Problems:
For large game trees, exhaustive search isn’t possible (due to time limitations).
Therefore, we have to expand the game tree as far as we can in the time available, and make an estimate of the value of the resulting game state.
(Not in the textbook)
Venn diagrams are a good visual model for trees.
For example, the branchy tree diagram
represents a tree which can alternatively be represented as these nested boxes:
+------------------+
|A |
| +---+ +---+ |
| | | | | |
| | B | | C | |
| | | | | |
| +---+ +---+ |
| |
+------------------+In fact, this is a very good model for general trees, since trees can be formally defined as sets containing disjoint subsets.
Visualization of the document tree:
We call it “first child, next sibling” — but which is first? The choice is arbitrary, unless we have an ordered tree, and then the children (subtrees) are assigned a particular order.↩
