资源描述
OUTLINEn10.1 Introduction to Treesn10.2 Applications of Treesn10.3 Tree Traversaln10.4 Spanning Treesn10.5 Minimal Spanning TreesCh10-110.1 INTRODUCTION TO TREESExample 1.Which of the graphs are trees?Def 1 A tree is a connected undirected graph with no simple circuits.Sol:G1,G2 Note.若拿掉connected的条件，就变成 forest Ch10-2Thm 1.Any undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.Def 2.A rooted tree is a tree in which one vertex has been designed as the root and every edge is directed away from the root.ExampleCh10-3DEF:A IS THE PARENT OF B,B IS THE CHILD OF A,C,D,E ARE SIBLINGS,A,B,D ARE ANCESTORS OF F C,D,E,F,G ARE DESCENDANTS OF B C,E,F,G ARE LEAVES OF THE TREE (DEG=1)A,B,D ARE INTERNAL VERTICES OF THE TREE (AT LEAST ONE CHILD)SUBTREE WITH D AS ITS ROOT:abfcedgfdgCh10-4Def 3 A rooted tree is called an m-ary tree if everyinternal vetex has no more than m children.The treeis called a full m-ary tree if every internal vertex has exactly m children.An m-ary tree with m=2 is calleda binary tree.Example 3 full binary tree full 3-ary tree full 5-ary tree not full 3-ary tree Ch10-5aebcfDef:left child of a right child of c right subtree of a dleft subtree of a Ch10-6 Properties of TreesThm 2.A tree with n vertices has n-1 edges.Pf.(by induction on n)n=1 :K1 is the only tree of order 1,|E(K1)|=0.ok!Assume the result is true for every trees of order n=k.Let T be a tree of order n=k+1,v be a leaf of T.Let T be the tree T-v.|V(T)|=k,and|E(T)|=k-1 by the induction hypothesis.|E(T)|=kBy induction,the result is true for all trees.#Ch10-7Thm 3.A full m-ary tree with i internal vertices contains n=mi+1 vertices.Pf.Every vertex,except the root,is the child of an internal vertex.Each internal vertex has m children.there are mi+1 vertices in the tree Exercise:19Cor.A full m-ary tree with n vertices contains(n-1)/m internal vertices,and hence n-(n-1)/m=(m-1)n+1)/m leaves.Ch10-8Def:The level of a vertex v in a rooted tree is the length of the unique path from the root to this vertex.The level of the root is defined to be zero.The height of a rooted tree is the maximum of the levels of vertices.Example 10.height=4level01234Ch10-9Def:A rooted m-ary tree of height h is balanced if allleaves are at levels h or h-1.Example 11 Which of the rooted trees shown below are balanced?Sol.T1,T3Thm 5.There are at most mh leaves in an m-ary treeof height h.Ch10-10Def:A complete m-ary tree is a full m-ary tree,where every leaf is at the same level.Ex 28 How many vertices and how many leaves doesa complete m-ary tree of height h have?Sol.#of vertices=1+m+m2+mh=(mh+1-1)/(m-1)#of leaves=mh Ch10-1110.2 APPLICATIONS OF TREESBinary Search TreesGoal:Implement a searching algorithm that finds items efficiently when the items are totally ordered.Binary Search Tree:Binary tree+each child of a vertex is designed as a right or left child,and each vertex v is labeled with a key label(v),which is one of the items.Note:label(v)label(w)if w is in the left subtree of v and label(v)label(w)if w is in the right subtree of v Ch10-12Example 1 Form a binary search tree for the words mathematics,physics,geography,zoology,meteorology,geology,psychology,and chemistry(using alphabetical order).Sol.Ch10-13Example 1 Form a binary search tree for the words mathematics,physics,geography,zoology,meteorology,geology,psychology,and chemistry(using alphabetical order).Procedure insertion(T:binary search tree,x:item)v:=root of Ta vertex not present in T has the value nullwhile v null and label(v)xbegin if x label(v)then if left child of v null then v:=left child of v else add new vertex as a left child of v and set v:=null else if right child of v null then v:=right child of v else add new vertex as a right child of v and set v:=nullend if root of T=null then add a vertex v to the tree and label it with xelse if v is null or label(v)x then label new vertex with x and let v be this new vertexv=location of xALGORITHM 1(LOCATING AND ADDING ITEMS TO A BINARY SEARCH TREE.)Ch10-14Example 2 Use Algorithm 1 to insert the word oceanography into the binary search tree in Example 1.Sol.psychologychemistryphysicsgeology zoologygeographymathematicsmeteorologyvlabel(v)=mathematics oceanography label(v)=meteorology oceanography oceanographyExercise:1,3Ch10-15Decision TreesA rooted tree in which each internal vertex corresponds to a decision,with a subtree at these vertices for each possible outcome of the decision,is called a decision tree.Example 3 Suppose there are seven coins,all with the same weight,and a counterfeit coin that weights less than the others.How many weighings are necessary using a balance scale to determine which of the eight coins is the counterfeit one?Give an algorithm for finding this counterfeit coin.Ch10-16Sol.称重时，可能左重、右重或平衡 3-ary treeNeed 8 leaves 至少需称两次Exercise:7Ch10-17Example 4 A decision tree that orders the elements of the list a,b,c.Sol.Ch10-18Prefix CodesProblem:Using bit strings to encode the letter of the English alphabet each letter needs a bit string of length 5 Is it possible to find a coding scheme of these letter such that when data are coded,fewer bits are used?Encode letters using varying numbers of bits.Some methods must be used to determine where the bits for each character start and end.Prefix codes:Codes with the property that the bit string for a letter never occurs as the first part of the bit string for another letter.Ch10-19Example:(not prefix code)e:0,a:1,t:01 The string 0101 could correspond to eat,tea,eaea,or tt.Example:(prefix code)e:0,a:10,t:11 The string 10110 is the encoding of ate.Ch10-20decode11111011100A prefix code can be represented using a binary tree.character:the label of the leafedge label:left child 0,right child 1The bit string used to encode a character is the sequenceof labels of the edges in the unique path from the root tothe leaf that has this character as its label.Example:encodee:0a:10 t :110n:1110s:1111 sanesaneExercise:22Ch10-21Huffman Coding(data compression)Input the frequencies of symbols in a string and outputa prefix code that encodes the string using the fewest possible bits,among all possible binary prefix codes forthese symbols.Ch10-22Procedure Huffman(C:symbols ai with frequencies wi,i=1,n)F:=forest of n rooted trees,each consisting of the single vertex ai and assigned weighted wi while F is not a treebegin Replace the rooted trees T and T of least weights from F with w(T)w(T)with a tree having a new root that has T as its left subtree and T as its right subtree.Label the new edge to T with 0 and the new edge to T with 1.Assign w(T)+w(T)as the weight of the new tree.end ALGORITHM 2(HUFFMAN CODING)Ch10-23Exercise:23Example 5 Use Huffman coding to encode the followingsymbols with the frequencies listed:A:0.08,B:0.10,C:0.12,D:0.15,E:0.20,F:0.35.What is the average number of bits used to encode a character?Sol:1.See the following figure 2.The average number of bits is:=30.08+30.10+30.12+30.15+20.20+20.35 =2.45Ch10-24Ch10-2510.3 Tree TraversalWe need procedures for visiting each vertex of an orderedrooted tree to access data.Universal Address SystemsLabel vertices:1.root 0,its k children 1,2,k(from left to right)2.For each vertex v at level n with label A,its r children A.1,A.2,A.r(from left to right).We can totally order the vertices using the lexicographic ordering of their labels in the universal address system.x1.x2.xn y1.y2.ym if there is an i,0 i n,with x1=y1,x2=y2,xi-1=yi-1,and xiyi;or if nm and xi=yi for i=1,2,n.Ch10-26Example 1The lexicographic ordering is:0 11.1 1.2 1.3 2 3 3.1 3.1.1 3.1.2 3.1.2.1 3.1.2.2 3.1.2.3 3.1.2.4 3.1.3 3.2 4 4.1 5 5.1 5.1.1 5.2 5.3Exercise:2Ch10-27Traversal AlgorithmsPreorder traversal Ch10-28Example 2.In which order does a preorder traversal visit the vertices in the ordered rooted tree T shown below?Sol:Ch10-29Inorder traversalCh10-30Example 3.In which order does an inorder traversal visit the vertices in the ordered rooted tree T shown below?Sol:Ch10-31Postorder traversalCh10-32Example 4.In which order does a postorder traversal visit the vertices in the ordered rooted tree T shown below?Sol:Ch10-33Preorder:a,b,d,h,e,i,j,c,f,g,kInorder:h,d,b,i,e,j,a,f,c,k,gPostorder:h,d,i,j,e,b,f,k,g,c,aCh10-34Procedure preorder(T:ordered rooted tree)r:=root of Tlist rfor each child c of r from left to rightbegin T(c):=subtree with c as its root preorder(T(c)end ALGORITHM 1(PREORDER TRAVERSAL)Ch10-35Procedure inorder(T:ordered rooted tree)r:=root of TIf r is a leaf then list relsebegin l:=first child of r from left to right T(l):=subtree with l as its root inorder(T(l)list r for each child c of r except for l from left to right T(c):=subtree with c as its root inorder(T(c)end ALGORITHM 2(INORDER TRAVERSAL)Ch10-36Procedure postorder(T:ordered rooted tree)r:=root of Tfor each child c of r from left to rightbegin T(c):=subtree with c as its root postorder(T(c)end list rALGORITHM 3(POSTORDER TRAVERSAL)Exercise:8Ch10-37Infix,Prefix,and Postfix NotationWe can represent complicated expressions,such as compound propositions,combinations of sets,and arithmetic expressions using ordered rooted trees.Example 1 Find the ordered rooted tree for (x+y)2)+(x-4)/3).Sol.leaf:variableinternal vertex:operation on its left and right subtrees Ch10-38The following binary trees represent the expressions:(x+y)/(x+3),(x+(y/x)+3,x+(y/(x+3).All their inorder traversals lead to x+y/x+3 ambiguous need parenthesesInfix form:An expression obtained when we traverse its rooted tree with inorder.Prefix form:by preorder.(also named Polish notation)Postfix form:by postorder.(reverse Polish notation)Ch10-39Sol.x y+2 x 4-3/+Example 6 What is the prefix form for(x+y)2)+(x-4)/3)?Example 8 What is the postfix form of the expression (x+y)2)+(x-4)/3)?Sol.+x y 2/-x 4 3Note.An expression in prefix form or postfix form is unambiguous,so no parentheses are needed.Ch10-40Example 7 What is the value of the prefix expression+-*2 3 5/2 3 4?Sol.Ch10-41Example 9 What is the value of the postfix expression7 2 3*-4 9 3/+?Sol.Ch10-42Example 10 Find the ordered rooted tree representing thecompound proposition(pq)(pq).Then use thisrooted tree to find the prefix,postfix,and infix forms of thisexpression.Sol.prefix:p q p q postfix:p q p q infix:(pq)(p)(q)Exercise:17,23,24Ch10-4310.4 Spanning TreesDef.Let G be a simple graph.A spanning tree of G is a subgraph of G that is a tree containing every vertex of G.IntroductionExample 1 Find a spanning tree of G.Sol.Remove an edge from any circuit.(repeat until no circuit exists)Ch10-44Four spanning trees of G:Ch10-45Exercise:1,8,11Thm 1 A simple graph is connected if and only if it hasa spanning tree.Exercise:24,25Example 3 Use depth-first search to find a spanning treefor the graph.Sol.(arbitrarily start with the vertex f)Ch10-46Depth-First Search(DFS)Ch10-47Example 4 The edges selected by DFS of a graph are called tree edges.All other edges of the graph must connect a vertexto an ancestor or descendant of this vertex in the tree.These edges are called back edges.The tree edges(red)and back edges(black)Procedure DFS(G:connected graph with vertices v1,v2,vn)T:=tree consisting only of the vertex v1visit(v1)procedure visit(v:vertex of G)for each vertex w adjacent to v and not yet in Tbegin add vertex w and edge v,w to T visit(w)endAlgorithm 1(Depth-First Search)Ch10-48Exercise:13Example 5 Use breadth-first search to find a spanning treefor the graph.Sol.(arbitrarily start with the vertex e)Ch10-49Breadth-First Search(BFS)Procedure BFS(G:connected graph with vertices v1,v2,vn)T:=tree consisting only of vertex v1L:=empty listput v1 in the list L of unprocessed verticeswhile L is not emptybegin remove the first vertex v from L for each neighbor w of v if w is not in L and not in T then begin add w to the end of the list L add w and edge v,w to T endendALGORITHM 2(BREADTH-FIRST SEARCH)Ch10-50Exercise:16There are problems that can be solved only by performing anexhaustive search of all possible solutions.Ch10-51Backtracking ApplicationsDecision tree:each internal vertex represents a decision,and each leaf is a possible solution.To find a solution via backtracking:first make a sequence of decisions from root to leaf in an attempt to reach a solution.Once it is clear that no solution can be found by any further sequence of decisions,backtrack to the parent of the current vertex and work toward a solution with another series of decisionsCh10-52Example 6(Graph Colorings)How can backtracking beused to decide whether the following graph can be coloredusing 3 colors?Sol.Ch10-53Example 7(The n-Queens Problem)The n-queens problem asks how n queens can be placed on an nn chessboard so that no two queens can attack on another.How can backtracking be used to solve then-queens problem.Sol.n=4impossibleCh10-54Example 8(Sum of Subsets)Give a set S of positive integers x1,x2,xn,find a subsetof S that has M as its sum.How can backtracking be used to solve this problem.Sol.S=31,27,15,11,7,5 M=39Exercise:30Ch10-55Depth-First Search in Directed GraphsExample 9 What is the output of DFS given the graph G?Sol.Ch10-5610.5 Minimum Spanning TreesG:connected weighted graph(each edge has an weight 0)Def.minimum spanning tree of G:a spanning tree of G with smallest sum of weights of its edges.Algorithms for Minimum Spanning TreesProcedure Prim(G:connected weighted undirected graph with n vertices)T:=a minimum-weight edgefor i:=1 to n-2begin e:=an edge of minimum weight incident to a vertex in T and not forming a simple circuit in T if added to T T:=T with e addedend T is a minimum spanning tree of GAlgorithm 1(Prims Algorithm)Ch10-57Example 2 Use Prims algorithm to find a minimum spanning tree of G.Sol.Exercise:3Ch10-58Procedure Kruskal(G:connected weighted undirected graph with n vertices)T:=empty graphfor i:=1 to n-1begin e:=any edge in G with smallest weight that does not form a simple circuit when added to T T:=T with e addedend T is a minimum spanning tree of GAlgorithm 2(Kruskal Algorithm)Ch10-59Example 3 Use Kruskalalgorithm to find a minimum spanning tree of G.Sol.Exercise:7
展开阅读全文