6-1 写出用广义表表示法表示的树的类声明，并给出如下成员函数的实现：
(1) operator >> ( ) 接收用广义表表示的树作为输入，建立广义表的存储表示；
(2) 复制构造函数 用另一棵表示为广义表的树初始化一棵树；
(3) operator == ( ) 测试用广义表表示的两棵树是否相等；
(4) operator << ( ) 用广义表的形式输出一棵树；
(5) 析构函数 清除一棵用广义表表示的树。
【解答】
#include
#define maxSubTreeNum 20; //最大子树(子表)个数
class GenTree; //GenTree类的前视声明
class GenTreeNode { //广义树结点类的声明
friend class GenTree;
private:
int utype; //结点标志：=0, 数据; =1, 子女
GenTreeNode * nextSibling; //utype=0, 指向第一个子女;
//utype=1或2, 指向同一层下一兄弟
union { //联合
char RootData; //utype=0, 根结点数据
char Childdata; //utype=1, 子女结点数据
GenTreeNode *firstChild; //utype=2, 指向第一个子女的指针
}
public:
GenTreeNode ( int tp, char item ) : utype (tp), nextSibling (NULL)
{ if ( tp == 0 ) RootData = item; else ChildData = item; }
//构造函数：构造广义表表示的树的数据结点
GenTreeNode ( GenTreeNode *son = NULL ) : utype (2), nextSibling (NULL), firstChild ( son ) { }
//构造函数：构造广义表表示的树的子树结点
int nodetype ( ) { return utype; } //返回结点的数据类型
char GetData ( ) { return data; } //返回数据结点的值
GenTreeNode * GetFchild ( ) { return firstChild; } //返回子树结点的地址
GenTreeNode * GetNsibling ( ) { return nextSibling; } //返回下一个兄弟结点的地址
void setInfo ( char item ) { data = item; } //将结点中的值修改为item
void setFchild ( GenTreeNode * ptr ) { firstChild = ptr; } //将结点中的子树指针修改为ptr
void setNsinbilg ( GenTreeNode * ptr ) { nextSibling = ptr; }
};
class GenTree { //广义树类定义
private:
GenTreeNode *first; //根指针
char retValue; //建树时的停止输入标志
GenTreeNode *Copy ( GenTreeNode * ptr ); //复制一个ptr指示的子树
void Traverse ( GenListNode * ptr ); //对ptr为根的子树遍历并输出
void Remove ( GenTreeNode *ptr ); //将以ptr为根的广义树结构释放
friend int Equal ( GenTreeNode *s, GenTreeNode *t ); //比较以s和t为根的树是否相等
public:
GenTree ( ); //构造函数
GenTree ( GenTree& t ); //复制构造函数
~GenTree ( ); //析构函数
friend int operator == ( GenTree& t1, GenTree& t2 ); //判两棵树t1与t2是否相等
friend istream& operator >> ( istream& in, GenTree& t ); //输入
friend ostream& operator << ( ostream& out, GenTree& t ); //输出
}
(1) operator >> ( ) 接收用广义表表示的树作为输入，建立广义表的存储表示
istream& operator >> ( istream& in, GenTree& t ) {
//友元函数, 从输入流对象in接受用广义表表示的树，建立广义表的存储表示t。
t.ConstructTree ( in, retValue );
return in;
}
void GenTree :: ConstructTree ( istream& in, char& value ) {
//从输入流对象in接受用广义表表示的非空树，建立广义表的存储表示t。
Stack st (maxSubTreeNum); //用于建表时记忆回退地址
GenTreeNode * p, q, r; Type ch;
cin >> value; //广义树停止输入标志数据
cin >> ch; first = q = new GenTreeNode ( 0, ch ); //建立整个树的根结点
cin >> ch; if ( ch == ‘(’ ) st.Push ( q ); //接着应是‘(’, 进栈
cin >> ch;
while ( ch != value ) { //逐个结点加入
switch ( ch ) {
case ‘(’ : p = new GenTreeNode ( q ); //建立子树, p->firstChild = q
r = st.GetTop( ); st.Pop( ); //从栈中退出前一结点
r->nextSibling = p; //插在前一结点r之后
st.Push( p ); st.Push( q ); //子树结点及子树根结点进栈
break;
case ‘)’ : q->nextSibling = NULL; st.pop( ); //子树建成, 封闭链, 退到上层
if ( st.IsEmpty ( ) == 0 ) q = st.GetTop( ); //栈不空, 取上层链子树结点
else return 0; //栈空, 无上层链, 算法结束
break;
case ‘,’ : break;
default : p = q;
if ( isupper (ch) ) q = new GenTreeNode ( 0, ch ); //大写字母, 建根结点
else q = new GenTreeNode ( 1, ch ); //非大写字母, 建数据结点
p->nextSibling = q; //链接
}
cin >> ch;
}
}
(2) 复制构造函数 用另一棵表示为广义表的树初始化一棵树；
GenTree :: GenTree ( const GenTree& t ) { //共有函数
first = Copy ( t.first );
}
GenTreeNode* GenTree :: Copy ( GenTreeNode *ptr ) {
//私有函数，复制一个ptr指示的用广义表表示的子树
GenTreeNode *q = NULL;
if ( ptr != NULL ) {
q = new GenTreeNode ( ptr->utype, NULL );
switch ( ptr->utype ) { //根据结点类型utype传送值域
case 0 : q->RootData = ptr->RootData; break; //传送根结点数据
case 1 : q->ChildData = ptr->ChildData; break; //传送子女结点数据
case 2 : q->firstChild = Copy ( ptr->firstChild ); break; //递归传送子树信息
}
q->nextSibling = Copy ( ptr->nextSibling ); //复制同一层下一结点为头的表
}
return q;
}
(3) operator == ( ) 测试用广义表表示的两棵树是否相等
int operator == ( GenTree& t1, GenTree& t2 ) {
//友元函数 : 判两棵树t1与t2是否相等, 若两表完全相等, 函数返回1, 否则返回0。
return Equal ( t1.first, t2.first );
}
int Equal ( GenTreeNode *t1, GenTreeNode *t2 ) {
//是GenTreeNode的友元函数
int x;
if ( t1 == NULL && t2 == NULL ) return 1; //表t1与表t2都是空树, 相等
if ( t1 != NULL && t2 != NULL && t1->utype == t2->utype ) { //两子树都非空且结点类型相同
本文档为【写出用广义表表示法表示的树的类声明】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483