tailieunhanh - Data Structures and Algorithms: Trees

Data Structures and Algorithms: Trees products Tree ADT, Preorder and postorder traversals, BinaryTree ADT, Inorder traversal, Tree Terminology, Preorder Traversal, Postorder Traversal. | Make Money Fast! Trees Stock Fraud Ponzi Scheme Bank Robbery Data structures and Algorithms Acknowledgement: These slides are adapted from slides provided with Data Structures and Algorithms in C++ Goodrich, Tamassia and Mount (Wiley, 2004) Outline and Reading Tree ADT (§) Preorder and postorder traversals (§) BinaryTree ADT (§) Inorder traversal (§) Trees 2 What is a Tree Computers”R”Us • In computer science, a tree is an abstract model of a Sales hierarchical structure • A tree consists of US International nodes with a parent-child relation Europe Asia • Applications: Organization charts File systems Trees Manufacturing Laptops R&D Desktops Canada 3 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. Trees • Subtree: tree consisting of a node and its descendants A B E C F G D H subtree I J K 4 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 .