The storage structure of a tree can adopt the parent representation, that is, the parent pointer array representation. Try to give the corresponding class definition. Each tree node contains two membe

  The storage structure of a tree can be expressed by parents , That is, the parent pointer array representation . Try to give the corresponding class definition . among , Each tree node contains two members ： Data fields data And parental pointer parent; A tree has an array of tree nodes NodeList[MaxSize],MaxSize Indicates the maximum number of nodes in the array ,size Is the number of current nodes ,current Indicates the location of the nearest operation node , The current pointer .

 

【 answer 】

Here are the parents （ Parent pointer ） Represents the tree and tree node class definitions .

template <class Type> class Tree;
template <class Type> class TreeNode {			// Tree node class 
friend class Tree<Type>;
private:
   Type data; 								// Node data 
   int parent;		 						// Parent pointer  ( Denote by node subscript )
};
 
template <class Type> class Tree {				// Tree class 
private:
   TreeNode<Type> *NodeList;      				// Node table 
   int Size, MaxSize;               				// The current number of nodes and the maximum number of nodes in the node table 
   int current;                    				// Current node pointer 
public:
   Tree ( int sz);                            		// Constructors 
   ~Tree ( ) { delete [ ] NedeList; }             		// Destructor 
   int Root ( );                              	// Search the root node 
   void BuildRoot ( const Type& value );       		// Establish the root node 
   int FirstChild ( );                         		// Search the first child of the current node 
   int NextSibling ( );                        		// Search the next brother of the current node 
   int Parent ( );                           		// Search the parent node of the current node 
   Type getData ( );                         		// Retrieve the value of the current node data member 
   void setData ( const Type& value );				// Modify the value of the current node data member 
   int InsertChild ( const Type& value );       		// Insert a new child under the current node 
   int DeleteChild ( int i );                   		// Delete the... Of the current node i A child 
   void DeleteSubTree ( );                    		// Delete the subtree with the current node as the root 
   int IsEmpty ( ) { return Size == 0; }         		// Judge whether the tree is empty 
};

template <class Type> Tree<Type> :: Tree ( int sz ) : MaxSize (sz) {
// Constructors ,  Create a parent pointer array and initialize .
   NodeList = new TreeNode[MaxSize];      		// Create node table 
   Size = 0;  current = -1;
}

template <class Type> int Tree<Type> :: Root ( ) {
// Search the root node 
   if ( Size != 0 ) { current = 0;  return 1; }
   current = -1;  return 0;
}

template <class Type> int Tree<Type> :: BuildRoot ( const Type& value ) {
// Establish the root node of the tree . The root of the tree is NodeList[0].
   NodeList[0].data = value;  NodeList[0].parent = -1;    // Root node 
   Size = 1;  current = 0;
}

template <class Type> int Tree<Type> :: FirstChild ( ) {
// After the function is executed, the current pointer points to the first child node of the current node and returns 1,  If there were no children ,  Then the current pointer is -1
// And the function returns 0.
   int i = current+1;                         		// Start looking for children from your current location 
   while ( i < Size && NodeList[i].parent != current ) i++;
   if ( i < Size ) { current = i;  return 1; }  	    		// The current pointer points to the child node and returns 1
   current = -1;  return 0;
}

template <class Type> int Tree<Type> :: NextSibling ( ) {
// After the function is executed, the current pointer points to the next sibling node of the current node and returns 1,  If there were no brothers ,  Then the current pointer is -1
// And the function returns 0.
   int i = current+1;                         		// Find the next brother from the current position 
   while ( i < Size && NodeList[i].parent != NodeList[current].parent ) i++;
   if ( i < Size ) { current = i;  return 1; }      		// The current pointer refers to the next sibling node ,  And back to 1
   current = -1;  return 0;
}	

template <class Type> int Tree<Type> :: Parent ( ) {
// After the function is executed, the current pointer points to the parent node of the current node and returns 1,  If there is no parent node ,  Then the current pointer is  -1 And letter 
// Number return 0.
   if ( current < Size && current > 0 ) { current = NodeList[current].parent;  return 1; }
   current = -1;  return 0;
}

template <class Type> Type Tree<Type> :: getData ( ) {
// Function returns the value stored in the current node .
   if ( current != -1 ) return NodeList[current].data;
   else return NULL;
}

template <class Type> int Tree<Type> :: InsertChild ( const Type& value ) {
// Insert data under the current node in the tree as value My new child node ,  If parent pointer array is full ,  You can't insert ,  function 
// return 0;  If the insertion is successful ,  Then the function returns 1.
   if ( Size < MaxSize ) {
 NodeList[++Size].data = value;        		// Value to children 
 NodeList[Size].parent = current;    			// Chain into parent node chain 
 return 1;
   }
   else return 0;
}

template <class Type> int Tree<Type> :: DeleteChild ( int i ) {
// Delete the... Under the current node in the tree i Children and all their descendants ,  If the node's i Child nodes do not exist , 
// Then the function returns 0;  If the deletion is successful ,  Then the function returns 1.
   int p = current, k = FirstChild ( );         		// Find the current node p The first child of 
   if ( !k ) { current = p;  return 0; }         		// If you don't find ,  The exit 
   int j = 1;
   while ( k && j < i ) { j++;  k = NextSibling ( ); }    // Find the second... Of the current node i A brother 
   if ( !k ) { current = p;  return 0; }         		// Not found 
   DeleteSubTree ( );                      		// find ,  Delete with current Root subtree 
   current = p;  return 1;
}

template <class Type> void Tree<Type> :: DeleteSubTree ( ) {
// Delete the subtree with the current node as the root node .
   if ( current != -1 ) {
 int t = current;  k = FirstChild ( );          	// Find the first child of the current node 
 while ( k ) {							// find 
    int p = current;						//p Write down your current child 
    k = NextSibling ( );  int q = current;		//q Write down a child 
    current = p;  DeleteSubTree ( );			// Delete current Root subtree 
    current = q;
 }
 k = t+1;
 while ( k < Size ) {						// modify 
    if ( NodeList[k].parent > t ) NodeList[k].parent--;
    NodeList[k-1].parent = NodeList[k].parent;
    NodeList[k-1].data = NodeList[k].data;
    k++;
 }
 Size--;
   }
}