Application of tree data structure

binary tree data structure java and binomial tree data structure
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
ECE 250 Algorithms and Data Structures The Tree Data Structure Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.The tree data structure 2 Outline In this topic, we will cover: – Definition of a tree data structure and its components – Concepts of: • Root, internal, and leaf nodes • Parents, children, and siblings • Paths, path length, height, and depth • Ancestors and descendants • Ordered and unordered trees • Subtrees – Examples • XHTML and CSSThe tree data structure 3 The Tree Data Structure Trees are the first data structure different from what you’ve seen in your first-year programming courses http://xkcd.com/71/The tree data structure 4 4.1.1 Trees A rooted tree data structure stores information in nodes – Similar to linked lists: • There is a first node, or root • Each node has variable number of references to successors • Each node, other than the root, has exactly one node pointing to itThe tree data structure 5 4.1.1.1 Terminology All nodes will have zero or more child nodes or children – I has three children: J, K and L For all nodes other than the root node, there is one parent node – H is the parent IThe tree data structure 6 4.1.1.1 Terminology The degree of a node is defined as the number of its children: deg(I) = 3 Nodes with the same parent are siblings – J, K, and L are siblingsThe tree data structure 7 4.1.1.1 Terminology Phylogenetic trees have nodes with degree 2 or 0:The tree data structure 8 4.1.1.1 Terminology Nodes with degree zero are also called leaf nodes All other nodes are said to be internal nodes, that is, they are internal to the treeThe tree data structure 9 4.1.1.1 Terminology Leaf nodes:The tree data structure 10 4.1.1.1 Terminology Internal nodes:The tree data structure 11 4.1.1.2 Terminology These trees are equal if the order of the children is ignored – unordered trees They are different if order is relevant (ordered trees) – We will usually examine ordered trees (linear orders) – In a hierarchical ordering, order is not relevantThe tree data structure 12 4.1.1.3 Terminology The shape of a rooted tree gives a natural flow from the root node, or just rootThe tree data structure 13 4.1.1.3 Terminology A path is a sequence of nodes (a , a , ..., a ) 0 1 n where a is a child of a is k + 1 k The length of this path is n E.g., the path (B, E, G) has length 2The tree data structure 14 4.1.1.3 Terminology Paths of length 10 (11 nodes) and 4 (5 nodes) Start of these paths End of these pathsThe tree data structure 15 4.1.1.3 Terminology For each node in a tree, there exists a unique path from the root node to that node The length of this path is the depth of the node, e.g., – E has depth 2 – L has depth 3The tree data structure 16 4.1.1.3 Terminology Nodes of depth up to 17 0 4 9 14 17The tree data structure 17 4.1.1.3 Terminology The height of a tree is defined as the maximum depth of any node within the tree The height of a tree with one node is 0 – Just the root node For convenience, we define the height of the empty tree to be –1The tree data structure 18 4.1.1.3 Terminology The height of this tree is 17 17The tree data structure 19 4.1.1.4 Terminology If a path exists from node a to node b: – a is an ancestor of b – b is a descendent of a Thus, a node is both an ancestor and a descendant of itself – We can add the adjective strict to exclude equality: a is a strict descendent of b if a is a descendant of b but a ≠ b The root node is an ancestor of all nodesThe tree data structure 20 4.1.1.4 Terminology The descendants of node B are B, C, D, E, F, and G: The ancestors of node I are I, H, and A: