Chapter 5: TREES
Trees
Trees Def) a tree is finite set of one or more nodes such that 1) there is a special node (root) 2) remaining nodes are partitioned into n 0 disjoint trees T 1,T 2,,T n where each of these is a tree; we call each T i subtree of the root acyclic graph : contain no cycle hierarchical structure
Trees Level 1 C D 2 E F G H I J 3 K L M 4
Trees terminology degree of a node: the number of subtrees of node degree of a tree: the maximum degree of the nodes in the tree leaf(terminal) node: a node with degree zero (K, L, F, G, M, I, J) internal(non-terminal) node: node with degree one or more (,, C, D, E, H)
Trees parent: a node that has subtrees child: a root of the subtrees sibling: child nodes of the same parent ancestor: all the nodes along the path from the root to the node descendant: all the nodes that are in its subtrees level: level of node s parent + 1 (level of the root node is 1) depth (or height) of a tree: the maximum level of any node in the tree
Trees Representation of trees list representation the information in the root node comes first followed by a list of the subtrees of that node (eg) (((E(K,L),F),C(G),D(H(M),I,J))) representation of a tree in memory where n is the degree of the tree data link 1 link 2 link n
Trees Representation of trees left-child right-sibling representation nodes of a fixed size easier to work two link / pointer fields per node left-child right-sibling node structure left child data right sibling
Trees left-child right-sibling representation of a tree C D E F G H I J K L M
Trees Representation of trees representation as a degree two tree simply rotate the left-child right-sibling tree clockwise by 45 degrees two children left child and right child degree 2 binary tree
Trees left-child right-child tree representation of a tree E C K F G D L H M I J
tree representations Trees tree left child-right sibling tree binary tree C C C tree left child-right sibling tree binary tree
inary Trees
inary Trees Def) a binary tree is a finite set of nodes such that 1) empty or 2) consists of root node and two disjoint binary trees, called, left subtree and right subtree two different binary trees
inary Trees Properties of binary trees difference between a binary tree and a tree may have empty node the order of subtree are important a binary tree is not a subset of a tree maximum number of nodes in a T 2 k -1 where k: depth of the tree relationship between the number of leaf nodes(n 0 ) and the number of nodes with degree 2(n 2 ) n 0 = n 2 + 1
inary Trees special types of binary trees skewed binary tree full binary tree (of depth k) def) a binary tree of depth k( 0) having 2 k - 1 nodes complete binary tree def) a binary tree with n nodes that correspond to the nodes numbered from 1 to n in the full binary tree of depth k
inary Trees full binary tree of depth 4 with sequential node numbers 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
inary Trees skewed and complete binary trees C C D D E F G E skewed binary tree H I complete binary tree
inary Trees binary tree representation array representation sequential representations determine the locations of the parent, left child, and right child of any node i in the binary tree 1) parent(i) is at i/2 if i 1 if i = 1, no parent 2) left_child(i) is at 2 i if 2i n 3) right_child(i) is at 2 i + 1 if 2 i + 1 n
inary Trees array representation of binary trees [1] [2] [3] [4] [5] [6] [7] [8] [9] [16] - C - - - D - E skew binary tree [1] [2] [3] [4] [5] [6] [7] [8] [9] C D E F G H I complete binary tree
inary Trees Problems of array representation inefficient storage utilization S(n) = 2 k -1 where k: depth of binary tree ideal for complete binary trees hard to insert/delete
linked representation inary Trees each node has three fields left_child, data, and right_child typedef struct node *tree_ptr; typedef struct node { }; int data; tree_ptr left_child, right_child; node representation for binary trees data left_child data right_child left_child right_child
inary Trees linked representation for the binary trees root NULL root NULL C C NULL D NULL E NULL NULL F NULL NULL G NULL D NULL NULL H NULL NULL I NULL NULL E NULL skewed binary tree complete binary tree
inary Trees leaf node s link fields contain null pointer NULL data NULL leaf node add a fourth field, parent, to know the parent of random nodes parent parent left_child data right_child data left_child right_child
inary Trees tree representation each node(in a tree) has variable sized nodes hard to represent it by using array use linked list need k link fields per node where k: degree of tree two types of link: non-null links and null links number of non-null links: n-1 number of null links: n k - (n-1)
inary Trees convert a tree into a binary tree 1) (parent,chilc 1,child 2,...,child k ) (parent,leftmost-child,next-right-sibling) leftchild right-sibling representation 2) simply rotate the left-child right-sibling tree clockwise by 45 degrees right field of root node always have null link null links: approximately 50% depth increased
inary Trees C D E F G tree E C F D C D G binary tree E F G left child-right sibling tree
inary Tree Traversal and Other Operations
inary Tree Traversals visit each node in the tree exactly once produce a linear order for the information in a tree what order? inorder: LVR (Left Visit Right) preorder: VLR (Visit Left Right) postorder: LRV (Left Right Visit) note) correspondence between these traversals and producing the infix, postfix, and prefix forms of expressions
inary Tree Traversals binary tree with arithmetic expression / * C * D + E (infix form) 1 + 2 * 17 E 3 14 * D 18 19 4 11 / C 15 16 5 8 12 13 6 7 9 10
inary Tree Traversals Inorder traversal void inorder(tree_ptr ptr) { } if(ptr) { } inorder(ptr->left_child); printf( %d,ptr->data); inorder(ptr->right_child); inorder is invoked 19 times for the complete traversal: 19 nodes output: /*C*D+E corresponds to the infix form
inary Tree Traversals trace of inorder call of inorder value in root action call of inorder value in root action 1 2 3 4 5 6 5 7 4 8 9 8 10 3 + * * / NULL NULL / NULL NULL * printf printf printf printf 11 12 11 13 2 14 15 14 16 1 17 18 17 19 C NULL C NULL * D NULL D NULL + E NULL E NULL printf printf printf printf printf
inary Tree Traversals Preorder traversal void preorder(tree_ptr ptr) { if(ptr) { printf( %d, ptr->data); preorder(ptr->left_child); preorder(ptr->right_child); } } output in the order: +**/CDE correspond to the prefix form
inary Tree Traversals Postorder traversal void postorder(tree_ptr ptr) { if (ptr) { postorder(ptr->left_child); postorder(ptr->right_child); printf( %d, ptr->data); } } output in the order: /C*D*E+ correspond to the postfix form
inary Tree Traversals Iterative inorder traversal recursion call itself directly or indirectly simple, compact expression: good readability don t need to know implementation details much storage: multiple activations exist internally slow execution speed application: factorial, fibonacci number, tree traversal, binary search, tower of Hanoi, quick sort, LISP structure
inary Tree Traversals iterative inorder traversal void iter_inorder(tree_ptr node) { } int top = -1; tree_ptr stack[mx_stck_size]; while (1) { } while (node) { } push(&top, node); node = node->left_child; node = pop(&top); if (!node) break; printf( %d, node->data); node = node->right_child;
inary Tree Traversals every node of the tree is placed on and removed from the stack exactly once time complexity: O(n) where n: the number of nodes in the tree space complexity: stack size O(n) where n: worst case depth of the tree (case of skewed binary tree)
inary Tree Traversals Level order traversal traversal by using queue(fifo) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 output in the order: 123456789 15 for previous example: +*E*D/C
inary Tree Traversals void level_order(tree_ptr ptr) { int front = rear = 0; tree_ptr queue[mx_queue_size]; if (!ptr) return; addq(front,&rear,ptr); while (1) { ptr = deleteq(&front, rear); if (ptr) { printf( %d, ptr->data); if (ptr->left_child) addq(front,&rear,ptr->left_child); if (ptr->right_child) addq(front,&rear,ptr->right_child); } else break; } }
dditional inary Tree Operations copying binary trees modified version of postorder tree_ptr copy(tree_ptr original) { } tree_ptr temp; if (original) { } temp = (tree_ptr)malloc(sizeof(node)); if (IS_FULL(temp)) exit(1); temp->left_child = copy(original->left_child); temp->right_child = copy(original->right_child); temp->data = original->data; return temp; return NULL;
dditional inary Tree Operations testing for equality of binary trees modified version of preorder int equal(tree_ptr first,tree_ptr second) { return ((!first &&!second) (first && second && (first->data == second->data) && equal(first->left_child, second->left_child) && equal(first->right_child, second->right_child)); }
Threaded inary Trees
Threaded inary Trees there are more null links than actual pointers in representation of any binary tree n+1 null links out of 2n total links how to use the null links? replace the null links by pointers, called threads, to other nodes in the tree
Threaded inary Trees construct the thread assume ptr represents a node rules 1) if ptr->left_child is null, then replace the null link with a pointer to the inorder predecessor of ptr 2) if ptr->right_child is null, then replace the null link with a pointer to the inorder successor of ptr
Threaded inary Trees threaded binary tree C D E F G H I
Threaded inary Trees how to distinguish actual pointers and threads? add two additional field to the node structure left_thread and right_thread if ptr->left_thread = TRUE ptr->left_child contains thread if ptr->left_thread = FLSE ptr->left_child contains a pointer to the left child same for right_thread
Threaded inary Trees threaded node structure typedef struct threaded_tree *threaded_ptr; typedef struct threaded_tree { short int left_thread; threaded_ptr left_child; char data; threaded_ptr right_child; short int right_thread; }; left_thread left_child data right_child right_thread
Threaded inary Trees two threads have been left dangling the left child of H the right child of G how to use two dangling links? add a head(=dummy) node an empty threaded tree left_thread left_child data right_child right_thread TRUE FLSE
Threaded inary Trees memory representation of a threaded tree root f -- f f f f f f C f f D f t E t t F t t G t t H t t I t f: FLSE t: TRUE
Threaded inary Trees inorder traversal of a threaded binary tree find the inorder successor of ptr if ptr->right_thread=true, then ptr->right_child otherwise follow a path of left-child links from the right-child of ptr until we reach a node with left_thread=true find inorder successor without using a stack
Threaded inary Trees finding the inorder successor of a node threaded_ptr insucc(threaded_ptr tree) { threaded_ptr temp; temp = tree->right_child; if (!tree->right_thread) while (!temp->left_thread) temp = temp->left_child; return temp; }
Threaded inary Trees inorder traversal repeated calls to insucc time: O(n) where n: number of nodes in a threaded binary tree inorder traversal of a threaded binary tree void tinorder(threaded_ptr tree) { } threaded_ptr temp = tree; for (;;) { } temp = insucc(temp); if (temp = tree) break; printf( %3c, temp->data);
Threaded inary Trees Inserting a node into a threaded binary tree insert child as the right child of parent 1) change parent->right_thread to FLSE 2) set child->left_thread and child->right_thread to TRUE 3) set child->left_child to point to parent 4) set child->right_child to point to parent->right_child 5) change parent->right_child to point to child 6) (if parent has nonempty right child) child becomes the inorder predecessor of the node that was previously parent s inorder successor
Threaded inary Trees right insertion in a threaded binary tree void insert_right(threaded_ptr parent, threaded_ptr child) { } threaded_ptr temp; child->right_child=parent->right_child; child->right_thread=parent->right_thread; child->left_child=parent; child->left_thread=true; parent->right_child=child; parent->right_thread=flse; if(!child->right_thread) { } temp=insucc(child); temp->left_child=child;
Threaded inary Trees root root parent parent C D child C D child before after
Threaded inary Trees root root parent parent child C D C X E F D child X E F before after