📄 tree.h
字号:
#include <iostream.h>
#include "stackqueue.h"
template<class Type>class binaryTree; //二叉树类的前视声明
template<class Type>class binTreeNode{ //二叉树结点类的定义
friend class binaryTree<Type>; //二叉树类是二叉树结点类的友类
public:
binTreeNode():leftChild (NULL),rightChdd (NULL){} //无参构造函数
binTreeNode (Type item, binTreeNode<Type>*left=NULL, binTreeNode<Type>*right=NULL)
:data(item), leftChild(left), rightChild(right){} //有参构造函数
Type getData()const {return data;} //取得结点数据值
binTreeNode<Type>* getLeft()const {return leftChild;} //取得结点左子女指针值
binTreeNode<Type>* getRight()const {return rightChild;} //取得结点右子女指针值
void setData(const Type& item) {data=item;} //修改结点数据值
void setLeft(binTreeNode <Type>*L) {leftChild=L;} //修改结点左子女指针值
void setRight (binTreeNode <Type> * R) {rightChild=R;} //修改结点右子女指针值
private:
binTreeNode <Type> * leftChild, * rightChild ; //左子女、右子女指针域
Type data ; //数据域
};
template <class Type> class binaryTree{ //二叉树类定义
public:
binaryTree():root(NULL){ } //空树构造函数
binaryTree(Type value):refValue (value), root (NULL){} //空树带停止值构造函数
virtual ~binaryTree(){destroy(root);} //析构函数
virtual int isEmpty(){return root==NULL?1:0;} //判二叉树空
virtual binTreeNode<Type>* parent(binTreeNode<Type>* current) //返回双亲指针
{return root==NULL || root==current ? NULL:parent(root,current);}
virtual binTreeNode<Type>* leftChild(binTreeNode <Type>*current)
{return root!=NULL ? current->leftChild:NULL;} //返回左孩子指针
virtual binTreeNode<Type>* rightChild(binTreeNode<Type>*current)
{return root!=NULL ? current->rightChild:NULL;} //返回右孩子指针
binTreeNode<Type>* getRoot()const{return root;} //返回根指针
virtual void insert(const Type& item){insert(item,root);} //插人新元素
virtual binTreeNode<Type>* find(const Type& item)const{
return find(item, root);} //搜索元素
friend istream& operator>>(istream& in, binaryTree<Type>& tree); //流输入友元
friend ostream& operator<<(ostream& out, binaryTree<Type>& tree); //流输出友元
private:
binTreeNode<Type>* root; //二叉树的根指针
Type refValue; //数据输人停止的标志,仅用于输人
binTreeNode<Type>* parent(binTreeNode<Type>* start, binTreeNode<Type>* current);
//私有函数:从结点start开始,搜索结点current的双亲结点。
void traverse(binTreeNode<Type>* current, ostream& out)const;
//私有函数:搜索并输出根为current的二叉树。
void destroy(binTreeNode<Type>* current);
//私有函数:若指针current不为空,则删除根为current的子树
binTreeNode<Type>* find(const Type& item, binTreeNode<Type>* current)const;
void insert(const Type& item, binTreeNode<Type>*& current);
};
template<class Type>binTreeNode<Type>* binaryTree<Type>::
find(const Type& x, binTreeNode<Type>* ptr) const {
//在以ptr为根的二叉树中搜索x,若找到返回该结点的地址，否则返回NULL值。
if(ptr==NULL) return NULL;
else if(x<ptr->data) return find (x, ptr->leftChild); //到左子树中继续搜索
else if(x>ptr->data) return find(x, ptr->rightChild); //到右子树中继续搜索
else return ptr; //搜索成功
}
template<class Type>void binaryTree<Type>::insert(const Type& x, binTreeNode<Type>*& ptr) {
//在以Ptr为根的二叉树中插人结点x,若树中已有x则不插人
if(ptr==NULL){ //新结点作为叶结点插人
ptr=new binTreeNode<Type>(x); //创建新结点
if(ptr==NULL){cerr<<"Out of space"<<endl; exit(1);}
}
else if(x<ptr->data) insert(x, ptr->leftChild); //小于根的关键码，向左子树插人
else if(x>ptr->data) insert(x, ptr->rightChild); //大于，向右子树插入
//除上述情况外，就是x已在树中的情形，不再插人
}
template<class Type>void binaryTree<Type>::destroy(binTreeNode<Type>*current){
//私有函数:若指针current不为空,则删除根为current的子树
if(current !=NULL){
destroy(current->leftChild); //先递归删除current的左子树
destroy(current->rightChild); //先递归删除current的右子树
delete current; //最后释放current指向的结点
}
}
template<class Type>binTreeNode<Type>* binaryTree<Type>::
parent(binTreeNode <Type>*start,binTreeNode<Type>*current){
//私有函数:从结点start开始,搜索结点current的双亲结点。
//若找到结点current的双亲结点,则返回双亲结点地址,否则返回NULL.
if(start==NULL)return NULL;
if(start->leftChild==current || start->rightChild==current) return start; //找到
binTreeNode<Type>* p; //否则
if((p=parent(start->leftChild, current))!=NULL) return p ; //在左子树中递归搜索
else return parent(start-> rightChild, current); //在右子树中递归搜索
}
template<class Type>void binaryTree<Type>::traverse(binTreeNode<Type>*current,ostream& out)const {
//私有函数:搜索并输出根为current的二叉树。
if ( current !=NULL){ //current为空则返回,否则
out<<current-> data<<' '; //输出current的数据值
traverse(current->leftChild, out); //搜索并输出current的左子树
traverse(current->rightChild, out); //搜索并输出current的右子树
}
}
template<class Type>istream & operator>>(istream&in, binaryTree<Type>& tree){
//重载操作:输人并建立一棵二叉树tree.in是输人流对象。
Type item;
cout<<"Constrict binary tree: \n"; //打印标题:构造二叉树
cout<<"Input data(end with*,"<<tree.Ref Value<<"):"; //提示:输人数据
in>>item; //输入refValue是输入结束标志
while(item !=tree.refValue ){ //判断是否结束输人
tree.insert(item); //插人到树中
cout<<"Input data(end with "<<tree.refValue<<"):"; //提示:输入数据
in>>item; //输人
}
return in;
}
template<class Type>ostream& operator<<(ostream& out, binaryTree<Type>& tree){
//重载操作:输出一棵二叉树tree , out是输出流对象。
out<<"preorder traversal of binary tree.\n" ; //提示:搜索二叉树
tree.traverse(tree.root, out); //从根开始输出
out<<endl;
return out;
}
//树的遍历器类===================================================
template <class Type> class treeIterator{ //树游标框架类定义
public:
treeIterator(const binaryTree<Type>& BT):t(BT), current(NULL){} //构造函数
virtual ~treeIterator(){} //析构函数
virtual void first()=0; //纯虚函数:从第一位置开始遍历
virtual void operator++()=0; //纯虚函数:到下一位置
int operator+()const { return current!=NULL;} //判是否遍历完
const Type& operator()() const ; //访问当前结点,可读、写
protected: //可继承的保护成员
const binaryTree<Type>& t; //被遍历的二叉树
const binTreeNode<Type>* current; //当前遍历位置
private: //不可继承的私有成员
treeIterator(const treeIterator & ){} //复制构造函数
treeIterator& operator=(const treeIterator& )const; //遍历器的赋值函数
};
template<class Type>const Type& treeIterator<Type>::operator()()const{
if(current==NULL){cerr<<"Illegal access"<<endl; exit(1);}
return current->getData(); //调用二叉树结点类的成员函数返回当前位置的数据值
} //必须在二叉树及其结点类定义中申明遍历器类为其友类
template <class Type> struct stackNode{ //在遍历时所用栈结点类定义
const binTreeNode<Type>* node; //指向树结点的指针
int popTim ; //该结点退栈的次数
stackNode(const binTreeNode<Type>* N=NULL):node(N), popTim(0){} //构造函数
};
template<class Type> class postOrder:public treeIterator <Type>{ //派生类:后序游标类
public:
postOrder(const binaryTree <Type>& BT ) ; //构造函数
~postOrder(){} //析构函数
void first(); //定位到后序下的第一个结点
void operator++(); //定位到后序下的下一个结点
protected:
stackArray<stackNode<Type> > st; //遍历时用到的工作栈
};
//基树BT、当前位置current、判遍历完+()、访问当前结点()()均继承父类,重新定义的构造函数Postorder和函数first()和operator++()重载如下:
template<class Type>postOrder<Type>::postOrder(const binaryTree<Type>&BT):
treeIterator<Type> (BT){} //调用父类构造函数构造无名对象
//treeIterator <Type> ( BT){st.push(stackNode <Type> ( t.getRoot()));} //工作栈空
//构造函数,初始化时调用父类的构造函数生成遍历器对象,基树的根指针压入工作栈
//treeIterator <Type> ( BT){current=t.getRoot();} //当前指针指向基树的根节点或空
template<class Type>void postOrder <Type>::first(){ //初始化函数
st.makeEmpty(); //再次用时需置空工作栈
if(t.getRoot()!=NULL)st.push(stackNode <Type>(t.getRoot())); //根结点进栈,退栈计数0
operator++(); //调用++()
}
//完成后current指向树的最左下结点退栈计数3,栈中为一路压入的结点（退栈计数均为0）
template<class Type>void postOrder<Type>::operator++(){ //下一个函数
if ( st.isEmpty()){ //当栈空且current亦为空,出错
if(current==NULL){cerr<<"Advanced past end"<<endl; exit (1);}
current=NULL; return; //仅栈空,遍历完成,置当前位置指针为空,返回
}
stackNode<Type> cNode ; //否则
for(;;){ //循环,一路向左下
cNode=st.pop(); //退出一个栈顶元素
if(++cNode.popTim==3) //若退栈计数为3,已到下一个结点,
{current=cNode.node;return;} //当前指针指到该结点,返回
st.push(cNode); //否则,再进栈
if(cNode.popTim==1){ //若退栈计数为1,
if(cNode.node->getLeft() !=NULL) //且结点左子女存在
st.push(stackNode<Type>(cNode.node-> getLeft())); //令其进栈,退栈计数0
}
else{ //若退栈计数为2,
if(cNode.node->getRight()!=NULL) //且结点右子女存在
st.push(stackNode<Type>(cNode.node-> getRight())); //令其进栈,退栈计数0
}
}
}
template<class Type>class inOrder:public postOrder <Type>{ //中序游标类的定义
public:
inOrder(binaryTree<Type>& BT):postOrder<Type>(BT){ } //调用后序构造函数
//void first(); 调用父类构造函数构造无名对象
//可继承后序的,但调用的是重载的中序++(),完成后current也指向基树最左下结点
void operator++();
};
template<class Type>void inOrder<Type>::operator++(){
if(st.isEmpty()){ //当栈空且current亦为空,出错
if(current==NULL){cerr<<"Advanced past end"<<endl; exit (1);}
current=NULL; return; //仅栈空,遍历完成,current置空后返回
}
stackNode<Type> cNode;
for( ; ;){ //循环,一路向左下
cNode=st.pop(); //退出一个栈顶元素
if(++cNode.popTim==2){ //若退栈计数为2,左子树已遍历
current=cNode.node; //当前指针指到它
if(cNode.node->getRight()!=NULL) //若右子树非空,随后应遍历
st.push(stackNode<Type>(cNode.node->getRight()));//右子树根指针压栈
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -