General Trees
General Tree Node
// General tree node ADTtemplate <class Elem> class GTNode {
public:GTNode(const Elem&); // Constructor
~GTNode(); // DestructorElem value(); // Return value
bool isLeaf(); // TRUE if is a leafGTNode* parent(); // Return parent
GTNode* leftmost_child(); // First childGTNode* right_sibling(); // Right sibling
void setValue(Elem&); // Set valuevoid insert_first(GTNode<Elem>* n);
void insert_next(GTNode<Elem>* n);void remove_first(); // Remove first child
void remove_next(); // Remove sibling};
General Tree Traversal
template <class Elem>void GenTree<Elem>::
printhelp(GTNode<Elem>* subroot) {if (subroot->isLeaf()) cout << "Leaf,";
else cout << "Internal,";cout << subroot->value() << "\n";
for (GTNode<Elem>* 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 bif (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 Implementations (2)
Converting to a Binary Tree
Left child/right sibling representation
essentially stores a binary tree.
Use this process to convert any general tree
to a binary tree.
A forest is a collection of one or more
general trees.
Sequential Implementations (1)
List node values in the order they would be
visited by a preorder traversal.
Saves space,but allows only sequential
access.
Need to retain tree structure for
reconstruction.
Example,For binary trees,us a symbol to
mark null links.
AB/D//CEG///FH//I//
Sequential Implementations (2)
Example,For full binary trees,mark nodes
as leaf or internal.
A’B’/DC’E’G/F’HI
Example,For general trees,mark the end of
each subtree.
RAC)D)E))BF)))