wex11_28.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#pragma hdrstop

// tree node class maintaining parent pointer
template <class T>
class PTreeNode
{
   private:
      // points to the left and right children of the node and
      // to the parent
      PTreeNode<T> *left;
      PTreeNode<T> *right;
      PTreeNode<T> *parent;

   public:
      // public member allowing the client to update its value
      T data;
   
      // constructor
      PTreeNode (const T& item, PTreeNode<T> *lptr = NULL,
                PTreeNode<T> *rptr = NULL, PTreeNode<T> *parnt = NULL);
   
      // access methods for the pointer fields
      PTreeNode<T>* & Left(void);
      PTreeNode<T>* & Right(void);
      PTreeNode<T>* & Parent(void);
};

// constructor. initialize the data and pointer fields.
template <class T>
PTreeNode<T>::PTreeNode (const T& item, PTreeNode<T> *lptr,
    PTreeNode<T> *rptr,PTreeNode<T> *parnt):
         data(item), left(lptr), right(rptr), parent(parnt)
{}

// method Left allows the user to reference the left child on either
// side of an assignment statement
template <class T>
PTreeNode<T>* &PTreeNode<T>::Left(void)
{
   // return the private member value left
   return left;
}

// method Right allows the user to reference the right child on either
// side of an assignment statement
template <class T>
PTreeNode<T>* &PTreeNode<T>::Right(void)
{
   // return the private member value right
   return right;
}

// method Parent allows the user to reference the parent on either
// side of an assignment statement
template <class T>
PTreeNode<T>* &PTreeNode<T>::Parent(void)
{
   // return the private member value parent
   return parent;
}

// insert item into a binary search tree made from
// PTreeNode objects
template <class T>			
void Insert(PTreeNode<T> * & t,T item)
{
    // t is current node in traversal, parent the previous node
    PTreeNode<T> *parent = NULL, *newNode;

    // terminate on on empty subtree
    while(t != NULL)
    {
        // update the parent pointer. then go left or right
        parent = t;
        if (item < t->data)
            t = t->Left();
        else 
            t = t->Right();
    }
    
    // create the new leaf node with parent pointer
    newNode = new PTreeNode<char>(item,NULL,NULL,parent);
    
    // if parent is NULL, insert as root node
    if (parent == NULL)
        t = newNode;
        
    // if item < parent->data, insert as left child        
    else if (item < parent->data)                   
        parent->Left() = newNode;
        
    else
        // if item >= parent->data, insert as right child     
        parent->Right() = newNode;
        
}

// print the data for the chain of nodes that leads
// from node to the root
template <class T>
void PrintAncestors(PTreeNode<T> *t)
{
	// print t->data and move upward by using
	// the Parent method. stop when the root
	// is found (node whose parent is NULL)
	while (t != NULL)
	{
		cout << t->data << "  ";
		t = t->Parent();
	}
	cout << endl;
}

// traverse tree inorder and save node addresses in a
template <class T>
void PInorder(PTreeNode<T> *t, PTreeNode<T> *a[], int& i)
{
	if (t != NULL)
	{
		PInorder(t->Left(), a, i);
		a[i++] = t;
		PInorder(t->Right(), a, i);
	}
}

// build Tree_2 using PTreeNode objects
void MakeTree(PTreeNode<char>* &root)
{
   // 9 TreeNode pointers; points to the 9 items in the tree 
   PTreeNode<char> *a, *b, *c, *d, *e, *f, *g, *h, *i;

   g = new PTreeNode<char>('G');
   h = new PTreeNode<char>('H');
   i = new PTreeNode<char>('I');
   d = new PTreeNode<char>('D',(PTreeNode<char> *)NULL, g);
   e = new PTreeNode<char>('E',h, i);
   f = new PTreeNode<char>('F');
   b = new PTreeNode<char>('B',d, (PTreeNode<char> *)NULL);
   c = new PTreeNode<char>('C',e, f);
   a = new PTreeNode<char>('A',b, c,(PTreeNode<char> *)NULL);
   g->Parent() = d;
   d->Parent() = b;
   b->Parent() = a;
   c->Parent() = a;
   e->Parent() = c;
   f->Parent() = c;
   h->Parent() = e;
   i->Parent() = e;
   root = a;
}

void main(void)
{
	PTreeNode<char> *root, *a[9];
	int i = 0;
	
	MakeTree(root);
	// a will contain address of each node in the tree
	PInorder(root,a,i);
	
	// find ancestors of each node in the tree
	for(i=0;i < 9;i++)
	{
		cout << a[i]->data << " to root: ";
		PrintAncestors(a[i]);
	}
}

/*
<Run>

D to root: D  B  A
G to root: G  D  B  A
B to root: B  A
A to root: A
H to root: H  E  C  A
E to root: E  C  A
I to root: I  E  C  A
C to root: C  A
F to root: F  C  A
*/