2/4/14 1 Chapter 7:Trees Nancy Amato Parasol Lab, Dept. CSE, Texas A&M University Acknowledgement: These slides are adapted from slides provided with Data Structures and Algorithms in C++, Goodrich, Tamassia and Mount (Wiley 2004) Make Money Fast! Stock Fraud Ponzi Scheme Bank Robbery http://parasol.tamu.edu Trees Outline and Reading • Tree Definitions and ADT (§7.1) • Tree Traversal Algorithms for General Trees (preorder and postorder) (§7.2) • BinaryTrees (§7.3) • Traversals of Binary Trees (preorder, inorder, postorder, and Euler Tour) (§7.3.6) • Template method pattern (§7.3.7) • Data structures for trees (§7.1.4 and §7.3.4) • C++ implementation (§7.1.3 and §7.3.2) 2 Trees What is a Tree • In computer science, a tree is an abstract model of a hierarchical structure • A tree consists of nodes with a parent-child relation • Applications: • Organization charts • File systems • Programming environments Computers”R”Us Sales R&D Manufacturing Laptops Desktops US International Europe Asia Canada 3 Trees subtee Tree Terminology • Root: node without parent (A) • Internal node: node with at least one child (A, B, C, F) • Leaf (aka External node): node without children (E, I, J, K, G, H, D) • Ancestors of a node: parent, grandparent, great-grandparent, etc. • Depth of a node: number of ancestors • Height of a tree: maximum depth of any node (3) • Descendant of a node: child, grandchild, great-grandchild, etc. A B D C G H E F I J K • Subtree: tree consisting of a node and its descendants 4 Trees Exercise: Trees • Answer the following questions about the tree shown on the right: • What is the size of the tree (number of nodes)? • Classify each node of the tree as a root, leaf, or internal node • List the ancestors of nodes B, F, G, and A. Which are the parents? • List the descendents of nodes B, F, G, and A. Which are the children? • List the depths of nodes B, F, G, and A. • What is the height of the tree? • Draw the subtrees that are rooted at node F and at node K. A B D C G H E F I J K 5 Trees Tree ADT • We use positions to abstract nodes • Generic methods: • integer size() • boolean isEmpty() • objectIterator elements() • positionIterator positions() • Accessor methods: • position root() • position parent(p) • positionIterator children(p) • Query methods: • boolean isInternal(p) • boolean isLeaf (p) • boolean isRoot(p) • Update methods: • swapElements(p, q) • object replaceElement(p, o) • Additional update methods may be defined by data structures implementing the Tree ADT 62/4/14 2 Trees ∅ A Linked Structure for General Trees • A node is represented by an object storing • Element • Parent node • Sequence of children nodes • Node objects implement the Position ADT B D A C E F B ∅ ∅ A D F ∅ C ∅ E 7 Trees Preorder Traversal • A traversal visits the nodes of a tree in a systematic manner • In a preorder traversal, a node is visited before its descendants • Application: print a structured document Algorithm preOrder(v)!visit(v)!for each child w of v!!preOrder(w)!Make Money Fast! 1. Motivations References 2. Methods 2.1 Stock Fraud 2.2 Ponzi Scheme 1.1 Greed 1.2 Avidity 2.3 Bank Robbery 1 2 3 5 4 6 7 8 9 8 Trees Exercise: Preorder Traversal • In a preorder traversal, a node is visited before its descendants • List the nodes of this tree in preorder traversal order. Algorithm preOrder(v)!visit(v)!for each child w of v!!preOrder (w)!A B D C G H E F I J K 9 Trees Postorder Traversal • In a postorder traversal, a node is visited after its descendants • Application: compute space used by files in a directory and its subdirectories Algorithm postOrder(v)!for each child w of v!!postOrder(w)!visit(v)!cs16/ homeworks/ todo.txt 1K programs/ DDR.java 10K Stocks.java 25K h1c.doc 3K h1nc.doc 2K Robot.java 20K 9 3 1 7 2 4 5 6 8 10 Trees Exercise: Postorder Traversal Algorithm postOrder(v)!for each child w of v! postOrder(w)!visit(v)!• In a postorder traversal, a node is visited after its descendants • List the nodes of this tree in postorder traversal order. A B D C G H E F I J K 11 Trees Binary Tree • A binary tree is a tree with the following properties: • Each internal node has two children • The children of a node are an ordered pair • We call the children of an internal node left child and right child • Alternative recursive definition: a binary tree is either • a tree consisting of a single node, or • a tree whose root has an ordered pair of children, each of which is a binary tree • Applications: • arithmetic expressions • decision processes • searching A B C F G D E H I 122/4/14 3 Trees Arithmetic Expression Tree • Binary tree associated with an arithmetic expression • internal nodes: operators • leaves: operands • Example: arithmetic expression tree for the expression (2 × (a - 1) + (3 × b)) +#×#×#-#2 a 1 3 b 13 Trees Decision Tree • Binary tree associated with a decision process • internal nodes: questions with yes/no answer • leaves: decisions • Example: dining decision Want a fast meal? How about coffee? On expense account? Starbucks Spike’s Al Forno Café Paragon Yes No Yes No Yes No 14 Trees Properties of Binary Trees • Notation n number of nodes l number of leaves i number of internal nodes h height • Properties: • l = i + 1 • n = 2l - 1 • h ≤ i • h ≤ (n - 1)/2 • l ≤ 2h • h ≥ log2 l • h ≥ log2 (n + 1) - 1 15 Trees BinaryTree ADT • The BinaryTree ADT extends the Tree ADT, i.e., it inherits all the methods of the Tree ADT • Additional methods: • position leftChild(p) • position rightChild(p) • position sibling(p) • Update methods may be defined by data structures implementing the BinaryTree ADT 16 Trees A Linked Structure for Binary Trees • A node is represented by an object storing • Element • Parent node • Left child node • Right child node • Node objects implement the Position ADT B D A C E ∅ ∅ ∅ ∅ ∅ ∅ B A D C E ∅ 17 Trees Inorder Traversal • In an inorder