際際滷

際際滷Share a Scribd company logo

CPSC 125 ch 5sec 2

G
guest862df4e

The document discusses trees and their representations in graphs. It defines trees as acyclic, connected graphs with one designated root node. Trees can be represented recursively or using adjacency lists and matrices. Binary trees are discussed, with examples of full and complete binary trees. Common tree traversal algorithms are presented: preorder, inorder and postorder. Applications of trees include decision trees, file systems and representing algebraic expressions. Infix, prefix and postfix notations are explained using binary expression trees.

1 of 15
Downloaded 17 times
Graphs and Trees Mathematical Structures for Computer Science Chapter 5 Copyright 息 2006 W.H. Freeman & Co. MSCS 際際滷s Graphs and Trees
Tree Terminology A special type of graph called a tree turns out to be a very useful representation of data. DEFINITION: TREE A tree is an acyclic, connected graph with one node designated as the root of the tree. An acyclic, connected graph with no designated root node is called a nonrooted tree or a free tree. Section 5.2 Trees and Their Representations 1
Defining Trees Recursively A tree can also be de鍖ned recursively. A single node is a tree (with that node as its root). If T1, T2, ... , Tt are disjoint trees with roots r1, r2, ... , rt, the graph formed by attaching a new node r by a single arc to each of r1, r2, ... , rt is a tree with root r. The nodes r1, r2, ... , rt are children of r, and r is a parent of r1, r2, ... , rt. Section 5.2 Trees and Their Representations 2
Tree Terminology The depth of a node in a tree is the length of the path from the root to the node; the root itself has depth 0. The depth (height) of the tree is the maximum depth of any node in the tree; in other words, it is the length of the longest path from the root to any node. A node with no children is called a leaf of the tree. All nonleaves are internal nodes. A forest is an acyclic graph (not necessarily connected). Section 5.2 Trees and Their Representations 3
Tree Terminology Binary trees are those where each node has at most two children. Each child of a node is designated as either the left child or the right child. A full binary tree (as seen in the middle 鍖gure below) occurs when all internal nodes have two children and all leaves are at the same depth. A complete binary tree (as seen in the right 鍖gure below) is an almost-full binary tree; the bottom level of the tree is 鍖lling from left to right but may not have its full complement of leaves. Section 5.2 Trees and Their Representations 4
Applications of Trees Decision trees were used to solve counting problems in Chapter 3. By using trees, a collection of records can be ef鍖ciently searched to locate a particular record or to determine that a record is not in the collection. A family tree is usually, indeed, a tree. Files stored on a computer are organized in a hierarchical (treelike) structure. Algebraic expressions involving binary operations can be represented by labeled binary trees. Section 5.2 Trees and Their Representations 5
Binary Tree Representation Because a tree is also a graph, representations for graphs in general can also be used for trees. Binary trees, however, have special characteristics that we want to capture in the representation, namely, the identity of the left and right child. The equivalent of an adjacency matrix is a two- column array (or an array of records) where the data for each node is the left and right child of that node. The equivalent of the adjacency list representation is a collection of records with three 鍖elds containing, respectively, the current node, a pointer to the record for the left-child node, and a pointer to the record for the right-child node. Section 5.2 Trees and Their Representations 6
Binary Tree Representation Example The tree represented by the 鍖gure above has the following adjacency list and adjacency matrix representations. Section 5.2 Trees and Their Representations 7
Tree Traversal Algorithms If a tree structure is being used to store data, it is often helpful to have a systematic mechanism for writing out the data values stored at all the nodes. This can be accomplished by traversing the tree, that is, visiting each of the nodes in the tree structure. The three common tree traversal algorithms are preorder, inorder, and postorder traversal. The terms preorder, inorder, and postorder refer to the order in which the root of a tree is visited compared to the subtree nodes. Section 5.2 Trees and Their Representations 8
Tree Traversal Algorithms In preorder traversal, the root of the tree is visited 鍖rst and then the subtrees are processed left to right, each in preorder. ALGORITHM Preorder Preorder(tree T) //Writes the nodes of a tree with root r in preorder write(r) for i 1 to t do Preorder(Ti) end for end Preorder Section 5.2 Trees and Their Representations 9
Tree Traversal Algorithms In inorder traversal, the left subtree is processed by an inorder traversal, then the root is visited, and then the remaining subtrees are processed from left to right, each in inorder. If the tree is binary, the result is that the root is visited between processing of the two subtrees. ALGORITHM Inorder Inorder(tree T ) //Writes the nodes of a tree with root r in inorder Inorder(T1) write(r) for i 2 to t do Inorder(Ti) end for end Inorder Section 5.2 Trees and Their Representations 10
Tree Traversal Algorithms In postorder traversal, the root is visited last, after all subtrees have been processed from left to right in postorder. ALGORITHM Postorder Postorder(tree T ) //Writes the nodes of a tree with root r in postorder for i 1 to t do Postorder(Ti) end for write(r) end Postorder Section 5.2 Trees and Their Representations 11
Tree Traversal Algorithms Example What is the preorder, inorder, and postorder traversal for the following tree? The preorder (root, left, right) traversal produces: a, b, d, e, c, f, h, i, g. The inorder (left, root, right) traversal produces: d, b, e, a, h, f, i, c, g. The postorder (left, right, root) traversal produces: d, e, b, h i, f, g, c, a. Section 5.2 Trees and Their Representations 12
Infix Notation The binary tree in the 鍖gure below represents the algebraic expression (2 + x) - (y * 3). If we do an inorder traversal of the expression tree, we retrieve the original algebraic expression. Parentheses are added as we complete the processing of a subtree. This is called in鍖x notation. Section 5.2 Trees and Their Representations 13
Polish Notation A preorder traversal of a tree as seen in this 鍖gure gives the expression * (2 + x) x 4. Here the operation symbol precedes its operands. This form of an expression is called pre鍖x notation, or Polish notation. The expression can be translated into in鍖x form as follows: * + 2 x 4 * (2 + x) 4 (2 + x ) * 4 A postorder traversal gives the expression 2 x 4 *, where the operation symbol follows its operands. This form of an expression is called post鍖x notation, or reverse Polish notation (or just RPN). The expression can be translated into in鍖x form as follows: 2 x 4 * (2 + x) 4 * (2 + x) * 4 Neither pre鍖x nor post鍖x form requires parentheses to avoid ambiguity. Section 5.2 Trees and Their Representations 14

More Related Content

CPSC 125 ch 5sec 2

  • 1. Graphs and Trees Mathematical Structures for Computer Science Chapter 5 Copyright 息 2006 W.H. Freeman & Co. MSCS 際際滷s Graphs and Trees
  • 2. Tree Terminology A special type of graph called a tree turns out to be a very useful representation of data. DEFINITION: TREE A tree is an acyclic, connected graph with one node designated as the root of the tree. An acyclic, connected graph with no designated root node is called a nonrooted tree or a free tree. Section 5.2 Trees and Their Representations 1
  • 3. Defining Trees Recursively A tree can also be de鍖ned recursively. A single node is a tree (with that node as its root). If T1, T2, ... , Tt are disjoint trees with roots r1, r2, ... , rt, the graph formed by attaching a new node r by a single arc to each of r1, r2, ... , rt is a tree with root r. The nodes r1, r2, ... , rt are children of r, and r is a parent of r1, r2, ... , rt. Section 5.2 Trees and Their Representations 2
  • 4. Tree Terminology The depth of a node in a tree is the length of the path from the root to the node; the root itself has depth 0. The depth (height) of the tree is the maximum depth of any node in the tree; in other words, it is the length of the longest path from the root to any node. A node with no children is called a leaf of the tree. All nonleaves are internal nodes. A forest is an acyclic graph (not necessarily connected). Section 5.2 Trees and Their Representations 3
  • 5. Tree Terminology Binary trees are those where each node has at most two children. Each child of a node is designated as either the left child or the right child. A full binary tree (as seen in the middle 鍖gure below) occurs when all internal nodes have two children and all leaves are at the same depth. A complete binary tree (as seen in the right 鍖gure below) is an almost-full binary tree; the bottom level of the tree is 鍖lling from left to right but may not have its full complement of leaves. Section 5.2 Trees and Their Representations 4
  • 6. Applications of Trees Decision trees were used to solve counting problems in Chapter 3. By using trees, a collection of records can be ef鍖ciently searched to locate a particular record or to determine that a record is not in the collection. A family tree is usually, indeed, a tree. Files stored on a computer are organized in a hierarchical (treelike) structure. Algebraic expressions involving binary operations can be represented by labeled binary trees. Section 5.2 Trees and Their Representations 5
  • 7. Binary Tree Representation Because a tree is also a graph, representations for graphs in general can also be used for trees. Binary trees, however, have special characteristics that we want to capture in the representation, namely, the identity of the left and right child. The equivalent of an adjacency matrix is a two- column array (or an array of records) where the data for each node is the left and right child of that node. The equivalent of the adjacency list representation is a collection of records with three 鍖elds containing, respectively, the current node, a pointer to the record for the left-child node, and a pointer to the record for the right-child node. Section 5.2 Trees and Their Representations 6
  • 8. Binary Tree Representation Example The tree represented by the 鍖gure above has the following adjacency list and adjacency matrix representations. Section 5.2 Trees and Their Representations 7
  • 9. Tree Traversal Algorithms If a tree structure is being used to store data, it is often helpful to have a systematic mechanism for writing out the data values stored at all the nodes. This can be accomplished by traversing the tree, that is, visiting each of the nodes in the tree structure. The three common tree traversal algorithms are preorder, inorder, and postorder traversal. The terms preorder, inorder, and postorder refer to the order in which the root of a tree is visited compared to the subtree nodes. Section 5.2 Trees and Their Representations 8
  • 10. Tree Traversal Algorithms In preorder traversal, the root of the tree is visited 鍖rst and then the subtrees are processed left to right, each in preorder. ALGORITHM Preorder Preorder(tree T) //Writes the nodes of a tree with root r in preorder write(r) for i 1 to t do Preorder(Ti) end for end Preorder Section 5.2 Trees and Their Representations 9
  • 11. Tree Traversal Algorithms In inorder traversal, the left subtree is processed by an inorder traversal, then the root is visited, and then the remaining subtrees are processed from left to right, each in inorder. If the tree is binary, the result is that the root is visited between processing of the two subtrees. ALGORITHM Inorder Inorder(tree T ) //Writes the nodes of a tree with root r in inorder Inorder(T1) write(r) for i 2 to t do Inorder(Ti) end for end Inorder Section 5.2 Trees and Their Representations 10
  • 12. Tree Traversal Algorithms In postorder traversal, the root is visited last, after all subtrees have been processed from left to right in postorder. ALGORITHM Postorder Postorder(tree T ) //Writes the nodes of a tree with root r in postorder for i 1 to t do Postorder(Ti) end for write(r) end Postorder Section 5.2 Trees and Their Representations 11
  • 13. Tree Traversal Algorithms Example What is the preorder, inorder, and postorder traversal for the following tree? The preorder (root, left, right) traversal produces: a, b, d, e, c, f, h, i, g. The inorder (left, root, right) traversal produces: d, b, e, a, h, f, i, c, g. The postorder (left, right, root) traversal produces: d, e, b, h i, f, g, c, a. Section 5.2 Trees and Their Representations 12
  • 14. Infix Notation The binary tree in the 鍖gure below represents the algebraic expression (2 + x) - (y * 3). If we do an inorder traversal of the expression tree, we retrieve the original algebraic expression. Parentheses are added as we complete the processing of a subtree. This is called in鍖x notation. Section 5.2 Trees and Their Representations 13
  • 15. Polish Notation A preorder traversal of a tree as seen in this 鍖gure gives the expression * (2 + x) x 4. Here the operation symbol precedes its operands. This form of an expression is called pre鍖x notation, or Polish notation. The expression can be translated into in鍖x form as follows: * + 2 x 4 * (2 + x) 4 (2 + x ) * 4 A postorder traversal gives the expression 2 x 4 *, where the operation symbol follows its operands. This form of an expression is called post鍖x notation, or reverse Polish notation (or just RPN). The expression can be translated into in鍖x form as follows: 2 x 4 * (2 + x) 4 * (2 + x) * 4 Neither pre鍖x nor post鍖x form requires parentheses to avoid ambiguity. Section 5.2 Trees and Their Representations 14