几个数据结构的知识点的实现,希望大家多提意见.
只写了几个,不全
:)




(1)二叉树
#include "stdafx.h"
#include <iostream.h>
#include<stdlib.h>

template<class T>
class Queue
{
private:
T QList[50];
int front,rear,count;
public:
Queue(void);
void QInsert(const T & item);
T QDelete(void);
void ClearQueue(void);
T QFront(void) const;
int QLength(void) const;
int QEmpty(void) const;
int QFull(void) const;
};

template<class T>
Queue<T>::Queue(void)
{
front=0;
rear=0;
count=0;
}

template<class T>
void Queue<T>::QInsert(const T & item)
{
if(count==50)
{
cout<<"Queue overflow"<<endl;
exit(1);
}
count++;
QList[rear]=item;
rear=(rear+1)%50;
//cout<<"Insert a node with the value"<<item<<endl;
return;
}

template<class T>
T Queue<T>::QDelete(void)
{
if(count==0)
{
cout<<"Deleting from am empty queue"<<endl;
exit(1);
}
T temp;
temp=QList[front];
count--;
front=(front+1)%50;
//cout<<"Delete a node with the value"<<temp<<endl;
return temp;
}

template<class T>
void Queue<T>::ClearQueue(void)
{
front=0;
rear=0;
count=0;
return;
}

template<class T>
T Queue<T>::QFront(void) const
{
if(count==0)
{
cout<<"Attempt to fetch an empty queue"<<endl;
return NULL;
}
T temp;
temp=QList[front];
//cout<<"The front of the queue is"<<temp<<endl;
return QList[front];
}

template<class T>
int Queue<T>::QLength(void) const
{
return count;
}

template<class T>
int Queue<T>::QEmpty(void) const
{
return (count==0);
}

template<class T>
int Queue<T>::QFull(void) const
{
return (count==50);
}

template<class T>
class Stack
{
private:
T StackList[50];//
int top;
public:
Stack(void);
void Push(const T& item);
T Pop(void);
void ClearStack(void);
T Peek(void) const;
int StackEmpty(void) const;
int StackFull(void) const;
int StackSize(void);
};

template<class T>
Stack<T>::Stack(void)
{
top=-1;
}

template<class T>
void Stack<T>::Push(const T& item)
{
if(top==49)//
{
cout<<"Stack overflow"<<endl;
return;
}
top++;
StackList[top]=item;
//cout<<"Now push"<<item<<endl;
return;
}

template<class T>
T Stack<T>::Pop(void)
{
T temp;
if(top==-1)
{
cout<<"Attemp to pop an empty stack"<<endl;
exit(1);
}
temp=StackList[top];
top--;
//cout<<"Now pop"<<temp<<endl;
return temp;
}

template<class T>
T Stack<T>::Peek(void) const
{
if(top==-1)
{
cout<<"Attemp to peek an empty stack"<<endl;
exit(1);
}
//cout<<"Now peek"<<StackList[top]<<endl;
return StackList[top];
}

template<class T>
int Stack<T>::StackEmpty(void) const
{
return (top==-1);
}

template<class T>
int Stack<T>::StackFull(void) const
{
return(top==49);//
}

template<class T>
void Stack<T>::ClearStack(void)
{
top=-1;
}

template<class T>
int Stack<T>::StackSize(void)
{
return 50;
}

template <class T>
class BinTree;

template <class T>
class BinTreeNode
{
friend class BinTree<T>;
public:
BinTreeNode<T> * left;
BinTreeNode<T> * right;
//public:
T data;
BinTreeNode(const T & item)
{
data=item;
left=NULL;
right=NULL;
}
BinTreeNode(BinTreeNode<T> * p) { data=p->data;left=p->left;right=p->right;}
BinTreeNode<T> * GetLeft(void) const
{
return left;
}
BinTreeNode<T> * GetRight(void) const
{
return right;
}
void SetLeft(BinTreeNode<T> * L)
{
left=L;
}
void SetRight(BinTreeNode<T> * R)
{
right=R;
}
BinTreeNode<T> * LeftInsert(BinTreeNode<T> * current,T item);
BinTreeNode<T> * RightInsert(BinTreeNode<T> * current,T item);
};

template <class T>
BinTreeNode<T> * BinTreeNode<T>::LeftInsert(BinTreeNode<T> * current,T item)
{
if(current->left==NULL)
{
current->left=new BinTreeNode<T>(item);
return current->left;
}
return NULL;
}

template <class T>
BinTreeNode<T> * BinTreeNode<T>::RightInsert(BinTreeNode<T> * current,T item)
{
if(current->right==NULL)
{
current->right=new BinTreeNode<T>(item);
return current->right;
}
return NULL;
}

template <class T>
class BinTree
{
private:
BinTreeNode<T> * root;
T stop;
BinTreeNode<T> * Father(BinTreeNode<T> * begin,BinTreeNode<T> * current);
void PreOrder(BinTreeNode<T> * t) const;
void InOrder(BinTreeNode<T> * t) const;
void PostOrder(BinTreeNode<T> * t) const;

public: void LevelOrder_Queue(BinTreeNode<T> * p);
BinTree() { root=NULL;}
BinTree(BinTreeNode<T> * ptr,T mark) { root=ptr;stop=mark;}
virtual int IsEmpty() { return(root==NULL?1:0);}
void PreOrder();
void InOrder();
void PostOrder();
void LevelOrder_Queue();
void PreOrder_Stack();
void InOrder_Stack();
void PostOrder_Stack();
virtual BinTreeNode<T> * Father(BinTreeNode<T> * current)
{
if(current==NULL)
return NULL;
Father(root,current);
}
virtual BinTreeNode<T> * Left(BinTreeNode<T> * current)
{
return ((current!=NULL)?current->left:NULL);
}
virtual BinTreeNode<T> * Right(BinTreeNode<T> * current)
{
return ((current!=NULL)?current->right:NULL);
}
int Find(const T & item) const;
BinTreeNode<T> * GetRoot() const
{
return root;
}
void Out();
BinTreeNode<T> * GetNode(T item) { BinTreeNode<T> * t=new BinTreeNode<T>(item) ;return t;}
int Find(BinTreeNode<T> * & current,T item) ;
void DelSubtree(BinTreeNode<T> * current);
BinTreeNode<T> * Brother(BinTreeNode<T> * p);
};

template <class T>
BinTreeNode<T> * BinTree<T>::Father(BinTreeNode<T> * begin,BinTreeNode<T> * current)
{
BinTreeNode<T> * temp;
if(begin==NULL)
return NULL;
if((begin->left==current)||(begin->right==current))
return begin;
if((temp=Father(begin->left,current))!=NULL)
return temp;
else
return Father(begin->right,current);
}

template <class T>
void BinTree<T>::DelSubtree(BinTreeNode<T> * current)
{
if(current!=NULL)
{
DelSubtree(current->left);
DelSubtree(current->right);
cout<<current->data;
delete current;
}
}

template <class T>
void BinTree<T>::Out()
{
cout<<"Output the binary tree in the preorder!"<<endl;
PreOrder();
cout<<endl;
return;
}

template <class T>
void BinTree<T>::PreOrder(BinTreeNode<T> * t) const
{
if(t!=NULL)
{
cout<<t->data;
PreOrder(t->left);
PreOrder(t->right);
return;
}
}

template <class T>
void BinTree<T>::InOrder(BinTreeNode<T> * t) const
{
if(t!=NULL)
{
InOrder(t->left);
cout<<t->data;
InOrder(t->right);
return;
}
}

template <class T>
void BinTree<T>::PostOrder(BinTreeNode<T> * t) const
{
if(t!=NULL)
{
PostOrder(t->left);
PostOrder(t->right);
cout<<t->data;
return;
}
}

template<class T>
void BinTree<T>::LevelOrder_Queue(BinTreeNode<T> * p)
{
Queue<BinTreeNode<T> * > q;
if(p!=NULL)
{
BinTreeNode<T> * temp=p;
q.QInsert(new BinTreeNode<T>(temp));
while(!q.QEmpty())
{
temp=q.QDelete();
if(temp!=NULL)
cout<<temp->data;
if(temp->left!=NULL)
q.QInsert(new BinTreeNode<T>(temp->left));
if(temp->right!=NULL)
q.QInsert(new BinTreeNode<T>(temp->right));

}
return;
}
}

template <class T>
void BinTree<T>::PreOrder()
{
PreOrder(root);
}

template <class T>
void BinTree<T>::InOrder()
{
InOrder(root);
}

template <class T>
void BinTree<T>::PostOrder()
{
PostOrder(root);
}

template<class T>
void BinTree<T>::LevelOrder_Queue()
{
LevelOrder_Queue(root);
}

template<class T>
void BinTree<T>::PreOrder_Stack()
{
if(root==NULL)
return;
Stack<BinTreeNode<T> * > s;
BinTreeNode<T> * p=root;
while(p!=NULL)
{
cout<<p->data;
s.Push(p);
if(p->left!=NULL)
p=p->left;
else
p=p->right;
}
while((p==NULL)&&(!s.StackEmpty()))
{
p=s.Pop();
if(s.StackEmpty())
return;
p=Brother(p);
}
while(!s.StackEmpty())
{
while(p!=NULL)
{
cout<<p->data;
s.Push(p);
if(p->left!=NULL)
p=p->left;
else
p=p->right;

}
while((p==NULL)&&(!s.StackEmpty()))
{
p=s.Pop();
if(s.StackEmpty())
return;
p=Brother(p);
}
}
}

template<class T>
void BinTree<T>::InOrder_Stack()
{
if(root==NULL)
return;
if((root->left==NULL)&&(root->right==NULL))
{
cout<<root->data;
return;
}
Stack<BinTreeNode<T> * > s;
BinTreeNode<T> * p=root;
BinTreeNode<T> * jl[100];
for(int i=0;i<100;i++)
jl[i]=NULL;
int num=0;
while(p!=NULL)
{
s.Push(p);
if(p->left!=NULL)
p=p->left;
else
p=p->right;
}
while((p==NULL)&&(!s.StackEmpty()))
{
p=s.Pop();
if(s.StackEmpty())
return;
int p_pos=0;
int r_pos=0;
for(int i=0;i<100;i++)
{
if(jl[i]==p)
p_pos=1;
if(jl[i]==Father(root,p))
r_pos=1;
}
if(p_pos==0)
{
cout<<p->data;
jl[num]=p;
num++;
}
if(r_pos==0)
{
cout<<Father(root,p)->data;
jl[num]=Father(root,p);
num++;
}
p=Brother(p);
}
while(!s.StackEmpty())
{
while(p!=NULL)
{
s.Push(p);
if(p->left!=NULL)
p=p->left;
else
p=p->right;

}
while((p==NULL)&&(!s.StackEmpty()))
{
p=s.Pop();
if(s.StackEmpty())
return;
int p_pos=0;
int r_pos=0;
for(int i=0;i<100;i++)
{
if(jl[i]==p)
p_pos=1;
if(jl[i]==Father(root,p))
r_pos=1;
}
if(p_pos==0)
{
cout<<p->data;
jl[num]=p;
num++;
}
if(r_pos==0)
{
cout<<Father(root,p)->data;
jl[num]=Father(root,p);
num++;
}
p=Brother(p);
}
}
}

template<class T>
void BinTree<T>::PostOrder_Stack()
{
if(root==NULL)
return;
Stack<BinTreeNode<T> * > s;
BinTreeNode<T> * p=root;
while(p!=NULL)
{
s.Push(p);
if(p->left!=NULL)
p=p->left;
else
p=p->right;
}
while((p==NULL)&&(!s.StackEmpty()))
{
p=s.Pop();
if(s.StackEmpty())
{
if(p==root)
cout<<p->data;
return;
}
cout<<p->data;
p=Brother(p);
}
while(!s.StackEmpty())
{
while(p!=NULL)
{
s.Push(p);
if(p->left!=NULL)
p=p->left;
else
p=p->right;

}
while((p==NULL)&&(!s.StackEmpty()))
{
p=s.Pop();
if(s.StackEmpty())
{
if(p==root)
cout<<p->data;
return;
}
cout<<p->data;
p=Brother(p);
}
}
}

template <class T>
int BinTree<T>::Find(BinTreeNode<T> * & current,T item)
{
int i=0;
if(current==NULL)
return 0;
else
if(current->data==item)
return 1;
else
if((i=Find(current->left,item))!=0)
return 1;
else
return Find(current->right,item);
}

template <class T>
int BinTree<T>::Find(const T & item) const
{
Find(root,item);
}

template<class T>
BinTreeNode<T> * BinTree<T>::Brother(BinTreeNode<T> * p)
{
if((root==NULL)||(p==NULL)||(p==root))
return NULL;
BinTreeNode<T> * temp=Father(root,p);
if (temp==NULL)
return NULL;
if((temp->right!=NULL)&&(temp->right==p))
return NULL;
return temp->right;
}

int main()
{
BinTreeNode<int> * rroot=new BinTreeNode<int>(1);
BinTreeNode<int> * nu2=rroot->LeftInsert(rroot,2);
BinTreeNode<int> * nu3=rroot->RightInsert(rroot,3);
BinTreeNode<int> * nu4=nu2->LeftInsert(nu2,4);
BinTreeNode<int> * nu5=nu2->RightInsert(nu2,5);
BinTreeNode<int> * nu6=nu3->LeftInsert(nu3,6);
BinTreeNode<int> * nu7=nu3->RightInsert(nu3,7);
BinTreeNode<int> * nu8=nu4->LeftInsert(nu4,8);
BinTreeNode<int> * nu9=nu4->RightInsert(nu4,9);
cout<<endl;
BinTree<int> bti(rroot,0);
bti.GetRoot();
cout<<endl;
bti.PreOrder();
cout<<endl;
cout<<bti.Find(rroot,1);
cout<<endl;
bti.LevelOrder_Queue(rroot);
cout<<endl;
cout<<"~~~~~~~~~";
bti.InOrder_Stack();
//cout<<endl;
//bti.InOrder_Stack();
//cout<<endl;
//bti.PostOrder_Stack();
cout<<endl;
bti.DelSubtree(rroot);
cout<<endl;
return 1;
}