數(shù)據(jù)結(jié)構(gòu)lecture13trees4

1、Introduction to Trees (4)6Pla n to give the lecture by clear expla nati on with particular examples.Make use of all kinds of in strume nts especially multimedia.To attract the atte nti on of stude nts through putt ing questi ons and other in teractive method.Try to lead the stude nts their way of th

2、i nking.Course Layout1. review Tree(1、2、3)2.newcontent1. concept and structure of general tree2. change general tree to binary tree and change forest to binary tree3. Huffma n tree and Huffma n code2 minu tes18 minu tes25 minu tes43 minu tes1. review the key points and the difficulties3. summary2. q

3、uestions from students2 mi nute3. homeworkContent7-7 GENERAL TREES CONCEPTS AND STRUCTUREA general tree is a tree in which each node can have an un limited outdegree. Each node may have as many childre n as is n ecessary to satisfy its requireme nts. Although gen eral trees have little use in comput

4、er scie nee, they are com monly found in user applicatio ns. For example, the bill of materials discussed on page 268 is an example of a gen eral tree. We therefore n eed to be able toprocess gen eral trees.7-8 CHANGING GENERAL TREE TO BINARY TREEIt is considerably easier to represent binary trees i

5、n programs tha n it is to represe nt gen eral trees. We would therefore like to be able to represent general trees with a binary tree format. The binary tree format can be adopted by cha nging the meaning of the left and right pointers. In a general tree, we can use two relati on ships: pare nt to c

6、hild and sibli ng to sibli ng. Using these two relati on ships, we can represe nt any gen eral tree as a binary tree.Con sider the tree show n in Figure 7-17. To change it to a binary tree, we first identify the branch from the pare nt to its first or leftmost child. These bran ches from each pare n

7、t become left pointers in the binary tree. TheyB(a) The general treeG(匸)Connect siblings(b) Identify leftmost child rent(d) Delete uinneeded branches(e) The resulting binary treeare show n in Figure 7-17(b). Then, we connect sibli ngs, start ing with the leftmost child, using a branch for each sibli

8、ng to its right sibling. These branches, shown in Figure 7-17(c), are the right poi nters in the bi nary tree. The third and last step in the conversion process is to remove all unn eeded bran ches from the pare nt to its childre n. The result ing binary tree is show n in Figure7-17(d). Although thi

9、s is a valid tree structure, it does not have a traditi onal bi nary tree format. We therefore redraw it as show n in Figure 7-17(e).Insertions into General TreesTo insert a node into a gen eral tree, the user must supply the pare nt of the no de. Give n the pare nt, three different rules may be use

10、d: (1) first In-first out (FIFO) insertion, (2) last in-first out (LIFO) in serti on, and (3) key-seque need In serti on.FLFO InsertionWhen using FIFO insertion , we in sert the no des at the end of the sibli ng list, much as we in sert a new node at the rear of a queue. When the list is the n proce

11、ssed, the sibli ngs will be processed In FIFO order. FIFO order is used when the application requires that the data be processed in the order in which they were in put. Figure 7-18 shows two FIFO Insertions into a gen eral tree. Node N has bee n in serted into level 1 after node F, and node M has be

12、e n in serted at level 2 after node D.(a) Befoire insertkm(b) After InwrtionLIFO InsertionTo process sibling lists in the opposite order in which they were created, we use LIFO Insertion . LIFO insertion places the new node at the beg inning of the sibli ng list. It is the equivale nt of a stack. Fi

13、gure 7-19 shows the insertion points for a LI FO tree.Key-Sequenced InsertionPerhaps the most com mon of the in serti on rules, key-sequenced Insertion places the new node in key seque nee among the sibli ng no des. The logic for inserting in key seque nee is similar to that for In serti on into a l

14、in ked list. Start ing at the pare nt sfirst child, we follow the sibli ng (right) poin ters un til we locate the correct insertion point and the n build the links with the predecessors and successors (if an y). Figure 7-20 shows the correct key-sequeneed insertion locations for several differe nt v

15、alues in a gen eral tree.General Tree DeletionsAlthough we cannot develop sta ndard rules for gen eral tree insertions, Deleti ons we can develop sta ndard deleti on rules. The first rule is similar to all other bi nary tree delete rules (see Chapter 8): a node may be deleted only lilt is a leaf. i

16、n the gen eral tree, this means a node cannot be deleted if It has any children: that is, It cannot have a left subtree (It Is okay If it has right subtrees). If the user tries to delete a node that has childre n, the program provides an error message that the node cannot be deleted until its childr

17、en are deleted. It i s then the user s responsibility to first delete any children. As an alternative, the application could be programmed to delete the children fast and then delete the requested no de, if this alter native is used, it should be with a differe nt user opti on, such as purge node an

18、d childre n, and not the simple delete node opti on.When a node is deleted, we must also check for sibli ngs; that is, does the node have a right subtree pointer? If there are siblings, then the logic follows the basic rules for linked lists. If the first node is deleted, the n the pare nt sleft poi

19、n ter must be updated. If any other node is deleted, the n its predecessors right pointer must be update d to point to the deleted node s successor.7-9 HUFFMAN CODEASCII and EBCDIC are fixed-length codes. Each ASCII character consists of 7 bits. Each EBCDIC character consists of 8 bits. Character le

20、ngth does not vary. Although the character E occurs more freque ntly tha n the character Z. both are assig ned the same nu mber of bits in a give n code. This con siste ncy means that every character uses the maximum nu mber of bits.Huffma n code, however, makes character storage more efficie nt. I

21、n Huffma n code, we assig n shorter codes to characters that occur more freque ntly and Ion ger codes to those that occur less freque ntly. For example, E and T, two characters that occur freque ntly in the En glish Ian guage, could be assig ned I bit each. A, 0, R, and N, which also occur freque nt

22、ly but less freque ntly tha n E and T, could be assig ned 2 bits each. S, U, I, D, M, C, and U are the next most freque nt and could be assig ned 3 bits each, and so forth. In a give n piece of text, only some of the characters will require the maximum bit len gth. When used in a n etwork tran smiss

23、i on, the overall len gth of the transmission is shorter if Huffman-encoded characters are transmitted rather than fixed-length en codi ng: Huffma n code is thus a popular data compressi on algorithm.Before we can assig n bit patter ns to each character, we assig n each character a weight based on i

24、ts freque ncy of use. in our example, we assume that the freque ncy of the character E in a text is15% and the freque ncy of the character T is 12%.E=15U=05T=121=04A=10D=040=08M=03R=07N=06S=05C=03G=02K=02Once we have established the weight of each character, we build a tree based on those values. Th

25、e process for build ing this tree is show n in Figures 7-21 through 7-24. It follows three basic steps:1. First we organize the entire character set into a row, ordered according to frequency from highest to lowest (or vice versa). Each character is now a node at the leaf level of a tree.2. Next, we

26、 find the two no des with the smallest comb ined freque ncy weights and join them toform a third no de, result ing in a simple two-level tree. The weight of the new node is the comb ined weights of the orig inal two no des. This no de, one level up from the leaves, is eligible to be comb ined with o

27、ther no des. Remember, the sum of the weights of the two no des chose n must be smaller tha n the comb in ati on of any other possible choices.3. We repeat Step 2 un til all of the no des, on every Level, are comb ined into a sin gle tree.同 1512 IQ DB 07 DE 0505 (Ml 040303 02021512 151210007060505 0

28、4040303O i15121008 1512100807 06 OS 05 151210007 06 &151210OB07D6OS05 0404Figure 7-21 shows the first part of this process. The first row of the figure shows Step 1, with the leaf-level no des represe nti ng the origi nal characters arran ged in desce nding order of value; the n, as expla ined in St

29、ep 2, we locate the two no des with the smallest values and comb ine them. Thisstep is show n in the sec ond row. As you can see, this process results in the creati on of a new node (represented by a solid circle). The frequency value (weight) of this new node is the sum of the weights of the two no

30、 des. In the third row, we comb ine two more no des, and so on.In the sixth row, the no des with the lowest values are found one level up from the characters rather tha n among the characters themselves. We comb ine them into a node two levels up from theleaves.Also In the sixth row, the lowest-valu

31、e node is 08 (0) and the second lowest value is 10 (A). But there are three 10s-one at the leaf level (A), one a level up from the leaves (S-U), and one two levels up from the leaves (M-C-G-K). Which should we choose? We choose whichever of the 10s is adjace nt to the 8. This decisi on keeps the bra

32、nch lines from cross ing and allows us to preserve the legibility of the tree.If none of the higher values are adjace nt to the lower value, we can rearra nge the no des for clarity(see Figure 7-22). I n the figure (third row), we have moved the character T from the left side of the tree to the righ

33、t to combine it with a node on that side. We move the character E for the same reas on.Figure 7-23 shows the rest of the process. As you can see, the completed tree results in a sin gle node at the root level (with a value of 86).Once the tree is complete, we use it to assig n codes to each characte

34、r. First, we assig n a bit value to each branch see Figure 7-24). Start ing from the root (top no de), we assig n 0 to the left branch and I to the right branch and repeat this patter n at each no de. Which branch becomes 0 and which becomes 1 is left to the desig ner-as long as the assig nments are

35、 con siste nt throughout the tree.A character s code is found by starting at the root and following the branches that lead to that character. The code itself is the bit value of each branch on the path taken in sequenee. In our example, for instanee, A 000, G = 11010, and so on. The code for each ch

36、aracter and the freque ncy of the character are show n In Figure 7-24. If you exam ine the codes carefully, you will note that the leadi ng bits of each code are uniq ue; that is, no code is the prefix of any other code because each has bee n obta ined by follow ing a differe nt path from the root.G

37、A = 000O = 001S = 0100U = 0101I = O1WD = 0111E = 100R = 1010N = 1011M = 11000C = 11001G = 11010K = 11011T = 1117-10 SUMMARYA tree consists of a finite set of elements called no des and a fin ite set of directed lines calledbran ches that conn ect the no des.The nu mber of bran ches associated with a

38、 node is the degree of the no de.When the branch is directed toward the no de, it is an in degree bran ch; whe n the branch is directed away front the no de. It is an outdegree bran ch. The sum of In degree and outdegree bran ches Is the degree of the no de.If the tree is not empty, the first node i

39、s called the root, which has the in degree of zero.All no des in the tree, except the root must have an in degree of one.A leaf is a node with an outdegree of zero.An internal node is a node that is n either the root nor a leaf.A node can be a pare nt, a child, or both. Two or more no des with the s

40、ame pare nt are called sibli ngs.A path is a seque nee of no des in which each node Is adjace nt to the n ext one.An an cestor is any node in the path from the root of a give n no de. A desce nden t is any node in all of the paths from a given node to a leaf.The level of a node is its distance from

41、the root.The height of a tree is the level of the leaf in the longest path from the root plus 1; the height of an empty tree is -1.A subtree is any connected structure below the root.A tree can be defined recursively as a set of nodes that either (l)is empty or (2) has a designated node called the r

42、oot from which hierarchically descend zero or more subtrees, which are also frees. A binary tree is a tree in which no node can have more than two children.The minimum and maximum height of a binary tree can be related to the number of nodes:Given the height of a binary tree, the minimum and maximum

43、 number of nodes in the tree can be calculated asThe balance factor of a binary free is the difference in height between its left and right subtrees.A free is balanced if its balance factor is 0 and its subtrees are also balanced; a binary tree Is balanced if the heights of its subtrees differ by no

44、 more than I and its subtrees are also balanced.A complete tree has the maximum number of entries for its height; a tree is complete when the last level is full.A nearly complete tree Is a tree that has the minimum height for its nodes and all nodes in the last level are found on the left.A binary f

45、ree traversal visits each node of the tree once and only once in a predetermined sequence.The two approaches to binary tree traversal are depth first and breadth first.Using the depth-first approach, we traverse a binary tree in six different sequences: however, only three of these sequences are given standard names: preorder inorder. and postorder In the preorder traversal, we process the root firs