程序代做 CS61B Lecture #20: Trees

CS61B Lecture #20: Trees
Last modified: Wed Oct 16 16:03:40 2019 CS61B: Lecture #20 1

A Recursive Structure

Copyright By PowCoder代写 加微信 powcoder

• Trees naturally represent recursively defined, hierarchical objects with more than one recursive subpart for each instance.
• Common examples: expressions, sentences.
– Expressions have definitions such as “an expression consists of a
literal or two expressions separated by an operator.”
• Also describe structures in which we recursively divide a set into multiple subsets.
Last modified: Wed Oct 16 16:03:40 2019 CS61B: Lecture #20 2

Formal Definitions
• Trees come in a variety of flavors, all defined recursively:
– 61A style: A tree consists of a label value and zero or more
branches (or children), each of them a tree.
– 61A style, alternative definition: A tree is a set of nodes (or vertices), each of which has a label value and one or more child nodes, such that no node descends (directly or indirectly) from itself. A node is the parent of its children.
– Positional trees: A tree is either empty or consists of a node containing a label value and an indexed sequence of zero or more children, each a positional tree. If every node has two positions, we have a binary tree and the children are its left and right sub- trees. Again, nodes are the parents of their non-empty children.
– We’ll see other varieties when considering graphs.
Last modified: Wed Oct 16 16:03:40 2019 CS61B: Lecture #20 3

Tree Characteristics (I)
• The root of a tree is a non-empty node with no parent in that tree (its parent might be in some larger tree that contains that tree as a subtree). Thus, every node is the root of a (sub)tree.
• The order, arity, or degree of a node (tree) is its number (maximum number) of children.
• The nodes of a k-ary tree each have at most k children.
• A leaf node has no children (no non-empty children in the case of
positional trees).
Last modified: Wed Oct 16 16:03:40 2019 CS61B: Lecture #20 4

Tree Characteristics (II)
• The height of a node in a tree is the largest distance to a leaf. That is, a leaf has height 0 and a non-empty tree’s height is one more than the maximum height of its children. The height of a tree is the height of its root.
• The depth of a node in a tree is the distance to the root of that tree. That is, in a tree whose root is R, R itself has depth 0 in R, and if node S ̸= R is in the tree with root R, then its depth is one greater than its parent’s.
Last modified: Wed Oct 16 16:03:40 2019 CS61B: Lecture #20 5

A Tree Type, 61A Style
public class Tree {
// This constructor is convenient, but unfortunately requires this // SuppressWarnings annotation to prevent (harmless) warnings
// that we will explain later.
@SuppressWarnings(“unchecked”)
public Tree(Label label, Tree… children) { label = label;
kids = new ArrayList<>(Arrays.asList(children)); }
public int arity() { return kids.size(); }
public Label label() { return label; }
public Tree child(int k) { return kids.get(k); }
private Label label;
private ArrayList> kids; }
Last modified: Wed Oct 16 16:03:40 2019 CS61B: Lecture #20 6

Fundamental Operation: Traversal
• Traversing a tree means enumerating (some subset of) its nodes. • Typically done recursively, because that is natural description.
• As nodes are enumerated, we say they are visited.
• Three basic orders for enumeration (+ variations):
– Preorder: visit node, traverse its children.
– Postorder: traverse children, visit node.
– Inorder: traverse first child, visit node, traverse second child (binary trees only).
351515 024 236 036
142 inorder
Last modified: Wed Oct 16 16:03:40 2019 CS61B: Lecture #20 7

Problem: Convert
into (- (- (* x (+ y 3))) z)
Preorder Traversal and Prefix Expressions
static String toLisp(Tree T) { if (T.arity() == 0) return T.label(); else {
String R; R = “(” + T.label();
for (int i = 0; i < T.arity(); i += 1) R += " " + toLisp(T.child(i)); return R + ")"; (Assume Tree is means “Tree whose labels have type Label.”)
Last modified: Wed Oct 16 16:03:40 2019
CS61B: Lecture #20 8

Inorder Traversal and Infix Expressions Problem: Convert
into ((-(x*(y+3)))-z)
To think about: how to get rid of all those paren- theses.
static String toInfix(Tree T) { if (T.arity() == 0) {
return T.label();
} else if (T.arity() == 1) {
return “(” T.label() + toInfix(T.child(0)) + “)”; } else {
return “(” toInfix(T.child(0)) + T.label() + toInfix(T.child(1)) + “)”; }
Last modified: Wed Oct 16 16:03:40 2019 CS61B: Lecture #20 9

Postorder Traversal and Postfix Expressions Problem: Convert
static String toPolish(Tree T) { String R; R = “”;
for (int i = 0; i < T.arity(); i += 1) R += toPolish(T.child(i)) + " "; return R + String.format("%s:%d", T.label(), T.arity()); into x y 3 +:2 *:2 -:1 z -:2 Last modified: Wed Oct 16 16:03:40 2019 CS61B: Lecture #20 10 A General Traversal: The Visitor Pattern void preorderTraverse(Tree T, Consumer> visit) {
if (T != null) {
visit.accept(T);
for (int i = 0; i < T.arity(); i += 1) preorderTraverse(T.child(i), visit); • java.util.function.Consumer is a library interface that works as a function-like type with one void method, accept, which takes an argument of type AType.
• Now, using Java 8 lambda syntax, I can print all labels in the tree in preorder with:
preorderTraverse(myTree, T -> System.out.print(T.label() + ” “));
Last modified: Wed Oct 16 16:03:40 2019 CS61B: Lecture #20 11

Iterative Depth-First Traversals
• Tree recursion conceals data: a stack of nodes (all the T arguments) and a little extra information. Can make the data explicit:
void preorderTraverse2(Tree T, Consumer> visit) { Stack> work = new Stack<>();
work.push(T);
while (!work.isEmpty()) {
Tree node = work.pop();
visit.accept(node);
for (int i = node.arity()-1; i >= 0; i -= 1)
work.push(node.child(i)); // Why backward? }
• This traversal takes the same Θ(·) time as doing it recursively, and
also the same Θ(·) space.
• That is, we have substituted an explicit stack data structure (work)
for Java’s built-in execution stack (which handles function calls).
Last modified: Wed Oct 16 16:03:40 2019 CS61B: Lecture #20 12

Traverse all nodes at depth 0, then depth 1, etc:
Level-Order (Breadth-First) Traversal
Last modified: Wed Oct 16 16:03:40 2019
CS61B: Lecture #20 13

Breadth-First Traversal Implemented
A simple modification to iterative depth-first traversal gives breadth- first traversal. Just change the (LIFO) stack to a (FIFO) queue:
void breadthFirstTraverse(Tree T, Consumer> visit) { ArrayDeque> work = new ArrayDeque<>(); // (Changed) work.push(T);
while (!work.isEmpty()) {
Tree node = work.remove(); // (Changed) if (node != null) {
visit.accept(node);
for (int i = 0; i < node.arity(); i += 1) // (Changed) work.push(node.child(i)); Last modified: Wed Oct 16 16:03:40 2019 CS61B: Lecture #20 14 • The traversal algorithms have roughly the form of the boom example in §1.3.3 of Data Structures—an exponential algorithm. • However, the role of M in that algorithm is played by the height of the tree, not the number of nodes. • In fact, easy to see that tree traversal is linear: Θ(N), where N is the # of nodes: Form of the algorithm implies that there is one visit at the root, and then one visit for every edge in the tree. Since every node but the root has exactly one parent, and the root has none, must be N − 1 edges in any non-empty tree. • In positional tree, is also one recursive call for each empty tree, but # of empty trees can be no greater than kN, where k is arity. • For k-ary tree (max # children is k), h + 1 ≤ N ≤ kh+1−1, where h is • So h ∈ Ω(logk N) = Ω(lgN) and h ∈ O(N). • Many tree algorithms look at one child only. For them, worst-case time is proportional to the height of the tree—Θ(lgN)—assuming that tree is bushy—each level has about as many nodes as possible. Last modified: Wed Oct 16 16:03:40 2019 CS61B: Lecture #20 15 Recursive Breadth-First Traversal: Iterative Deepening • Previous breadth-first traversal used space proportional to the width of the tree, which is Θ(N) for bushy trees, whereas depth-first traversal takes lg N space on bushy trees. • Can we get breadth-first traversal in lg N space and Θ(N ) time on bushy trees? • For each level, k, of the tree from 0 to lev, call doLevel(T,k): void doLevel(Tree T, int lev) { if (lev == 0) for each non-null child, C, of T { doLevel(C, lev-1); • So we do breadth-first traversal by repeated (truncated) depth- first traversals: iterative deepening. • In doLevel(T, k), we skip (i.e., traverse but don’t visit) the nodes before level k, and then visit at level k, but not their children. Last modified: Wed Oct 16 16:03:40 2019 CS61B: Lecture #20 16 Iterative Deepening Time? 7 8 9 1011 12 13 14 3 •Lethbeheight,N be#ofnodes. • Count # edges traversed (i.e, # of calls, not counting null nodes). • First (full) tree: 1 for level 0, 3 for level 1, 7 for level 2, 15 for level 3. • Or in general (21 − 1) + (22 − 1) + . . . + (2h+1 − 1) = 2h+2 − h ∈ Θ(N ), since N = 2h+1 − 1 for this tree. • Second (right leaning) tree: 1 for level 0, 2 for level 2, 3 for level 3. • Or in general (h+1)(h+2)/2 = N(N +1)/2 ∈ Θ(N2), since N = h+1 for this kind of tree. Last modified: Wed Oct 16 16:03:40 2019 CS61B: Lecture #20 17 Iterators for Trees • Frankly, iterators are not terribly convenient on trees. • But can use ideas from iterative methods. class PreorderTreeIterator implements Iterator { private Stack> s = new Stack>();
publicPreorderTreeIterator(TreeT){s.push(T); }
public boolean hasNext() { return !s.isEmpty(); } public T next() {
Tree result = s.pop();
for (int i = result.arity()-1; i >= 0; i -= 1)
s.push(result.child(i));
return result.label();
Example: (what do I have to add to class Tree first?)
for (String label : aTree) System.out.print(label + ” “);
Last modified: Wed Oct 16 16:03:40 2019 CS61B: Lecture #20 18

Tree Representation
(a) Embedded child pointers (+ optional parent pointers)
… … …
(c) child/sibling pointers
(b) Array of child pointers (+ optional parent pointers)
(d) breadth-first array (complete trees)
Last modified: Wed Oct 16 16:03:40 2019
CS61B: Lecture #20 19

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com