CS211 Spring 2002 Lecture 7: Trees and Recursion 2/11/2003 ------------------------------------------------------------------------------- 0) Announcements: + lecture notes and reading for 1/2 half of semester posted last week + A3 posted Thurs/Fri Objectives/Topics of Lecture 7: + continue intro to trees. see L3 (Tree1) and posted reading + we will do more with trees during inheritance topic ------------------------------------------------------------------------------- 1) Trees Linear Data Structure: + unique items placed next to each other + examples: array, list, stack, and more Non Linear Data Structure: + more than one child/next item + examples: tree, graph + list is "degenerate" tree (sometimes) Common examples: + file system + company hierarchy + inheritance hierarchy + cost/benefits + expert systems + geneology Definitions: GRAPH set of vertices (also called NODES, POINTS) and set of edges (also called LINES, ARCS) with each edge connecting a pair of vertices A graph has a PATH, which is a sequence of edges in which each edge connects to another edge at each vertex TREE a graph in which every pair of vertices has a unique path See http://www.nist.gov/dads/HTML/tree.html for more formality ROOTED The "top" node has no "incoming" edges (no parent) TREE All other nodes have a path to the root A rooted tree is usually just called TREE unrooted tree? see http://www.nist.gov/dads/HTML/freetree.html Node terminology: ROOT The "topmost" node to which all other nodes have a path PARENT The node "above" another node, leading towards the root CHILD The node "below" another node, leading sway from the root INTERNAL NODE A node that has a parent and at least one child LEAF A child node with no children SIBLING A node at the same "level" as another (see below) ANCESTOR An "eventual" parent node (see PATH) DESCENDANT An "eventual" child node (see PATH) ------------------------------------------------------------------------------- 2) Recursiveness of Trees (borrowing from DS&A) Mathematical: TREE is a finite, non-empty set of nodes T = {r} U T1 U T2 U ... U Tn s.t. 1) node r is the root of the tree 2) remaining nodes into n >= 0 subsets T1, T2, ..., Tn, each of which is a tree Use notation T = {r, T1, T2, ..., Tn} for a tree The subsets of T1,...,Tn are SUBTREES example) A T = {A,{B,{{D},{E}}},{C}} / \ B C T1 = {A} / \ T2 = {B,{{D},{E}} D E T3 = {C} The gist: + Each internal node is the root of its own tree. + A rooted tree consists of a root and a set of subtrees for each child of the root. The definitions are recursive! + BC: n=0 (no subtrees, just a root) + a tree is defined in terms of its subtress Why bother? STRUCTURAL INDUCTION ------------------------------------------------------------------------------- 3) Measuring Paths Need ways to analyze the organization of a tree's hierarchy PATH (from DS&A again) Given a tree T with set of nodes r[i] in R, a PATH P in T is the non-empty sequence of nodes P=r[1], r[2], ..., r[n] for 1 <= i <= k such that the ith node in the node sequence r[i] is the parent of the (i+1)th node in the sequence r[i+1]. What? example) assume a degenerate tree A->B->C->D root is A Path from A to D is A,B,C,D PATH LENGTH The length of path P is k-1. What? example) i starts 1 and k=4; so, length = 4-1 = 3 ------------------------------------------------------------------------------- 4) Height and Depth LEVEL (or DEPTH) of a node + Length of the path from the root to a node. + root starts at level 0 (in DS&SD, they say level 1) HEIGHT of a node: + longest path lengthfrom the node to a leaf + leaves are all at height zero HEIGHT of a tree: + height of root + essentially, the "max height of a node" example) A d(A) = 0, h(A) = 3 B C d(B) = 1, h(B) = 1 D E F d(C) = 1, h(C) = 2 G h(tree) = 3 ------------------------------------------------------------------------------- 5) Types of Trees DEGREE: number of subtrees associated with a node General tree: nodes can different degrees M- (or N-) Ary Trees: nodes all have the same degree (see DS&A for formal definition) Ordered tree: we're assuming that the order of the subtrees is important (otherwise, we have oriented trees) Binary tree: M (or N) = 2 ------------------------------------------------------------------------------- 6) Tree Traversals WALKING, TRAVERSING: visiting all of the nodes in a tree 2 ways to walk: + depth-first: visit an entire parent-child path until reaching a leaf + breadth-first: visit nodes on entire level focus on depth-first for now: + preorder traversal + in order traversal + postorder traversal binary trees: + preorder: visit root, traverse left subtree, traverse right subtree + in order: traverse left subtree, visit root, traverse right subtree + postorder: traverse left subtree, traverse right subtree, visit root ------------------------------------------------------------------------------- 7) Implementation See BinaryNode.java, BinaryTree.java, BinaryTreeTest.java + DS&SD and DS&A code is more general because of inheritance + the BinaryNode and BinaryTree are more limited, but clearer for now The gist: ref root var ---> node / | \ left val right ------------------------------------------------------------------------------- 8) Expression Parsing Discussed a bit more in section example (from DS&A): a/b + (c-d)e can draw tree Infix notation: + write operators in between operands + use in order traversal for printing + algorithm: print left paren, traverse left, print root, traverse right, print right paren ( ( a / b ) + ( ( c - d ) * e ) ) Prefix notation: + write operators in front of operands + handy for functional notation of operations (and moving beyond binary) + algorithm: print root, print left paren, traverse left, print comma, traverse right, print right paren +(/(a,b),*(-(c,d),e)) Postfix notation: + write operators at "end" of operands (CS212 people: see SaM) + no parens needed! + good for actually evaluating the value of the expression a b / c d - e * + -------------------------------------------------------------------------------