Data Structure教学课件（华南理工）Tutorial04 ans.pdfVIP

Data Structure (Semester 1, 2013-2014) Tutorial 04 Prepared by Dr. Patrick Chan Date: November-2013 1. Write a function that takes as input a general tree and returns the number of nodes in that tree. Write your function to use the GenTree and GTNode ADTs of Figure 6.2 (pp. 194). Answer: int gencount(GTNodeElem* subroot) { if (subroot == NULL) return 0 int count = 1; GTNodeElem* temp = subroot-leftmost_child(); while (temp != NULL) { count += gencount(temp); temp = temp-right_sibling(); } return count; } or int gencount(GTNodeElem* subroot) { if (subroot == NULL) return 0 return 1 + gencount(subroot-leftmost_child())+ gencount(subroot-right_sibling()); } Data Structure – Tutorial 4 1 2. Write an algorithm to determine if two general trees are identical. Answer: // Return TRUE iff t1 and t2 are roots of identical // general trees template class Elem bool Compare(GTNodeElem* t1, GTNodeElem* t2) { GTNodeElem *c1, *c2; if (((t1 == NULL) (t2 != NULL)) || ((t2 == NULL) (t1 != NULL))) return false; if ((t1 == NULL) (t2 == NULL)) return true; if (t1-val() != t2-val()) return false; c1 = t1-leftmost_child(); c2 = t2-leftmost_child(); while(!((c1 == NULL) (c2 == NULL))) { if (!Compare(c1, c2)) return false; if (c1 != NULL) c1 = c1-right_sibling(); if (c2 != NULL) c2 = c2-right_sibling(); }} Data Structure – Tutorial 4 2 3. Using the weighted union rule and path compression, show the array for the parent pointer implementation