#include "DCirList.h"
#pragma once
#pragma region
//树类
//测试日期 2010-3-11
#ifndef TREENODE_H
#define TREENODE_H
template<class T>
class TreeNode
{
public:
TreeNode<T>* firstchild; //第一个孩子结点指针
TreeNode<T>* nextsibling; //下一个兄弟结点指针
T data; //数据域
TreeNode(){firstchild=nextsibling=NULL;} //构造函数
TreeNode(T item,TreeNode<T>* pf=NULL,TreeNode<T>* pn=NULL) //重载构造函数
{data=item;firstchild=pf;nextsibling=pn;}
};
#endif
#pragma endregion
#pragma region
#ifndef TREE_H
#define TREE_H
template<class T>
class Tree
{
private:
TreeNode<T>* root; //根结点指针
TreeNode<T>* current; //当前结点指针
TreeNode<T>* SearchParent(TreeNode<T>* t,TreeNode<T>* s); //递归查找父结点
TreeNode<T>* SearchPrevious(TreeNode<T>* t,TreeNode<T>* s); //递归查找前驱结点
TreeNode<T>* Copy(TreeNode<T>* t); //拷贝函数
public:
Tree(){root=current=NULL;} //构造函数
~Tree(){ClearTree();} //析构函数
void ClearTree(){DeleteSubtree(root);} //清空树
//获取结点指针(8个函数)
TreeNode<T>* GetRoot()
{return root;} //返回根结点指针
TreeNode<T>* GetCurrent()
{return current;} //返回当前结点指针
TreeNode<T>* GetParent(); //返回当前结点的父结点的指针
TreeNode<T>* GetPrevious(); //返回当前结点的前驱结点的指针
TreeNode<T>* GetFirstChild() //返回当前结点的第一个孩子结点的指针
{return current==NULL?NULL:current->firstchild;}
TreeNode<T>* GetLastChild(); //返回当前结点的最后一个孩子结点的指针
TreeNode<T>* GetNextSibling() //返回当前结点的兄弟结点的指针
{return current==NULL?NULL:current->nextsibling;}
TreeNode<T>* GetChild(int i); //返回当前结点的第i个孩子结点的指针
//三种遍历(3个函数)
void PreOrder(TreeNode<T> *t,void(*visit)(T x)); //先根遍历以t为根结点的数据域
void PosOrder(TreeNode<T> *t,void(*visit)(T x)); //后根遍历以t为根结点的数据域
void LevelOrder(TreeNode<T> *t,void(*visit)(T x)); //层序遍历以t为根结点的数据域
//设置当前结点,并返回当前结点指针(8个函数)
TreeNode<T>* SetRoot()
{return current=root;} //把根结点设置为当前结点
TreeNode<T>* SetCurrent(TreeNode<T> *t)
{return current=t;} //把t所指向的结点设置为当前结点
TreeNode<T>* SetParent()
{return current=GetParent();} //把当前结点的父结点设置为当前结点
TreeNode<T>* SetPrevious()
{return current=GetPrevious();} //把当前结点的前驱结点设置为当前结点
TreeNode<T>* SetFirstChild()
{return current=GetFirstChild();} //把当前结点的第一个孩子结点设置为当前结点
TreeNode<T>* SetLastChild()
{return current=GetLastChild();} //把当前结点的最后一个孩子结点设置为当前结点
TreeNode<T>* SetNextSibling()
{return current=GetNextSibling();} //把当前结点的兄弟结点设置为当前结点
TreeNode<T>* SetChild(int i)
{return current=GetChild(i);} //把当前结点的第i个孩子结点设置为当前结点
//插入与删除(6个函数)
void InsertFirstChild(T x); //把x插入为当前结点的第一个孩子结点
void InsertLastChild(T x); //把x插入为当前结点的最后一个孩子结点
void InsertChild(int i,T x); //把x插入为当前结点的第i个孩子结点
void InsertSibling(T x); //把x插入为当前结点的下一个兄弟结点
void DeleteSubtree(TreeNode<T>* &t); //删除以t为根结点的子树
void DeleteChild(int i); //删除当前结点的第i个孩子结点
//其他操作(2个函数)
bool IsEmpty(){return root==NULL?true:false;} //判断是否为空树
Tree<T>& operator=(Tree<T>& tree); //运算符重载
};
#endif
#pragma endregion
#pragma region
template<class T>
TreeNode<T>* Tree<T>::SearchParent(TreeNode<T> *t, TreeNode<T> *s)
{
if(t==NULL||s==NULL||s==root) return NULL;
TreeNode<T>* p=t->firstchild;
for(;p!=NULL;p=p->nextsibling)
{
if(p==s) return t;
SearchParent(p,s);
}
return NULL;
}
template<class T>
TreeNode<T>* Tree<T>::SearchPrevious(TreeNode<T> *t, TreeNode<T> *s)
{
if(t==NULL||s==NULL||s==root) return NULL;
if(t->firstchild==s||t->nextsibling==s) return t;
TreeNode<T> *p=NULL;
if((p=SearchPrevious(t->firstchild,s))!=NULL) return p;
if((p=SearchPrevious(t->nextsibling,s))!=NULL) return p;
}
template<class T>
TreeNode<T>* Tree<T>::Copy(TreeNode<T> *t)
{
if(t==NULL) return NULL;
TreeNode<T>* p=new TreeNode<T>();
p->data=t->data;
p->firstchild=Copy(t->firstchild);
p->nextsibling=Copy(t->nextsibling);
return p;
}
template<class T>
TreeNode<T>* Tree<T>::GetParent()
{
return SearchParent(root,current);
}
template<class T>
TreeNode<T>* Tree<T>::GetPrevious()
{
return SearchPrevious(root,current);
}
template<class T>
TreeNode<T>* Tree<T>::GetLastChild()
{
if(current==NULL) return NULL;
TreeNode<T>* p=current->firstchild;
for(;p->nextsibling!=NULL;p=p->nextsibling);
return p;
}
template<class T>
TreeNode<T>* Tree<T>::GetChild(int i)
{
if(current==NULL||i<0) return NULL;
TreeNode<T>* p=current->firstchild;
for(int k=0;p!=NULL&&k<i;k++)
p=p->nextsibling;
return p;
}
template<class T>
void Tree<T>::PreOrder(TreeNode<T> *t, void (*visit)(T))
{
if(t==NULL) return;
visit(t->data);
if(t->firstchild!=NULL) PreOrder(t->firstchild,visit);
if(t->nextsibling!=NULL) PreOrder(t->nextsibling,visit);
}
template<class T>
void Tree<T>::PosOrder(TreeNode<T> *t, void (*visit)(T))
{
if(t==NULL) return;
if(t->firstchild!=NULL) PosOrder(t->firstchild,visit);
visit(t->data);
if(t->nextsibling!=NULL) PosOrder(t->nextsibling,visit);
}
template<class T>
void Tree<T>::LevelOrder(TreeNode<T> *t, void (*visit)(T))
{
if(t==NULL) return;
DCirList<TreeNode<T>*> list;
TreeNode<T>* p1,*p2;
list.PushBack(t);
while(!list.IsEmpty())
{
p1=list.PopFront();
visit(p1->data);
p2=p1->firstchild;
while(p2!=NULL)
{
list.PushBack(p2);
p2=p2->nextsibling;
}
}
}
template<class T>
void Tree<T>::InsertFirstChild(T x)
{
TreeNode<T>* newnode=new TreeNode<T>(x);
if(root==NULL){current=root=newnode; return;}
if(current==NULL)return;
if(current->firstchild!=NULL)
{
TreeNode<T>* p=GetFirstChild();
current->firstchild=newnode;
newnode->nextsibling=p;
}
else
current->firstchild=newnode;
}
template<class T>
void Tree<T>::InsertLastChild(T x)
{
TreeNode<T>* newnode=new TreeNode<T>(x);
if(root==NULL){current=root=newnode; return;}
if(current==NULL)return;
if(current->firstchild!=NULL)
{
TreeNode<T>* p=GetLastChild();
p->nextsibling=newnode;
}
else
current->firstchild=newnode;
}
template<class T>
void Tree<T>::InsertChild(int i, T x)
{
TreeNode<T>* newnode=new TreeNode<T>(x);
if(root==NULL){current=root=newnode; return;}
if(current==NULL||i<0)return;
TreeNode<T>* p=current->firstchild;
if(p!=NULL)
{
if(i==0)
{
newnode->nextsibling=p;
current->firstchild=newnode;
}
else
{
p=GetChild(i-1);
newnode->nextsibling=p->nextsibling;
p->nextsibling=newnode;
}
}
else
current->firstchild=newnode;
}
template<class T>
void Tree<T>::InsertSibling(T x)
{
if(current==NULL||current==root)return;
TreeNode<T>* newnode=new TreeNode<T>(x);
newnode->nextsibling=current->nextsibling;
current->nextsibling=newnode;
}
template<class T>
void Tree<T>::DeleteSubtree(TreeNode<T>* &t)
{
if(t==NULL) return;
TreeNode<T> *r,*p1,*p2;
p1=t->firstchild;
while(p1!=NULL)
{
p2=p1->nextsibling;
DeleteSubtree(p1);
p1=p2;
}
r=SearchPrevious(root,t);
if(r!=NULL)
{
if(r->firstchild==t)
r->firstchild=t->nextsibling;
if(r->nextsibling==t)
r->nextsibling=t->nextsibling;
}
delete t;
t=NULL;
}
template<class T>
void Tree<T>::DeleteChild(int i)
{
TreeNode<T>* p=GetChild(i);
DeleteSubtree(p);
}
template<class T>
Tree<T>& Tree<T>::operator =(Tree<T> &tree)
{
if(tree.root==NULL) return *this;
current=root=Copy(tree.root);
return *this;
}
#pragma endregion
分享到:
相关推荐
数据结构---C语言描述-(耿国华)-高等教育出版社出版-课后习题答案
数据结构-基本算法-孩子兄弟链表(学生时代源码,调试可运行)
数据结构-----JAVA类集学习之-------线性表.pdf
山东大学数据结构课设-基于prim算法生成最小生成树的可视化展示程序(下载即用).zip山东大学数据结构课设-基于prim算法生成最小生成树的可视化展示程序(下载即用).zip山东大学数据结构课设-基于prim算法生成最小...
利用大量且丰富的图示与范例, 详解复杂的抽象理论,从最基本的数据结构概念开始 说明,再以Java工具加以诠释阵列结构、堆栈、链表 、队列、排序、查找等重要的概念,引领读者抓住重 点轻松进入数据结构的学习领域
数据结构--哈夫曼树的基本代码 数据结构的重点算法之一
数据结构--二叉树--思维导图.pdf
数据结构(Java)练习--树.docx
数据结构--DS实验数据结构--DS实验数据结构--DS实验数据结构--DS实验
数据结构--树与森林--思维导图.pdf
数据结构--严蔚敏数据结构--严蔚敏数据结构--严蔚敏数据结构--严蔚敏
数据结构--图数据结构--图数据结构--图数据结构--图数据结构--图, 图的处理
图解数据结构6-树及树的遍历,非常详细地介绍了数据结构中“树”的概念
数据结构---二叉排序树.doc
数据结构-树的建立遍历,有助于学习C/C++
数据结构----名词解释
数据结构---图课件 详细全面 有代码实现
C语言树据结构 抽象数据类型的实现—树 利用二叉链表的存储结构,开发工具:VC++