template<typename Type> class LinkQueue;
template<typename Type> class QueueNode{
private:
friend class LinkQueue<Type>;
QueueNode(const Type item,QueueNode<Type> *next=NULL)
:m_data(item),m_pnext(next){}
private:
Type m_data;
QueueNode<Type> *m_pnext;
};
#include "QueueNode.h"
template<typename Type> class LinkQueue{
public:
LinkQueue():m_prear(NULL),m_pfront(NULL){}
~LinkQueue(){
MakeEmpty();
}
void Append(const Type item);
Type Delete();
Type GetFront();
void MakeEmpty();
bool IsEmpty() const{
return m_pfront==NULL;
}
void Print();
private:
QueueNode<Type> *m_prear,*m_pfront;
};
template<typename Type> void LinkQueue<Type>::MakeEmpty(){
QueueNode<Type> *pdel;
while(m_pfront){
pdel=m_pfront;
m_pfront=m_pfront->m_pnext;
delete pdel;
}
}
template<typename Type> void LinkQueue<Type>::Append(const Type item){
if(m_pfront==NULL){
m_pfront=m_prear=new QueueNode<Type>(item);
}
else{
m_prear=m_prear->m_pnext=new QueueNode<Type>(item);
}
}
template<typename Type> Type LinkQueue<Type>::Delete(){
if(IsEmpty()){
cout<<"There is no element!"<<endl;
exit(1);
}
QueueNode<Type> *pdel=m_pfront;
Type temp=m_pfront->m_data;
m_pfront=m_pfront->m_pnext;
delete pdel;
return temp;
}
template<typename Type> Type LinkQueue<Type>::GetFront(){
if(IsEmpty()){
cout<<"There is no element!"<<endl;
exit(1);
}
return m_pfront->m_data;
}
template<typename Type> void LinkQueue<Type>::Print(){
QueueNode<Type> *pmove=m_pfront;
cout<<"front";
while(pmove){
cout<<"--->"<<pmove->m_data;
pmove=pmove->m_pnext;
}
cout<<"--->rear"<<endl<<endl<<endl;
}
template<typename Type> class Tree;
template<typename Type> class TreeNode{
public:
friend class Tree<Type>;
private:
Type m_data;
TreeNode<Type> *m_pfirst,*m_pnext;
TreeNode():m_pfirst(NULL), m_pnext(NULL){}
TreeNode(Type item, TreeNode<Type> *first = NULL, TreeNode<Type> *next = NULL)
:m_data(item), m_pfirst(first), m_pnext(next){}
};
#include "TreeNode.h"
#include "LinkQueue.h"
template<typename Type> class Tree{
public:
Tree():m_proot(NULL), m_pcurrent(NULL){}
public:
TreeNode<Type> *GetCurrent(){ //Get the current node
return m_pcurrent;
}
void SetCurrent(TreeNode<Type> *current){ //set the current node
m_pcurrent = current;
}
bool Insert(Type item); //insert an new node to current node
void Remove(Type item); //delete the node whose data is equal to item
void Remove(TreeNode<Type> *current); //delete the node
bool Find(Type item); //find the node whose data is equal to item
void PrintChild(TreeNode<Type> *current); //print the child tree
TreeNode<Type> *Parent(TreeNode<Type> *current); //get the parent
void Print(); //print the tree
void PreOrder(TreeNode<Type> *root); //ordering the tree by visiting the root first
void PostOrder(TreeNode<Type> *root); //ordering the tree by visiting the root last
void LevelOrder(TreeNode<Type> *root); //ordering the tree by level
void PreOrder();
void PostOrder();
void LevelOrder();
private:
TreeNode<Type> *m_proot,*m_pcurrent;
bool Find(TreeNode<Type> *root, Type item);
void Remove(TreeNode<Type> *root, Type item);
TreeNode<Type> *Parent(TreeNode<Type> *root, TreeNode<Type> *current);
void Print(TreeNode<Type> *start, int n=0);
};
template<typename Type> bool Tree<Type>::Insert(Type item){
TreeNode<Type> *newnode = new TreeNode<Type>(item);
if (NULL == newnode){
cout << "Application Error!" <<endl;
exit(1);
}
if (NULL == m_proot){
m_proot = newnode;
m_pcurrent = m_proot;
return 1;
}
if (NULL == m_pcurrent){
cerr << "insert error!" <<endl;
return 0;
}
if(NULL == m_pcurrent->m_pfirst){
m_pcurrent->m_pfirst = newnode;
m_pcurrent = newnode;
return 1;
}
TreeNode<Type> *pmove = m_pcurrent->m_pfirst;
while(pmove->m_pnext){
pmove = pmove->m_pnext;
}
pmove->m_pnext = newnode;
m_pcurrent = newnode;
return 1;
}
template<typename Type> void Tree<Type>::Remove(TreeNode<Type> *current){
if(NULL == current){
return;
}
TreeNode<Type> *temp = Parent(current);
if(NULL == temp){
TreeNode<Type> *pmove = current->m_pfirst;
if(NULL != pmove->m_pfirst){
pmove=pmove->m_pfirst;
while(pmove->m_pnext){
pmove = pmove->m_pnext;
}
pmove->m_pnext = current->m_pfirst->m_pnext;
current->m_pfirst->m_pnext = NULL;
}
else{
pmove->m_pfirst = pmove->m_pnext;
}
m_proot = current->m_pfirst;
}
else{
if(temp->m_pfirst == current){
TreeNode<Type> *pmove = current->m_pfirst;
if (pmove){
while (pmove->m_pnext){
pmove = pmove->m_pnext;
}
pmove->m_pnext = current->m_pnext;
}
else{
current->m_pfirst = current->m_pnext;
}
}
else{
TreeNode<Type> *pmove = temp->m_pfirst;
while(pmove->m_pnext != current){
pmove = pmove->m_pnext;
}
pmove->m_pnext = current->m_pnext;
while(pmove->m_pnext){
pmove = pmove->m_pnext;
}
pmove->m_pnext = current->m_pfirst;
}
}
delete current;
}
template<typename Type> void Tree<Type>::Remove(TreeNode<Type> *root, Type item){
if(NULL == root){
return;
}
if(root->m_pfirst){
TreeNode<Type> *pmove=root->m_pfirst;
while(pmove){
Remove(pmove, item);
pmove = pmove->m_pnext;
}
}
if(root->m_data == item){
Remove(root);
}
}
template<typename Type> void Tree<Type>::Remove(Type item){
return Remove(m_proot, item);
}
template<typename Type> TreeNode<Type>* Tree<Type>::Parent(
TreeNode<Type> *root, TreeNode<Type> *current){
if(NULL == root){
return NULL;
}
TreeNode<Type> *pmove=root->m_pfirst,*temp;
if(NULL != pmove){
while(pmove){
if(pmove == current){
return root;
}
pmove = pmove->m_pnext;
}
}
pmove = root->m_pfirst;
while(pmove){
temp = Parent(pmove, current);
if(temp){
return temp;
}
pmove = pmove->m_pnext;
}
return NULL;
}
template<typename Type> TreeNode<Type>* Tree<Type>::Parent(TreeNode<Type> *current){
return Parent(m_proot,current);
}
template<typename Type> void Tree<Type>::PrintChild(TreeNode<Type> *current){
TreeNode<Type> *pmove = current->m_pfirst;
cout<<"first";
if(NULL != pmove){
cout<<"--->"<<pmove->m_data;
}
while(pmove->m_pnext){
cout<<"--->"<<pmove->m_data;
pmove = pmove->m_pnext;
}
}
template<typename Type> bool Tree<Type>::Find(TreeNode<Type> *root, Type item){
if (root->m_data == item){
return 1;
}
if (NULL == root){
return 0;
}
TreeNode<Type> *pmove=root->m_pfirst;
if (NULL == pmove){
return 0;
}
while (pmove){
if (Find(pmove, item)){
return 1;
}
pmove = pmove->m_pnext;
}
return 0;
}
template<typename Type> bool Tree<Type>::Find(Type item){
return Find(m_proot,item);
}
template<typename Type> void Tree<Type>::Print(TreeNode<Type> *start, int n = 0){
if (NULL == start){
for (int i=0; i<n; i++){
cout << " ";
}
cout << "NULL" << endl;
return;
}
TreeNode<Type> *pmove = start->m_pfirst;
Print(pmove, n+1);
for (int i=0; i<n; i++){
cout << " ";
}
cout << start->m_data << "--->" <<endl;
if (NULL == pmove){
return;
}
pmove = pmove->m_pnext;
while (pmove){
Print(pmove, n+1);
pmove = pmove->m_pnext;
}
}
template<typename Type> void Tree<Type>::Print(){
Print(m_proot);
}
template<typename Type> void Tree<Type>::PreOrder(TreeNode<Type> *root){
if (NULL == root){
return;
}
cout << root->m_data;
TreeNode<Type> *pmove = root->m_pfirst;
while (pmove){
PreOrder(pmove);
pmove = pmove->m_pnext;
}
}
template<typename Type> void Tree<Type>::PostOrder(TreeNode<Type> *root){
if (NULL == root){
return;
}
TreeNode<Type> *pmove = root->m_pfirst;
while (pmove){
PostOrder(pmove);
pmove = pmove->m_pnext;
}
cout << root->m_data;
}
template<typename Type> void Tree<Type>::PreOrder(){
PreOrder(m_proot);
}
template<typename Type> void Tree<Type>::PostOrder(){
PostOrder(m_proot);
}
template<typename Type> void Tree<Type>::LevelOrder(TreeNode<Type> *root){ //using queue
LinkQueue<TreeNode<Type> *> queue;
TreeNode<Type> *pmove, *ptemp;
if (root != NULL){
queue.Append(root);
while (!queue.IsEmpty()){
ptemp = queue.Delete();
cout << ptemp->m_data;
pmove = ptemp->m_pfirst;
while(pmove){
queue.Append(pmove);
pmove = pmove->m_pnext;
}
}
}
}
template<typename Type> void Tree<Type>::LevelOrder(){
LevelOrder(m_proot);
}
#include <iostream>
using namespace std;
#include "Tree.h"
int main(){
Tree<int> tree;
int init[10]={3,6,0,2,8,4,9,1,5,7};
for (int i=0; i<10; i++){
tree.Insert(init[i]);
if (1 == i % 2){
tree.SetCurrent(tree.Parent(tree.GetCurrent()));
}
}
tree.Print();
cout << endl <<endl << endl;
tree.Remove(3);
tree.Print();
cout << endl <<endl << endl;
cout << tree.Find(5) << endl << tree.Find(11) <<endl;
tree.PreOrder();
cout << endl;
tree.PostOrder();
cout << endl;
tree.LevelOrder();
return 0;
}
