Trees P.J. Drongowski 12 November 2004 **************************************** Tree (mathematical definition) **************************************** * A directed graph without cycles is called "acyclic" * A connected acyclic graph is called a "tree" * A "rooted tree" is a tree with one unique root node from which any other node is accessible by one and only one path * A "binary rooted tree" is a rooted tree where each node has at most two children (the left child and the right child) * If G is a tree: + Every two nodes of G are connected by a unique path + The number of nodes equals the number of edges plus one * A traversal of a tree yields a particular ordering of its nodes. Given a tree T with root node r where r is connected to the subtrees T1, T2, ... TN from left to right, we define the following three traversals of T. + Pre-order traversal: pre(T) = r, pre(T1), pre(T2), ... pre(TN) + Post-order traversal: post(T) = post(T1), post(T2), ... post(TN), r + In-order traversal for binary tree: in(T) = in(Tleft), r, in(Tright) * Sources + Modern Applied Algebra, Birkhoff and Bartee + Graph Theory, Harary **************************************** Uses of trees **************************************** * Trees in the real world + Family tree + Cell division (growth, generations) * Information processing + Unix file system and path names (or more generally, how to label a path in a hierarchy) + Windows registry + Structure of software project + Windows Explorer (expand/collapse file tree) + Call graph + Taxonomies + Decision trees + Power distribution grid on integrated circuit + Distribution of clock signal on integrated circuit Kinds of trees * N-ary: Up to N children below each node * Binary: Up to 2 children below each node * Balanced: **************************************** Binary tree **************************************** * A binary tree is a finite graph + A binary tree consists of nodes and edges + The number of nodes is finite * There is one special node called the "root" * Each node may be connected to zero, one or two other child (successor) nodes + A node without children is a "leaf node" + A node with one or more children is an "interior node" + For each interior node, The child node drawn to the left is the "left child" and the child node drawn to the right is the "right child" * With the exception of the root, each node has exactly one parent * Any node in a tree can be regarded as the root node of a subtree + This observation leads to recursive algorithms! + The subtree beginning with the left child of a node is the "left subtree" + The subtree beginning with the right child of a node is the "right subtree" Tree diagrams (rooted trees) * The root node is drawn at the top * The children of the root are drawn below the root + The left subtree is drawn to the left starting with the left child + The right ssubtree is drawn to the right starting with the right child **************************************** Definitions **************************************** Althought there is pretty good agreement about the definition of "parent," "child," "sibling," etc., authors sometimes define "height," "depth" and "level" differently. Read papers carefully and note the particular definition used by the author. Also, observe whether numbering the numbering scheme in use begins with zero or one. Your mileage may vary (YMMV.) * Siblings + Nodes with the same parent are called "siblings" * Descendants + The nodes within a subtree are "descendants" of the subtree's root node * Ancestors + Each node on the unique path from a node to the root (including the root) is an "ancestor" of the node + The root is an ancestor of every other node * Depth of a node + The "depth" of a node is the length of the path (number of edges) from the node to the root + The depth of a node is equal to the number of ancestors of the node + The depth of the root node is zero + The depth of any of the children of the root node is one + The depth of a node is one plus the depth of the parent of the node * Depth of a tree + The depth of a tree is the maximum depth of any of its leaf nodes * Height of a node + The "height" of a node is the length of the path from the node to the deepest leaf node + The height of a leaf node is 0 + The height of an interior node is one plus the maximum height of a child of the node * Tree height + The height of a tree is the height of the root node + The height of a tree is equal to the maximum depth of any of the leaf nodes + An empty tree has height zero + A tree with just one node has height one + The maximum number of nodes in a tree of height M is 2^(M+1)-1 * Level + The level of a node is the same as its height + The level D of a tree is the set of all nodes with the same depth d + The root node is level zero * Full binary tree + In a full binary tree, every leaf has the same height and every interior node has two children + Every node has exactly two children or no children at all * Complete binary tree + In a complete binary tree, every level except possibly the deepest level is filled, AND + At the deepest level, all nodes must be arranged as far left as possible **************************************** Array representation of binary tree **************************************** * A binary tree can be laid down level-by-level in an array as shown below * The left and right child of a node at index i is easily selected: + Left child is at index (2*i) + Right child is at index (2*i)-1 Node Left child Right child ---- ---------- ----------- 1 2 3 2 4 5 1 3 6 7 / \ 4 8 9 / \ 5 10 11 / \ 6 12 13 / \ 7 14 15 2 3 8 * * / \ / \ 9 * * / \ / \ 10 * * 4 5 6 7 11 * * / \ / \ / \ / \ 12 * * 8 9 10 11 12 13 14 15 13 * * 14 * * 15 * * The array representation of a tree can be used to implement a "heap" data structure. The tree (heap) must satisfy two properties: * [Ordering property] For every node n other than the root, the value stored at n is greater than or equal to the value stored at n's parent. * [Structural property] The tree must be complete. The smallest value msut be stored at the root of the tree. All values on a path from the root to a leaf node are in nondecreasing order. **************************************** Linked node representation **************************************** * A tree node is easily represented using a class or struct: class Node { private: int data ; Node *left ; Node *right ; public: Node() { data = 0 ; right = left = NULL ; } } ; * The data member can be replaced by application-specific data items as needed **************************************** Simple traversals **************************************** * Like linked lists, we need to be able to traverse (walk) trees * There are three kinds of simple traversals: preorder, postorder, inorder * These traversals visit each node exactly once * It's easiest to give recursive definitions of the traversals * The main difference between traversals is when the "visit" action is performed upon the node data relative to the recursive calls to traverse the left and right subtrees 4 / \ / \ Pre-order: 4, 14, 4, 12, 10, 22, 10, 18, 8 / \ Post-order: 4, 10, 22, 12, 14, 8, 18, 10, 4 14 10 In-order: 4, 14, 10, 12, 22, 4, 10, 8, 18 / \ \ 4 12 18 / \ / 10 22 8 * Preorder traversal starting at node n 1. Perform the visit action on the node data 2. If the node is an interior node, a. Perform preorder traversal beginning with the left child of n b. Perform preorder traversal beginning with the right child of n * Postorder traversal starting at node n 1. If the node is an interior node, a. Perform postorder traversal beginning with the left child of n b. Perform postorder traversal beginning with the right child of n 2. Perform the visit action on the node data * Postorder traversal starting at node n 1. If the node is an interior node, perform inorder traversal beginning with the left child of n 2. Perform the visit action on the node data 3. If the node is an interior node, perform inorder traversal beginning with the right child of n **************************************** Euler traversal **************************************** * An Euler tour traversal is a tour around the edges of a tree * Each node is encountered three times: + On the left, before the Euler tour of the left subtree + From below, between Euler tours of the two subtrees + On the right, after the Euler tour of the right subtree * For leaf nodes, all three visits happen at the same time * Euler tour 1. Perform the action for visiting the node "on the left" 2. If the node is an interior node, tour the left subtree 3. Perform the action for visiting the node "from below" 4. If the node is an interior node, tour the right subtree 5. Perform the action for visiting the node "on the right" * Example: Displaying a fully parenthesized infix expression * If the node is a leaf node, display the value of the node * If the node is an interior node, 1. Display '(' 2. Tour the left subtree 3. Display the operator associated with the node 4. Tour the right subtree 5. Dipslay ')' Sources: Data Structures and Algorithms in Java, Goodrich and Tamassia, 2001 Data Structures and other Objects Using C++, Main and Savitch, 2005 Data Structures and Problem Solving Using Java, Weiss, 2002 Problem Solving with Java, Koffman and Wolz, 2002 *********************************************************** tree.h *********************************************************** #ifndef TREE_H #define TREE_H #include class Node { friend class Tree ; private: int data ; Node *left ; Node *right ; public: Node() { data = 0 ; right = left = NULL ; } } ; class Tree { public: Tree() ; Node *make_root(int value) ; Node *insert_left(Node *parent, int value) ; Node *insert_right(Node *parent, int value) ; void preorder() ; void inorder() ; void postorder() ; private: Node *root ; void inner_preorder(Node *node) ; void inner_inorder(Node *node) ; void inner_postorder(Node *node) ; } ; #endif *********************************************************** tree.cpp *********************************************************** #include #include using namespace std ; #include "tree.h" Tree::Tree() { root = NULL ; } Node *Tree::make_root(int value) { Node *pNew ; pNew = new Node() ; pNew->data = value ; root = pNew ; } Node *Tree::insert_left(Node *parent, int value) { Node *pNew ; pNew = new Node() ; pNew->data = value ; parent->left = pNew ; } Node *Tree::insert_right(Node *parent, int value) { Node *pNew ; pNew = new Node() ; pNew->data = value ; parent->right = pNew ; } void Tree::inner_preorder(Node *node) { if (node == NULL) return ; else { cout << node->data << " " ; inner_preorder(node->left) ; inner_preorder(node->right) ; } } void Tree::preorder() { cout << "Pre-order traversal: " ; inner_preorder(root) ; cout << endl ; } void Tree::inner_inorder(Node *node) { if (node == NULL) return ; else { inner_inorder(node->left) ; cout << node->data << " " ; inner_inorder(node->right) ; } } void Tree::inorder() { cout << "In-order traversal: " ; inner_inorder(root) ; cout << endl ; } void Tree::inner_postorder(Node *node) { if (node == NULL) return ; else { inner_postorder(node->left) ; inner_postorder(node->right) ; cout << node->data << " " ; } } void Tree::postorder() { cout << "Post-order traversal: " ; inner_postorder(root) ; cout << endl ; } *********************************************************** ex1.cpp *********************************************************** #include "tree.h" // root // / \ // / \ // 14 10 // / \ \ // 4 12 18 // / \ / // 10 22 8 int main() { Tree tree ; Node *root ; Node *pA, *pB, *pC, *pD, *pE, *pF ; Node *pG, *pH ; root = tree.make_root(4) ; pA = tree.insert_left(root, 14) ; pB = tree.insert_right(root, 10) ; pC = tree.insert_left(pA, 4) ; pD = tree.insert_right(pA, 12) ; pE = tree.insert_left(pD, 10) ; pF = tree.insert_right(pD, 22) ; pG = tree.insert_right(pB, 18) ; pH = tree.insert_left(pG, 8) ; tree.preorder() ; tree.inorder() ; tree.postorder() ; } *********************************************************** ex2.cpp *********************************************************** #include "tree.h" // 0 // / \ // / \ // / \ // 1 2 // / \ / \ // 3 4 5 6 // \ / \ // 7 8 9 int main() { Tree tree ; Node *p0 ; Node *p1, *p2, *p3, *p4, *p5, *p6 ; Node *p7, *p8, *p9 ; p0 = tree.make_root(0) ; p1 = tree.insert_left (p0, 1) ; p2 = tree.insert_right(p0, 2) ; p3 = tree.insert_left (p1, 3) ; p4 = tree.insert_right(p1, 4) ; p7 = tree.insert_right(p4, 7) ; p5 = tree.insert_left (p2, 5) ; p6 = tree.insert_right(p2, 6) ; p8 = tree.insert_left (p5, 8) ; p9 = tree.insert_right(p5, 9) ; tree.preorder() ; tree.inorder() ; tree.postorder() ; } *********************************************************** ex3.cpp *********************************************************** #include "tree.h" // 1 // / \ // / \ // / \ // / \ // 2 3 // / \ / \ // / \ / \ // 4 5 6 7 // / \ / \ / \ / \ // 8 9 10 11 12 13 14 15 int main() { Tree tree ; Node *p1, *p2, *p3, *p4, *p5, *p6 ; Node *p7, *p8, *p9, *p10, *p11, *p12 ; Node *p13, *p14, *p15 ; p1 = tree.make_root(1) ; p2 = tree.insert_left (p1, 2) ; p3 = tree.insert_right(p1, 3) ; p4 = tree.insert_left (p2, 4) ; p5 = tree.insert_right(p2, 5) ; p8 = tree.insert_left (p4, 8) ; p9 = tree.insert_right(p4, 9) ; p10 = tree.insert_left (p5, 10) ; p11 = tree.insert_right(p5, 11) ; p6 = tree.insert_left (p3, 6) ; p7 = tree.insert_right(p3, 7) ; p12 = tree.insert_left (p6, 12) ; p13 = tree.insert_right(p6, 13) ; p14 = tree.insert_left (p7, 14) ; p15 = tree.insert_right(p7, 15) ; tree.preorder() ; tree.inorder() ; tree.postorder() ; }