treenode.cpp

数据结构c++-书的一些源代码

#include <iostream.h>
#include <stdlib.h>
#include "lnkqueue.h"
#include <math.h>
#include <conio.h>

template <class T>
class TreeNode
{
 private:
  TreeNode<T>* left;
  TreeNode<T>* right;
 public:
  T data;
  TreeNode(const T& item,TreeNode<T> *lptr=NULL,TreeNode<T> *rptr=NULL);
  TreeNode<T>* Left(void) const;
  TreeNode<T>* Right(void) const;
 // friend  class BinSTree<T>;
};

//treenode.cpp
template <class T>
TreeNode<T>::TreeNode(const T& item,TreeNode<T> *lptr,TreeNode<T> *rptr)
{
 data=item;
 left=lptr;
 right=rptr;
}
template <class T>
TreeNode<T>* TreeNode<T>::Left(void) const
{
 return left;
}
template <class T>
TreeNode<T>* TreeNode<T>::Right(void) const
{
 return right;
}

//treelib.cpp
template <class T>
TreeNode<T> *GetTreeNode(T item,TreeNode<T> *lptr=NULL,TreeNode<T> *rptr=NULL)
{
 TreeNode<T> *p;
 p=new TreeNode<T> (item,lptr,rptr);
 if(p==NULL)
 {
  cerr<<"Memory allocation failure!\n";
  exit(1);
 }
 return p;
}
template <class T>
void FreeTreeNode(TreeNode<T> *p)
{
 delete p;
}
void MakeCharTree(TreeNode<char>*  &root,int n)
{
 TreeNode<char> *a,*b,*c,*d,*e,*f,*g,*h,*i,*p=NULL;
 if(n==0)
 {
  d=GetTreeNode('D');
  b=GetTreeNode('B',p,d);
  e=GetTreeNode('E');
  c=GetTreeNode('C',e,p);
  root=GetTreeNode('A',b,c);
  return;    
 }
 if(n==1)
 {
  d=GetTreeNode('D');
  g=GetTreeNode('G');
  e=GetTreeNode('E',g,p);
  b=GetTreeNode('B',d,e);
  h=GetTreeNode('H');
  i=GetTreeNode('I');
  f=GetTreeNode('F',h,i);
  c=GetTreeNode('C',p,f);
  root=GetTreeNode('A',b,c);
  return;
 }
 if(n==2)
 {
  g=GetTreeNode('G');
  d=GetTreeNode('D',p,g);
  b=GetTreeNode('B',d,p);
  h=GetTreeNode('H');
  i=GetTreeNode('I');
  e=GetTreeNode('E',h,i);
  f=GetTreeNode('F');
  c=GetTreeNode('C',e,f);
  root=GetTreeNode('A',b,c);
  return;
 }
}

void Printchar(char item)
{
 cout<<item<<" ";
 return;
}
template <class T>
void Preorder(TreeNode<T> *t,void visit(T item))
{
 if(t!=NULL)
 {
  visit(t->data);
  Preorder(t->Left(),visit);
  Preorder(t->Right(),visit);
 }
}

template <class T>
void Inorder(TreeNode<T> *t,void visit(T item))
{
 if(t!=NULL)
 {
  Inorder(t->Left(),visit);
  visit(t->data);
  Inorder(t->Right(),visit);
 }
}
template <class T>
void Postorder(TreeNode<T> *t,void visit(T item))
{
 if(t!=NULL)
 {
  Postorder(t->Left(),visit);
  Postorder(t->Right(),visit);
  visit(t->data);
 }
}
template <class T>
void LevelScan(TreeNode<T> *t,void visit(T item))
{
 Queue<TreeNode<T>*> q;
 TreeNode<T> *p;
 q.QInsert(t);
 while(!q.QEmpty())
 {
  p=q.QDelete();
  visit(p->data);
  if(p->Left()!=NULL)
    q.QInsert(p->Left());
  if(p->Right()!=NULL)
    q.QInsert(p->Right());
  }
}


template <class T>
void CountLeaf(TreeNode<T> *t,int& count)
{
 if(t!=NULL)
 {
  CountLeaf(t->Left(),count);
  CountLeaf(t->Right(),count);
  if(t->Left()==NULL && t->Right()==NULL)
  count++;
 }
}
template <class T>
int Depth(TreeNode<T> *t)
{
 int depthleft,depthright,depthval;
 if(t==NULL)
  depthval=-1;
 else
 {
  depthleft=Depth(t->Left());
  depthright=Depth(t->Right());
  depthval=1+(depthleft>depthright ? depthleft:depthright);
 }
 return depthval;
}
const indentunit=6;
void IndentBlanks(int num)
{
 for(int i=0;i<num;i++)
  cout<<" ";
}
 
template <class T>
void PrintTree(TreeNode<T> *t,int level)
{
 if(t!=NULL)
 {
  PrintTree(t->Right(),level+1);
  if(level!=0)
  {
   IndentBlanks(indentunit*(level-1));
   cout<<"  ----";
  }
  cout<<t->data<<endl;
  PrintTree(t->Left(),level+1);
 }
}
struct Info
 {
  int xIndent,yLevel;
 };

template <class T>
void PrintVTree(TreeNode<T> *t,int dataWidth,int screenWidth)
{
 
 Queue<TreeNode<T> *> Q;
 Queue<Info> QI;
 TreeNode<T> *p;
 Info    s,s1,s2;
 int offset,level,len;
                                
 Q.QInsert(t);
 s.xIndent=screenWidth/dataWidth;
 s.yLevel=0;
 QI.QInsert(s);
 level=-1;
 while(!Q.QEmpty() && !QI.QEmpty())
 {
	 s2=s; //new add
	 p=Q.QDelete();
	 s=QI.QDelete();

	 //  if(level==0)
  //  len=screenWidth/2;
  //else
    //len=screenWidth/pow(2,level);

  if(s.yLevel!=level)
  {
   cout<<"\n\nLevel "<<s.yLevel;
   level=s.yLevel;
   IndentBlanks(s.xIndent-1);
  }
  else
   IndentBlanks(s.xIndent-s2.xIndent);   //new modify

  cout<<p->data;
  if(p->Left()!=NULL)
  {
   Q.QInsert(p->Left());
   s1.yLevel=s.yLevel+1;
   offset=screenWidth/pow(dataWidth,s1.yLevel+1);
   s1.xIndent=s.xIndent-offset;
   QI.QInsert(s1);
  }
  if(p->Right()!=NULL)  
  {
   Q.QInsert(p->Right());
   s1.yLevel=s.yLevel+1;
   offset=screenWidth/pow(dataWidth,s1.yLevel+1);
   s1.xIndent=s.xIndent+offset;
   QI.QInsert(s1);
  }
 }
}

//node.cpp, link.cpp, linkqueue.cpp

//node.cpp
template <class T>
Node<T>::Node(const T& item,Node<T>* ptrnext):next(ptrnext),data(item)
{}
template <class T>
void Node<T>::InsertAfter(Node<T> *p)
{
 p->next=next;
 next=p;
}
template <class T>
Node<T>* Node<T>::DeleteAfter(void)
{
 Node<T> *tempPtr=next;
 if(next==NULL)
    return NULL;
 next=tempPtr->next;
 return tempPtr;
}
template <class T>
Node<T>* Node<T>:: NextNode(void) const
{
 return next;
}


//link.cpp
template <class T>
Node<T>* LinkedList<T>::GetNode(const T& item,Node<T>* ptrNext)
{
 Node<T> *newNode;
 newNode=new Node<T>(item,ptrNext);
 if (newNode==NULL)
 {
  cerr<<"Memory allocation failure!"<<endl;
  exit(1);
 }
 return newNode;
}
template <class T>
void LinkedList<T>::FreeNode(Node<T> *p)
{
 delete p;
}
template <class T>
void LinkedList<T>::CopyList(const LinkedList<T>& L)
{
 Node<T> *p=L.front;
 while (p!=NULL)
 {
  InsertRear(p->data);
  p=p->NextNode();
 }
 if(position==-1)
   return;
 prevPtr=NULL;
 currPtr=front;
 for(int pos=0;pos!=position;pos++)
 {
  prevPtr=currPtr;
  currPtr=currPtr->NextNode();
 }
}
template <class T>
LinkedList<T>::LinkedList(void):front(NULL),rear(NULL),
       prevPtr(NULL),currPtr(NULL),size(0),position(-1)
{}
template <class T>
LinkedList<T>::LinkedList(const LinkedList<T>& L)
{
 if(size!=0)
   return;
 CopyList(L);
}
template <class T>
LinkedList<T>::~LinkedList(void)
{
 ClearList();
}
template <class T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& L)
{
 ClearList();
 CopyList(L);
 return *this;
}
template <class T>
int LinkedList<T>::ListSize(void) const
{
  return size;
}
template <class T>
int LinkedList<T>::ListEmpty(void) const
{
 return (size==0);
}
template <class T>
void LinkedList<T>::Reset(int pos)
{
 int startPos;
 if(front==NULL)
   return;
 if(pos<0 ||pos>size-1)
 {
  cerr<<"Reset Invalid list position: "<<pos<<endl;
  return;
 }
 if(pos==0)
 {
  prevPtr=NULL;
  currPtr=front;
  position=0;
 }
 else
 {
  currPtr=front->NextNode();
  prevPtr=front;
  startPos=1;
  for(position=startPos;position!=pos;position++)
  {
   prevPtr=currPtr;
   currPtr=currPtr->NextNode();
  }
 }
}
template <class T>
void LinkedList<T>::Next(void)
{
 if(currPtr!=NULL)
 {
  prevPtr=currPtr;
  currPtr=currPtr->NextNode();
  position++;
 }
}
template <class T>
int LinkedList<T>::EndOfList(void) const
{
 return (currPtr==rear->next);
}
template <class T>
int LinkedList<T>::CurrentPosition(void) const
{
 return position;
}
template <class T>
void LinkedList<T>::InsertFront(const T& item)
{
 Node<T> *newNode;
 newNode=GetNode(item,front);
 if(rear==NULL)
  rear=newNode;

  currPtr=newNode;
  prevPtr=NULL;
  front=newNode;
  size++;
  position=0;
 }

template <class T>
void LinkedList<T>::InsertRear(const T& item)
{
 Node<T> *newNode;
 if(front==NULL)
   InsertFront(item);
 else
 {
  newNode=GetNode(item);
  rear->next=newNode;
  prevPtr=rear;
  rear=newNode;
  currPtr=rear;
  size++;
  position=size-1;
 }
}
template <class T>
void LinkedList<T>::InsertAt(const T& item)
{
 Node<T> *newNode;
 if(prevPtr==NULL)
 {
  newNode=GetNode(item,front);
  front=newNode;
 }
 else
 {
  newNode=GetNode(item);
  prevPtr->InsertAfter(newNode);
 }
 if (prevPtr==rear)
 {
  rear= newNode;
  position=size;
 }
 currPtr=newNode;
 size++;
}

template <class T>
void LinkedList<T>::InsertAfter(const T& item)
{
 Node<T> *newNode;
 if(front==NULL)
 {
  InsertFront(item);
  return;
 }
 if(currPtr==rear && currPtr!=NULL)
 {
  InsertRear(item);
  return;
 }
 prevPtr=currPtr;
 currPtr=currPtr->NextNode();
 position++;
 size++;
}
template <class T>
T LinkedList<T>::DeleteFront(void)
{
 Node<T> *temp;
 T data1;
 if(currPtr==NULL)
 {
  cerr<<"Invalid deletion! "<<endl;
  exit(1);
 }
 if(front==rear)
 {
   front=NULL;
   rear=NULL;
   data1=currPtr->data;
   currPtr=NULL;
   size=0;
   position=-1;
   return data1;
 }
  temp=front;
  front=front->NextNode();
  prevPtr=NULL;
  currPtr=temp->NextNode();
  position=0;
  data1=temp->data; 
  FreeNode(temp);
  size--;
  return data1;
}
template <class T>
void LinkedList<T>::DeleteAt(void)
{
 Node<T> *p;
 if(currPtr==NULL)
 {
  cerr<<"Invalid deletion! "<<endl;
  exit(1);
 }
 if (prevPtr==NULL)
 {
  p=front;
  front=front->NextNode();
 }
 else
 p=prevPtr->DeleteAfter();
 if(p==rear)
 {
  rear=prevPtr;
  position--;
 }
 currPtr=p->NextNode();
 FreeNode(p);
 size--;
}
template <class T>
T& LinkedList<T>::Data(void)
{
 return currPtr->data;
}
template <class T>
void LinkedList<T>::ClearList(void)
{
 Node<T> *currPosition,*nextPosition;
 currPosition=front;
 while(currPosition!=NULL)
 {
  nextPosition=currPosition->NextNode();
  FreeNode(currPosition);
  currPosition=nextPosition;
 }
 front=rear=NULL;
 prevPtr=currPtr=NULL;
 size=0;
 position=-1;
}

template <class T>
void FindMax(LinkedList<T> &L)
{
 if(L.ListEmpty())
 {
  cerr<<"Findmax: list empty!"<<endl;
  return;
 }
 L.Reset();
 T max=L.Data();
 int maxloc=0;
 for(L.Next();!L.EndOfList();L.Next())
  if(L.Data()>max)
  {
   max=L.Data();
   maxloc=L.CurrentPosition();
  }
 L.Reset(maxloc);
}

template <class T>
void PrintList(LinkedList<T>& L)
{
 int pos1;
 pos1=L.CurrentPosition();
 for(L.Reset();!L.EndOfList();L.Next())
   cout<<L.Data()<<" ";
 cout<<endl;
 L.Reset(pos1);
 }

//lnkqueue.cpp

template <class T>
Queue<T>::Queue(void)
{}
template <class T>
void Queue<T>::QInsert(const T& elt)
{
 queueList.InsertRear(elt);
}
template <class T>
T Queue<T>::QDelete(void)
{
 if(queueList.ListEmpty())
 {
  cerr<<"Calling QDelete for an empty queue! "<<endl;
  exit(1);
 }
 return queueList.DeleteFront();
 }
template <class T>
T Queue<T>::QFront(void)
{
 if(queueList.ListEmpty())
 {
  cerr<<"Calling QFront for an empty queue!"<<endl;
  exit(1);
 }
 queueList.Reset();
 return queueList.Data();
}
template <class T>
T Queue<T>::QRear(void)
{
 int len;
 len=queueList.ListSize();
 queueList.Reset(len-1);
 return queueList.Data();
}

template <class T>
int Queue<T>::QLength(void) const
{
 return queueList.ListSize();
}
template <class T>
int Queue<T>::QEmpty(void) const
{
 return (!queueList.ListSize());
}
template <class T>
void Queue<T>::QClear(void)
{
 queueList.ClearList();
}
template <class T>
LinkedList<T>& Queue<T>::Getqulst(void)
{
 return queueList;
}

void main(void)
{
 
 TreeNode<int> *root,*lchild,*rchild,*p;
 lchild=new TreeNode<int>(20);
 rchild=new TreeNode<int>(30);
 root=new TreeNode<int>(10,lchild,rchild);
 PrintVTree(root,2,64);
 cout<<endl;
 cout<<"root is: "<<root->data<<endl;
 p=root->Left();
 cout<<"left child is: "<<p->data<<endl;
 p=root->Right();
 cout<<"right child is: "<<p->data<<endl;

 TreeNode<char> *root2,*root1;
 MakeCharTree(root2,2);
 PrintVTree(root2,2,64);
 cout<<"\nInorder tree 2 : "<<endl;
 Inorder(root2,Printchar);
 cout<<"\nPreorder tree 2 :"<<endl;
 Preorder(root2,Printchar);
 cout<<"\nPostorder tree 2 :"<<endl;
 Postorder(root2,Printchar);
 cout<<"\nLevel scan:"<<endl;
 LevelScan(root2,Printchar);

 getch();

 int leafCount=0;
 CountLeaf(root2,leafCount);
 cout<<"\nNumber of leaf nodes is: "<<leafCount<<endl;
 cout<<"\nThe depth of the tree is: "<<Depth(root2)<<endl;

 int level=0;
 cout<<"\nPrint vertical tree 2 : "<<endl;
 PrintTree(root2,level);
 getch();
 
 cout<<"\nPrint horizontal tree 2 : "<<endl;
 PrintVTree(root2,2,64);
 cout<<"\n\nPrint horizontal tree 0 : "<<endl;
 MakeCharTree(root1,1);
 PrintVTree(root1,2,64);
 getch();
}