Trees CMSC 433 Chapter 8.1Tree TerminologyTree Terminology (continued)Slide 4Binary TreesSome Types of Binary TreesExpression treeHuffman TreesBinary Search TreeFull Binary TreesIs this tree full?Perfect Binary TreesComplete Binary TreesNodes in a complete tree can be numberedGeneral TreesTree TraversalsTree Traversals (continued)Visualizing Tree TraversalsVisualizing Tree Traversals (continued)TreesCMSC 433Chapter 8.1Nelson Padua-PerezBill Pugh2Tree Terminology•A tree consists of a collection of elements or nodes•Each node can contain data and (parent and child) links to other nodes•Each node has one parent, except for the root node, which has no parent•Each node can have any number of children3Tree Terminology (continued)•Nodes that have the same parent are siblings•A node that has no (non-empty) children is called a leaf node•A generalization of the parent-child relationship is the ancestor-descendent relationship4Tree Terminology (continued)•A subtree of a node is a tree whose root is a child of that node•The level of a node is a measure of its distance from the root•The height of a tree is the maximum level of any node in the tree•the empty tree has height zero•You will also hear depth used interchangably for height5Binary Trees•In a binary tree, each node has at most two subtrees•A set of nodes T is a binary tree if either of the following is true•T is empty•Its root node has two subtrees, TL and TR, such that TL and TR are binary trees6Some Types of Binary Trees•Expression tree•Each node contains an operator or an operand•Huffman tree•Represents Huffman codes for characters that might appear in a text file•Huffman code uses different numbers of bits to encode letters as opposed to ASCII or Unicode•Binary search trees•All elements in the left subtree precede those in the right subtree7Expression treeQuickTime™ and aTIFF (LZW) decompressorare needed to see this picture.8Huffman Trees0001010101111011110010001 010 10111 10111 10019Binary Search Tree10Full Binary Trees•A binary tree is full if each node has zero or two (non-empty) children•I’m going to stop saying non-empty children now; assume that whenever I say that a node has k children, I mean k non-empty children11Is this tree full?•Book is a little ambiguous•book doesn’t actually give a definition of full binary trees•But this tree is full•but not perfectQuickTime™ and aTIFF (LZW) decompressorare needed to see this picture.12Perfect Binary Trees•A binary tree is perfect it is a full binary tree and all leaf nodes are at the same level.•Recursively, a binary tree is perfect if•it is empty, or•it has two perfect children with equal height13Complete Binary Trees•A binary tree of height h is complete if it is filled up at level h-1, and at height h, any unfilled nodes are on the rightQuickTime™ and aTIFF (LZW) decompressorare needed to see this picture.QuickTime™ and aTIFF (LZW) decompressorare needed to see this picture.QuickTime™ and aTIFF (LZW) decompressorare needed to see this picture.14Nodes in a complete tree can be numbered•Root is numbered 0•Children of a node numbered x are numbered 2x+1 and 2x+2•The nodes of a complete tree with n nodes are numbered 0..n-1 QuickTime™ and aTIFF (LZW) decompressorare needed to see this picture.15General Trees•Nodes of a general tree can have any number of subtrees•A general tree can be represented using a binary tree16Tree Traversals•Often we want to determine the nodes of a tree and their relationship•Can do this by walking through the tree in a prescribed order and visiting the nodes as they are encountered•This process is called tree traversal•Three kinds of tree traversal•Inorder•Preorder•Postorder17Tree Traversals (continued)•Preorder: Visit root node, traverse TL, traverse TR•Inorder: Traverse TL, visit root node, traverse TR•Postorder: Traverse TL, Traverse TR, visit root node18Visualizing Tree Traversals•You can visualize a tree traversal by imagining a mouse that walks along the edge of the tree•If the mouse always keeps the tree to the left, it will trace a route known as the Euler tour•Preorder traversal if we record each node as the mouse first encounters it•Inorder if each node is recorded as the mouse returns from traversing its left subtree•Postorder if we record each node as the mouse last encounters it19Visualizing Tree Traversals
View Full Document
Unlocking...