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) linksto 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 leafnode• A generalization of the parent-child relationship is theancestor-descendent relationship4Tree Terminology (continued)• A subtree of a node is a tree whose root is a child of thatnode• The level of a node is a measure of its distance from theroot• The height of a tree is the maximum level of any node inthe tree• the empty tree has height zero• You will also hear depth used interchangably forheight5Binary 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 followingis true• T is empty• Its root node has two subtrees, TL and TR, such thatTL 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 mightappear in a text file• Huffman code uses different numbers of bits toencode letters as opposed to ASCII or Unicode• Binary search trees• All elements in the left subtree precede those in theright subtree7Expression tree8Huffman 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 kchildren, I mean k non-empty children11Is this tree full?• Book is a little ambiguous• book doesn’t actually give a definition of full binarytrees• But this tree is full• but not perfect12Perfect Binary Trees• A binary tree is perfect it is a full binary tree and all leafnodes 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 atlevel h-1, and at height h, any unfilled nodes are on theright14Nodes in a complete tree can be numbered• Root is numbered 0• Children of a node numbered x are numbered 2x+1 and2x+2• The nodes of a complete tree with n nodes arenumbered 0..n-115General Trees• Nodes of a general tree can have any number ofsubtrees• A general tree can be represented using a binary tree16Tree Traversals• Often we want to determine the nodes of a tree and theirrelationship• Can do this by walking through the tree in aprescribed order and visiting the nodes as they areencountered• 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 mousethat walks along the edge of the tree• If the mouse always keeps the tree to the left, it willtrace a route known as the Euler tour• Preorder traversal if we record each node as the mouse firstencounters it• Inorder if each node is recorded as the mouse returns fromtraversing its left subtree• Postorder if we record each node as the mouse lastencounters it19Visualizing Tree Traversals
View Full Document
Unlocking...