advertisement

CSCI 3333 Data Structures Trees by Dr. Bun Yue Professor of Computer Science yue@uhcl.edu http://sce.uhcl.edu/yue/ 2013 Acknowledgement Mr. Charles Moen Dr. Wei Ding Ms. Krishani Abeysekera Dr. Michael Goodrich What is a Tree In computer Computers”R”Us science, a tree is an abstract model of a Sales Manufacturing R&D hierarchical structure A tree consists US International Laptops Desktops of nodes with a parent-child Europe Asia Canada relation Trees Each node in the tree has 0 or 1 parent node. 0 or more child nodes. Only the root node has no parent. A tree can be considered as a special case of a directed (acyclic) graph. Example: a family tree may not necessarily be a tree in the computing sense. Trees British Royal Family Tree Queen Victoria King Edward VII Albert Victor Alice King George V King Edward VIII King George VI Queen Elizabeth II Charles William Henry Ann Peter Andrew Zara Beatrice Eugenie Edward 5 Some Tree Applications Applications: Organization charts File Folders Email Repository Programming environments: e.g. drop down menus. Recursive Definition of Trees An empty tree is a tree. A tree contains a root node connected to 0 or more child subtrees. Trees Are these trees? 1 3 2 4 8 Tree Terminology Root: node without parent (A) Internal node: node with at least one child (A, B, C, F) External node (a.k.a. leaf ): node without children (E, I, J, K, G, H, D) Ancestors of a node: parent, grandparent, grandgrandparent, etc. Depth of a node: number of E ancestors Height of a tree: maximum depth of any node (3) Descendant of a node: child, I grandchild, grand-grandchild, etc. Subtree: tree consisting of a node and its descendants A B C F J G K D H subtree Tree ADT (§ 6.1.2) We use positions to abstract nodes Generic methods: integer size() boolean isEmpty() Iterator elements() Iterator positions() Accessor methods: position root() position parent(p) positionIterator children(p) Query methods: Update method: boolean isInternal(p) boolean isExternal(p) boolean isRoot(p) object replace (p, o) Additional update methods may be defined by data structures implementing the Tree ADT Interface TreeNode in Java Enumeration children(): Returns the children of the receiver as an Enumeration. boolean getAllowsChildren(): Returns true if the receiver allows children. TreeNode getChildAt(int childIndex): Returns the child TreeNode at index childIndex. int getChildCount(): Returns the number of children TreeNodes the receiver contains. int getIndex(TreeNode node): Returns the index of node in the receivers children. TreeNode getParent(): Returns the parent TreeNode of the receiver. Boolean isLeaf(): Returns true if the receiver is a leaf. Interface MutatableTreeNode Sub-interface of TreeNode Methods: void insert(MutableTreeNode child, int index): Adds child to the receiver at index. void remove(int index): Removes the child at index from the receiver. void remove(MutableTreeNode node): Removes node from the receiver. void removeFromParent(): Removes the receiver from its parent. void setParent(MutableTreeNode newParent): Sets the parent of the receiver to newParent. void setUserObject(Object object): Resets the user object of the receiver to object. Size of a tree Size = number of nodes in the tree. Recursion analysis: Base case: empty root => return 0; Recursive case: non-empty root => return 1 + sum of size of all child sub-trees. Size of a tree Algorithm size(TreeNode root) Input TreeNode root Output: size of the tree if (root = null) return 0; else return 1 + Sum of sizes of all children of root end if Implementation in Java public static int size(TreeNode root) { if (root == null) return 0; Enumeration enum = root.children(); int result = 1; // count the root. while (enum.hasMoreElement()) { result += size((TreeNode) enum.nextElement()); } return result; } Trees in languages There are no general tree classes in the standard libraries in many languages: e.g. C++ STL, Ruby, Python, etc. No single interface tree design satisfies all users. There may be specialized trees, especially for GUI design. E.g. JTree in Java FXTreeList in Ruby Tree Traversal Traversing is the systematic way of accessing, or ‘visiting’ all the nodes in a tree. Consider the three operations on a binary tree: V: Visit a node L: (Recursively) traverse the left subtree of a node R: (Recursively) traverse the right subtree of a node Tree Traversing We can traverse a tree in six different orders: LVR VLR LRV VRL RVL RLV 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 1 Algorithm preOrder(v) visit(v) for each child w of v preorder (w) Make Money Fast! 2 5 1. Motivations 9 2. Methods 3 4 1.1 Greed 1.2 Avidity 6 2.1 Stock Fraud 7 2.2 Ponzi Scheme References 8 2.3 Bank Robbery Java Implementation public static void preorder(TreeNode root) { if (root != null) { visit(root); // assume declared. Enumernation enum = root.children(); while (enum.hasMoreElement()) { preorder((TreeNode) enum.nextElement()); } } 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 9 Algorithm postOrder(v) for each child w of v postOrder (w) visit(v) cs16/ 3 8 7 homeworks/ todo.txt 1K programs/ 1 2 h1c.doc 3K h1nc.doc 2K 4 DDR.java 10K 5 Stocks.java 25K 6 Robot.java 20K Inorder Traversal For binary tree, inorder traversal can also be defined: L V R. Java Implementation public static void inorder(TreeNode root) { if (root != null) { inorder(root.getChildAt(0)); visit(root); // assume declared. inorder(root.getChildAt(1)); } Expression Notation There are three common notations for expressions: Prefix: operator come before operands. Postfix: operator come after operands. Infix: Binary operator come between operands. Unary operator come before the operand. Examples Infix: (a+b)*(c-d/f/(g+h)) Prefix: *+ab-c//df+gh Used by human being. E.g. functional language such as Lisp: Lisp: (* (+ a b) (- c (/ d (/ f (+ g h))))) Postfix: ab+cdf/gh+/-* E.g. Postfix calculator Expression Trees An expression tree can be used to represent an expression. Operator: root Operands: child sub-trees Variable and constants: leaf nodes. Traversals of Expression Trees Preorder traversal => prefix notation. Postorder traversal => postfix notation. Inorder traversal with parenthesis added => infix notation. Linked Structure for Trees A node is represented by an object storing Element Parent node Sequence of children nodes B Node objects implement the Position ADT D C A B A D F F E C E Tree Classes in Ruby FXTreeItem: a tree node for GUI application. Some methods: Tree related: childOf?, parentOf?, numChildren, parent, etc. Traversal of child nodes: first, next, last, etc. GUI related: selected?, selected=, hasFocus?, etc. Tree Classes in Ruby 2 FXTreeList: a list of FXTreeItem. Include methods for list manipulation, such as appendItem, clearItems, etc. Questions and Comments?