几个数据结构的知识点的实现,希望大家多提意见.
只写了几个,不全
:)
(3)树
#include "stdafx.h"
#include <iostream.h>
#include <stdlib.h>
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）
return;
top++;
StackList[top]=item;
return;
}
template<class T>
T Stack<T>::Pop(void)
{
T temp;
if(top==-1)
exit(1);
temp=StackList[top];
top--;
return temp;
}
template<class T>
T Stack<T>::Peek(void) const
{
if(top==-1)
exit(1);
return StackList[top];
return;
}
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 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;
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;
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];
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 Tree;
template <class T>
class TreeNode
{
friend class Tree<T>;
private:
TreeNode<T> * firstchild;
TreeNode<T> * nextbrother;
public:
T data;
TreeNode(T item,TreeNode<T> * L=NULL,TreeNode<T> * R=NULL) { data=item;firstchild=L;nextbrother=R;}
TreeNode(TreeNode<T> * p) { data=p->data;firstchild=p->firstchild;nextbrother=p->nextbrother;}
TreeNode<T> * InsertChild(T item);
TreeNode<T> * InsertBrother(T item);
};
template <class T>
TreeNode<T> * TreeNode<T>::InsertChild(T item)
{
if(firstchild==NULL)
{
TreeNode<T> * temp=new TreeNode<T>(item);
cout<<"Insert a child"<<endl;
firstchild=temp;
return temp;
}
cout<<"Can not insert child at this position"<<endl;
return NULL;
}
template <class T>
TreeNode<T> * TreeNode<T>::InsertBrother(T item)
{
TreeNode<T> * temp1=this;
TreeNode<T> * temp2=temp1->nextbrother;
while(temp2!=NULL)
{
cout<<"Skip one brother"<<endl;
temp1=temp2;
temp2=temp2->nextbrother;
}
temp1->nextbrother=new TreeNode<T>(item);
cout<<"Insert a brother"<<endl;
return temp1->nextbrother;
}
template<class T>
class Tree
{
private:
TreeNode<T> * root;
TreeNode<T> * current;
public:
Tree(TreeNode<T> * p) { root=p;current=p;}
void PreOrder();
void PostOrder();
void PreOrder_Stack();
void PostOrder_Stack();
void LevelOrder_Queue();
int Find(TreeNode<T> * p,T target);
void DelSubtree(TreeNode<T> * p);
TreeNode<T> * Father(TreeNode<T> * t,TreeNode<T> * p);
};
template<class T>
void Tree<T>::PreOrder()
{
if(current!=NULL)
{
cout<<current->data;
TreeNode<T> * temp=current;
current=current->firstchild;
while(current!=NULL)
{
PreOrder();
current=current->nextbrother;
}
current=temp;
}
return;
}
template<class T>
void Tree<T>::PostOrder()
{
if(current!=NULL)
{
TreeNode<T> * temp=current;
current=current->firstchild;
while(current!=NULL)
{
PostOrder();
current=current->nextbrother;
}
current=temp;
cout<<current->data;
}
return;
}
template<class T>
void Tree<T>::PreOrder_Stack()
{
Stack<TreeNode<T> * > s;
TreeNode<T> * p=current;
while(current!=NULL)
{
cout<<current->data;
s.Push(new TreeNode<T>(current));
current=current->firstchild;
}
while((current==NULL)&&(!s.StackEmpty()))
{
current=s.Pop();
current=current->nextbrother;
}
while(!s.StackEmpty())
{
while(current!=NULL)
{
cout<<current->data;
s.Push(new TreeNode<T>(current));
current=current->firstchild;
}
while((current==NULL)&&(!s.StackEmpty()))
{
current=s.Pop();
current=current->nextbrother;
}
}
current=p;
}
template<class T>
void Tree<T>::PostOrder_Stack()
{
Stack<TreeNode<T> * > s;
TreeNode<T> * p=current;
while(current!=NULL)
{
s.Push(new TreeNode<T>(current));
current=current->firstchild;
}
while((current==NULL)&&(!s.StackEmpty()))
{
current=s.Pop();
cout<<current->data;
current=current->nextbrother;
}
while(!s.StackEmpty())
{
while(current!=NULL)
{
s.Push(new TreeNode<T>(current));
current=current->firstchild;
}
while((current==NULL)&&(!s.StackEmpty()))
{
current=s.Pop();
cout<<current->data;
current=current->nextbrother;
}
}
current=p;
}
template <class T>
void Tree<T>::LevelOrder_Queue()
{
Queue<TreeNode<T> * > q;
if(current!=NULL)
{
TreeNode<T> * p=current;
q.QInsert(new TreeNode<T>(current));
while(!q.QEmpty())
{
current=q.QDelete();
cout<<current->data;
current=current->firstchild;
while(current!=NULL)
{
q.QInsert(new TreeNode<T>(current));
current=current->nextbrother;
}
}
current=p;
}
}
template<class T>
int Tree<T>::Find(TreeNode<T> * p,T target)
{
if(p==NULL)
return 0;
if(p->data==target)
return 1;
TreeNode<T> * temp=p->firstchild;
int i=0;
while(temp!=NULL)
{
i=Find(temp,target);
if(i==1)
return 1;
temp=temp->nextbrother;
}
return 0;
}
template<class T>
void Tree<T>::DelSubtree(TreeNode<T> * p)
{
if(p==NULL)
return;
cout<<p->data;
TreeNode<T> * temp=p->firstchild;
while(temp!=NULL)
{
DelSubtree(temp);
temp=temp->nextbrother;
}
return;
}
template<class T>
TreeNode<T> * Tree<T>::Father(TreeNode<T> * t,TreeNode<T> * p)
{
if((t==NULL)||(p==NULL))
return NULL;
TreeNode<T> * temp=t->firstchild;
while(temp!=NULL)
{
if(temp==p)
return t;
temp=temp->nextbrother;
}
TreeNode<T> * temp1=NULL;
TreeNode<T> * temp2=NULL;
if(t->firstchild!=NULL)
{
temp2=t->firstchild;
temp1=Father(temp2,p);
while((temp1==NULL)&&(temp2!=NULL))
{
temp2=temp2->nextbrother;
temp1=Father(temp2,p);
}
return temp1;
}
return NULL;
}
int main()
{
TreeNode<int> * tni1=new TreeNode<int>(1);
TreeNode<int> * tni2=tni1->InsertChild(2);
TreeNode<int> * tni3=tni2->InsertBrother(3);
TreeNode<int> * tni4=tni2->InsertChild(4);
TreeNode<int> * tni5=tni4->InsertBrother(5);
TreeNode<int> * tni6=tni3->InsertChild(6);
TreeNode<int> * tni7=tni6->InsertBrother(7);
TreeNode<int> * tni8=tni4->InsertChild(8);
TreeNode<int> * tni9=tni3->InsertBrother(9);
Tree<int> * tri=new Tree<int>(tni1);
tri->PreOrder();
cout<<endl;
tri->PostOrder();
cout<<endl;
tri->PreOrder_Stack();
cout<<endl;
tri->PostOrder_Stack();
cout<<endl;
int i=0;
i=tri->Find(tni1,0);
cout<<i;
cout<<endl;
tri->DelSubtree(tni1);
cout<<endl;
TreeNode<int> * tni10=tri->Father(tni1,tni3);
cout<<tni10->data;
cout<<endl;
tri->LevelOrder_Queue();
return 1;
}
