TreeNode.h
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){}
};
Tree.h
#include "TreeNode.h"
#include "LinkQueue.h"
template<typename Type> class Tree{
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);
public:
Tree():m_proot(NULL), m_pcurrent(NULL){}
TreeNode<Type> *GetCurrent(){return m_pcurrent;}
void SetCurrent(TreeNode<Type> *current){m_pcurrent = current;}
bool Insert(Type item);
void Remove(Type item);
void Remove(TreeNode<Type> *current);
bool Find(Type item);
void PrintChild(TreeNode<Type> *current);
TreeNode<Type> *Parent(TreeNode<Type> *current);
void Print();
void PreOrder(TreeNode<Type> *root);
void PostOrder(TreeNode<Type> *root);
void LevelOrder(TreeNode<Type> *root);
void PreOrder();
void PostOrder();
void LevelOrder();
};
Tree.cpp
template<typename Type> bool Tree<Type>::Insert(Type item){
TreeNode<Type> *p = new TreeNode<Type>(item);
if (NULL == p){
cout << "Application Error!" <<endl;
exit(1);
}
if(m_proot == NULL)
{
m_proot = p;
m_pcurrent = p;
return 1;
}
if (NULL == m_pcurrent){
cerr << "insert error!" <<endl;
return 0;
}
if(m_pcurrent->m_pfirst == NULL)
{
m_pcurrent->m_pfirst = p;
m_pcurrent = p;
return 1;
}
TreeNode<Type> *q = m_pcurrent->m_pfirst;
while(q->m_pnext != NULL)
q = q->m_pnext;
q->m_pnext = p;
m_pcurrent = p;
return 1;
}
template<typename Type> void Tree<Type>::Remove(TreeNode<Type> *current){
if(current == NULL)
return ;
if(current == m_proot)
{
TreeNode<Type> *p = current->m_pfirst;
TreeNode<Type> *q = p->m_pfirst;
if(q == NULL)
{
p->m_pfirst = p->m_pnext;
p->m_pnext = NULL;
}
m_proot = p;
}
else
{
TreeNode<Type> *temp = Parent(current);
if(current == temp->m_pfirst )
{
TreeNode<Type> *p = current->m_pfirst;
if(p)
{
while(p)p = p->m_pnext;
p->m_pnext = current->m_pnext;
}
else
current->m_pfirst = current->m_pnext;
}
else{
TreeNode<Type> *p = temp->m_pfirst;
while(p->m_pnext != current)
p = p->m_pnext;
p->m_pnext = current->m_pnext;
while(p->m_pnext)
p = p->m_pnext;
p->m_pnext = current->m_pnext;
}
}
delete current;
}
template<typename Type> void Tree<Type>::Remove(TreeNode<Type> *root, Type item){
if(root == NULL)
return ;
if(root->m_pfirst)
{
TreeNode<Type> *p = root->m_pfirst;
while(p)
{
Remove(p, item);
p = p->m_pnext;
}
}
if(root->m_data == item)
Remove(root);
}
template<typename Type> void Tree<Type>::Remove(Type item){
Remove(m_proot, item);
}
template<typename Type> TreeNode<Type>* Tree<Type>::Parent(TreeNode<Type> *root, TreeNode<Type> *current){
if(root == NULL)
return NULL;
TreeNode<Type> *p = root->m_pfirst;
if(p)
{
while(p){
if(p == current)
return root;
TreeNode<Type> *q = Parent(p,current);
if(q)
return q;
p = p->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> *p = current->m_pfirst;
while(p)
{
cout << p->m_data<<' ';
p = p->m_pnext;
}
cout<<endl;
}
template<typename Type> bool Tree<Type>::Find(TreeNode<Type> *root, Type item){
if(root->m_data == item)
return 1;
if(root == NULL)
return 0;
TreeNode<Type> *p = root->m_pfirst;
while(p)
{
if(Find(p,item))
return 1;
p = p->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(root == NULL)
return ;
cout<<root->m_data<<' ';
TreeNode<Type> *p = root->m_pfirst;
while(p)
{
PreOrder(p);
p = p->m_pnext;
}
}
template<typename Type> void Tree<Type>::PostOrder(TreeNode<Type> *root){
if(root == NULL)
return ;
TreeNode<Type> *p = root->m_pfirst;
while(p)
{
PostOrder(p);
p = p->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> *p, *q;
if(root != NULL)
{
queue.Append(root);
while(! queue.IsEmpty())
{
p = queue.Delete();
cout<<p->m_data<<' ';
q = p->m_pfirst;
while(q)
{
queue.Append(q);
q = q->m_pnext;
}
}
}
}
template<typename Type> void Tree<Type>::LevelOrder(){
LevelOrder(m_proot);
}
Test.cpp
#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;
}