【精品数据结构】GeneralTrees.pptVIP

General Trees General Tree Node // General tree node ADT template class Elem class GTNode { public: GTNode(const Elem); // Constructor ~GTNode(); // Destructor Elem value(); // Return value bool isLeaf(); // TRUE if is a leaf GTNode* parent(); // Return parent GTNode* leftmost_child(); // First child GTNode* right_sibling(); // Right sibling void setValue(Elem); // Set value void insert_first(GTNodeElem* n); void insert_next(GTNodeElem* n); void remove_first(); // Remove first child void remove_next(); // Remove sibling }; General Tree Traversal template class Elem void GenTreeElem:: printhelp(GTNodeElem* subroot) { if (subroot-isLeaf()) cout Leaf: ; else cout Internal: ; cout subroot-value() \n; for (GTNodeElem* temp = subroot-leftmost_child(); temp != NULL; temp = temp-right_sibling()) printhelp(temp); } Parent Pointer Implementation Equivalence Class Problem The parent pointer representation is good for answering: Are two elements in the same tree? // Return TRUE if nodes in different trees bool Gentree::differ(int a, int b) { int root1 = FIND(a); // Find root for a int root2 = FIND(b); // Find root for b return root1 != root2; // Compare roots } Union/Find void Gentree::UNION(int a, int b) { int root1 = FIND(a); // Find root for a int root2 = FIND(b); // Find root for b if (root1 != root2) array[root2] = root1; } int Gentree::FIND(int curr) const { while (array[curr]!=ROOT) curr = array[curr]; return curr; // At root } Want to keep the depth small. Weighted union rule: Join the tree with fewer nodes to the tree with more nodes. Equiv Class Processing (1) Equiv Class Processing (2) Path Compression int Gentree::FIND(int curr) const { if (array[curr] == ROOT) return curr; return array[curr] = FIND(array[curr]); } Lists of Children Leftmost Child/Right Sibling (1) Leftmost Child/Right Sibling (2) Linked Implementations (1) Linked Implementati