数据结构(c++版)实验参考书

1、前 言数据结构是计算机及相关专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好数据结构的关键。为了更好地配合学生实验，特编写实验指导书。一、实验目的

2、更好的理解算法的思想、培养编程能力。二、实验要求1、 每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。 2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。 3、实验结束后总结实验内容、书写实验报告。 4、遵守实验室规章制度、不缺席、按时上、下机。 5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣10分。 6、实验报告有一次不合格，扣5分，两次以上不合格者，平时成绩以零分记。三、实验环境 Qt或 VC+6.0四、说明 1、本实验的所有算法中元素类型可以根据实际需要选择。 2、实验题目中带者为较高要求，学生

3、可自选；其余部分为基本内容，应尽量完成（至少完成70%，否则实验不合格）。 3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。五、实验报告的书写要求 1明确实验的目的及要求； 2记录实验的输入数据和输出结果； 3说明实验中出现的问题和解决过程； 4写出实验的体会和实验过程中没能解决的问题；六、参考书目 数据结构（C+语言描述） 王红梅等 清华大学出版社DATA STRUCTURE WITH C+ William Ford,William Topp清华大学出版社（影印版）实验一 线性表的操作实验类型：验证性 实

4、验要求：必修实验学时： 2学时一、实验目的：参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法。二、实验要求：1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容：1设计一个静态数组存储结构的顺序表类，要求编程实现如下任务：建立一个线性表，首先依次输人数据元素1，2，3，10，然后删除数据元素6，最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过50个。2设计一个带头结点的单链表类，要求

5、：(1)生成一个整数线性表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。(2)设计一个测试主函数，实际运行验证所设计单链表类的正确性。3设计一个不带头结点的单链表类，要求： (1)不带头结点单链表类的成员函数包括取数据元素个数、插入元素、删除所有值为k的元素、取数据元素。 (提示：要考虑在第一个数据元素结点前插入和删除第一个数据元素结点时与在其他位置插入和删除其他位置结点时的不同情况。)(2)设计一个测试主函数，实际运行验证所设计循环单链表类的正确性。4设计一个带头结点的循环单链表类，实现约瑟夫环问题；问题描述：设编号为1,2,，n(n>0)个

6、人按顺时针方向围坐-圈，每人持有一个正整数密码。开始时任意给出一个报数上限值m从第一个人开始顺时针方向自1起顺序报数。报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1起顺序报数.如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，并给出出列人的编号序列。 测试数据： n=7,7个人的密码依次为3,1,7,2,4,8,4 初始报数上限值m=20*5设计一个带头结点的循环双向链表类，要求：(1)带头结点循环双向链表类的成员函数包括：取数据元素个数、插入、删除、取数据元素。 (2)设计一个测试主函数，实际运行验证所设计循环双向链表类的正确性。

7、*6设计一个单链表实现一元多项式求和问题。要求： （1）设计存储结构表示一元多项式； （2）设计算法实现一元多项式相加。 四、程序样例顺序表类定义：将该类保存在文件SeqList.h中。const int MaxSize=100; /100只是示例性的数据，可根据实际问题具体定义template <class T> /定义模板类SeqListclass SeqListpublic: SeqList( ) length=0; /无参构造函数 SeqList(T a , int n); /有参构造函数 SeqList( ) /析构函数为空 int Length( ) return le

8、ngth; /求线性表的长度 T Get(int i); /按位查找，取线性表的第i个元素 int Locate(T x ); /按值查找，求线性表中值为x的元素序号 void Insert(int i, T x); /在线性表中第i个位置插入值为x的元素 T Delete(int i); /删除线性表的第i个元素 void PrintList( ); /遍历线性表，按序号依次输出各元素private: T dataMaxSize; /存放数据元素的数组 int length; /线性表的长度;template <class T> SeqList: SeqList(T a , in

9、t n) if (n>MaxSize) throw "参数非法" for (i=0; i<n; i+) datai=ai; length=n;template <class T> T SeqList:Get(int i) if (i<1 && i>length) throw "查找位置非法" else return datai-1;template <class T> int SeqList:Locate(T x) for (i=0; i<length; i+) if (datai=x

10、) return i+1; /下标为i的元素等于x，返回其序号i+1 return 0; /退出循环，说明查找失败template <class T> void SeqList:Insert(int i, T x) if (length>=MaxSize) throw "上溢" if (i<1 | | i>length+1) throw "位置"for (j=length; j>=i; j-) dataj=dataj-1; /注意第j个元素存在数组下标为j-1处datai-1=x;length+;template &l

11、t;class T> T SeqList:Delete(int i) if (length=0) throw "下溢" if (i<1 | | i>length) throw "位置" x=datai-1; for (j=i; j<length; j+) dataj-1=dataj; /注意此处j已经是元素所在的数组下标 length-; return x;链表类定义：将该类保存在文件LinkList.h中。template <class T>struct Node T data; Node<T> *nex

12、t; /此处<T>也可以省略template <class T>class LinkListpublic:LinkList( )first=new Node<T> first->next=NULL; /建立只有头结点的空链表 LinkList(T a , int n); /建立有n个元素的单链表LinkList( ); /析构函数int Length( ); /求单链表的长度T Get(int i); /取单链表中第i个结点的元素值int Locate(T x); /求单链表中值为x的元素序号void Insert(int i, T x); /在单链表

13、中第i个位置插入元素值为x的结点T Delete(int i); /在单链表中删除第i个结点void PrintList( ); /遍历单链表，按序号依次输出各元素private:Node<T> *first; /单链表的头指针;template <class T> LinkList: LinkList( ) p=first; /工作指针p初始化 while (p) /释放单链表的每一个结点的存储空间 q=p; /暂存被释放结点 p=p->next; /工作指针p指向被释放结点的下一个结点，使单链表不断开 delete q; template <class

14、T> T LinkList:Get(int i) p=first->next; j=1; /或p=first; j=0; while (p && j<i) p=p->next; /工作指针p后移 j+; if (!p) throw "位置" else return p->data; template <class T> void LinkList:Insert(int i, T x) p=first ; j=0; /工作指针p初始化while (p && j<i-1)p=p->next;

15、/工作指针p后移j+;if (!p) throw "位置"else s=new Node<T> s->data=x; /向内存申请一个结点s，其数据域为xs->next=p->next; /将结点s插入到结点p之后p->next=s; template <class T> T LinkList:Delete(int i) p=first ; j=0; /工作指针p初始化 while (p && j<i-1) /查找第i-1个结点 p=p->next; j+; if (!p | | !p->ne

16、xt) throw "位置" /结点p不存在或结点p的后继结点不存在 else q=p->next; x=q->data; /暂存被删结点 p->next=q->next; /摘链 delete q; return x;template <class T> LinkList: LinkList(T a , int n) first=new Node<T> first->next=NULL; /初始化一个空链表 for (i=0; i<n; i+) s=new Node<T> s->data=ai;

17、 /为每个数组元素建立一个结点 s->next=first->next; /插入到头结点之后 first->next=s; template <class T> LinkList: LinkList(T a , int n) first=new Node<T> /生成头结点 r=first; /尾指针初始化 for (i=0; i<n; i+) s=new Node<T> s->data=ai; /为每个数组元素建立一个结点 r->next=s; r=s; /插入到终端结点之后 r->next=NULL; /单链表建

18、立完毕，将终端结点的指针域置空 1#include <iostream.h> #include<SeqList.h> void main( ) int r =1,2,3,4,5,6,7,8,9,10; SeqList<int> a(r,50); cout<<”执行删除操作前数据为：”<<endl; a.PrintList( ); a.Delete(6); cout<<”执行删除操作后数据为：”<<endl;a.PrintList( ); 2 #include <iostream.h> #includ

19、e<LinkList.h> void divid( LinkList &L) Node<T> *p,*q,*h; h=new Node<T>( ); p=L.first->next; q=L.first; while (p) if(p->data%2!=0) q=p; p=p->next; else q=p; p=p->next; q-next=h.first->next; h.first->next=q; p=L.first->next; while(p->next!=Null) p=p->ne

20、xt; p->next= h.first->next; delete h; void main( ) int r =1,-2,3,-4,-5,6,-7,8,9,10; LinkList<int> List(r, 10); cout<<”执行操作前数据为：”<<endl; List.PrintList( ); divid (List); cout<<”执行操作后数据为：”<<endl;List.PrintList( );6void Add(LinkList<elem> &A, LinkList<el

21、em> B)pre=A.first; p=pre->next; /工作指针p初始化，指针pre始终指向p的前驱结点qre=B.first; q=qre->next; /工作指针q初始化，指针qre始终指向q的前驱结点while（p&&q） if (p->exp<q->exp) /第1种情况 pre=p; p=p->next; else if (p->exp>q->exp) /第2种情况，将结点q插入到结点p之前 v=q->next; pre->next=q; q->next=p; q=v; else

22、/第3种情况 p->coef =p->coef+q->coef; /系数相加 if (p->coef =0) /系数为0，删除结点p和结点q pre->next=p->next; /删除结点p delete p; p=pre->next; else /系数不为0，只删除结点q pre=p; p=p->next; qre->next=q->next /删除结点q delete q; q=qre->next;if (q) pre->next=q; /将结点q链接在第一个单链表的后面delete B.first; /释放第二个单

23、链表的头结点所占的内存实验二 栈、队列、串的操作实验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的：参照给定的栈类和队列类的程序样例，验证给出的栈和队列的常见算法，并结合线性表类实现有关串的操作。二、实验要求：1、掌握栈、队列、串的特点。掌握特殊线性表的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容： 1. 堆栈类测试和应用问题。要求： (1)设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。测试方法为：依次把数据元素1,2,3,4,5入栈，然后出栈堆栈中的数据元素并在屏幕上显示。

24、(2)定义数据元素的数据类型为如下形式的结构体：typedef struct char taskname10;/任务名 int taskno;/任务号 DataType； 设计一个包含5个数据元素的测试数据，并设计一个主函数实现依次把5个数据元素入栈，然后出栈堆栈中的数据元素并在屏幕上显示。2. 队列类测试和应用问题。要求： 设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为：依次把数据元素1,2,3,4,5入队，然后出队中的数据元素并在屏幕上显示。3设计串采用顺序存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有大于、等于和小于三种情况。 *4. 设计算

25、法利用栈类实现把十进制整数转换为二至九进制之间的任一进制输出。 *5. 设计串采用静态数组存储结构，编写函数实现串的替换Replace(S, start, T, V)，即要求在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回。并要求设计主函数进行测试。一个测试例子为：S”I am a student”，T=”student”，V=”teacher “。四、程序样例1 顺序栈类的定义const int StackSize=10; /10只是示例性的数据，可以根据实际问题具体定义template <

26、class T> /定义模板类SeqStackclass SeqStackpublic: SeqStack( ) top=-1; /构造函数，栈的初始化 SeqStack( ) /析构函数 void Push( T x ); /将元素x入栈 T Pop( ); /将栈顶元素弹出 T GetTop( ) if (top!=-1) return datatop; /取栈顶元素（并不删除） bool Empty( ) top=-1? return 1: return 0; /判断栈是否为空private: T dataStackSize; /存放栈元素的数组 int top; /栈顶指针，指示

27、栈顶元素在数组中的下标;template <class T>void SeqStack:Push(T x) if (top= StackSize-1) throw "上溢" top+; datatop=x; template <class T>T SeqStack: Pop( ) if (top=-1) throw "下溢" x=datatop-; return x; 2 链式栈类的定义template <class T>class LinkStackpublic: LinkStack( ) top=NULL; /构造

28、函数，置空链栈 LinkStack( ); /析构函数，释放链栈中各结点的存储空间 void Push(T x); /将元素x入栈 T Pop( ); /将栈顶元素出栈 T GetTop( ) if (top!=NULL) return top->data; /取栈顶元素（并不删除） bool Empty( ) top=NULL? return 1: return 0; /判断链栈是否为空栈private: Node<T> *top; /栈顶指针即链栈的头指针;template <class T> void LinkStack:Push(T x) s=new No

29、de<T> s->data=x; /申请一个数据域为x的结点s s->next=top; top=s; /将结点s插在栈顶 template <class T> T LinkStack:Pop( ) if (top=NULL) throw "下溢" x=top->data; /暂存栈顶元素 p=top; top=top->next; /将栈顶结点摘链 delete p; return x; template <class T> LinkStack:LinkStack( ) while (top) p=top->

30、;next; delete top; top=p; 3双栈类的定义const int StackSize=100; /100只是示例数据，需根据具体问题定义template <class T>class BothStack public: BothStack( ) top1= -1; top2=StackSize; /构造函数，将两个栈分别初始化 BothStack( ) /析构函数 void Push(int i, T x); /将元素x压入栈i T Pop(int i); /对栈i执行出栈操作 T GetTop(int i); /取栈i的栈顶元素 bool Empty(int

31、i); /判断栈i是否为空栈private: T dataStackSize; /存放两个栈的数组 int top1, top2; /两个栈的栈顶指针，分别指向各自的栈顶元素在数组中的下标;template <class T>void BothStack: Push(int i, T x )if (top1=top2-1) throw "上溢"if (i=1) data+top1=x;if (i=2) data-top2=x;template <class T>T BothStack: Pop(int i)if (i=1) /将栈1的栈顶元素出栈if

32、 (top1= -1) throw "下溢" return datatop1-; if (i=2) /将栈2的栈顶元素出栈if (top2=StackSize) throw ''下溢" return datatop2+; 4.循环队列类定义const int QueueSize=100; /定义存储队列元素的数组的最大长度template <class T> /定义模板类CirQueueclass CirQueuepublic: CirQueue( ) front=rear=0; /构造函数，置空队 CirQueue( ) /析构函数

33、void EnQueue(T x); /将元素x入队 T DeQueue( ); /将队头元素出队 T GetQueue( ); /取队头元素（并不删除） bool Empty( ) front=rear? return 1: return 0; /判断队列是否为空private: T dataQueueSize; /存放队列元素的数组 int front, rear; /队头和队尾指针，分别指向队头元素的前一个位置和队尾元素的位置;template <class T> void CirQueue:EnQueue(T x) if (rear+1) % QueueSize =fron

34、t) throw "上溢" rear=(rear+1) % QueueSize; /队尾指针在循环意义下加1 datarear=x; /在队尾处插入元素 template <class T> T CirQueue:GetQueue( ) if (rear=front) throw "下溢" i=(front+1) % QueueSize; /注意不要给队头指针赋值 return datai; template <class T>T CirQueue:DeQueue( ) if (rear=front) throw "下溢

35、" front=(front+1) % QueueSize; /队头指针在循环意义下加1 return datafront; /读取并返回出队前的队头元素，注意队头指针5.链队列类定义template <class T>class LinkQueuepublic: LinkQueue( ); /构造函数，初始化一个空的链队列 LinkQueue( ); /析构函数，释放链队列中各结点的存储空间 void EnQueue(T x); /将元素x入队 T DeQueue( ); /将队头元素出队 T GetQueue( ) if (front!=rear) return fr

36、ont->next->data; /取链队列的队头元素 bool Empty( ) front=rear? return 1: return 0; /判断链队列是否为空private: Node<T> *front, *rear; /队头和队尾指针，分别指向头结点和终端结点;template <class T>T LinkQueue:DeQueue( )if (rear=front) throw "下溢"p=front->next; x=p->data; /暂存队头元素front->next=p->next; /将

37、队头元素所在结点摘链if (p->next=NULL) rear=front; /判断出队前队列长度是否为1delete p; return x;template <class T>LinkQueue:LinkQueue( ) s=new Node<T> s->next=NULL; /创建一个头结点s front=rear=s; /将队头指针和队尾指针都指向头结点stemplate <class T> void LinkQueue:EnQueue(T x) s=new Node<T> s->data=x; /申请一个数据域为x的

38、结点s s->next=NULL; rear->next=s; /将结点s插入到队尾 rear=s; 注意问题1重点理解栈、队列和串的算法思想，能够根据实际情况选择合适的存储结构。 2栈、队列的算法是后续实验的基础（树、图、查找、排序等）。实验三 多维数组和广义表的操作实验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的：参照给定的多维数组类和广义表类的程序样例，验证给出的多维数组和广义表的常见算法，并实现有关的操作。二、实验要求：1、掌握多维数组和广义表的特点。掌握它们的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调

39、试情况、设计技巧、心得体会。三、实验内容： 1.设计函数建立一个n*n阶的对称矩阵。要求：（1）实现将对称矩阵用一维数组存储输出。（2）实现矩阵转置算法。（3）实现魔方阵算法。 (4)设计一个测试例子，并编写主程序进行测试。 2采用链式存储结构设计广义表类，实现以下操作： （1）创建广义表，取广义表的表头元素和表尾元素； （2）求广义表的深度。四、程序样例1稀疏矩阵结构类型声明const int MaxTerm=100; struct SparseMatrix element dataMaxTerm; int mu, nu, tu; /行数、列数、非零元个数 ;template <cla

40、ss T> ruct element int row, col; T item ;2稀疏矩阵转置算法Trans1void Trans1(SparseMatrix A, SparseMatrix &B)B.mu=A.nu; B.nu=A.mu; B.tu=A.tu;/设置行数、列数、非零元素个数if (B.tu>0) /有非零元素则转换 pb=0; for (col=0; col<A.nu; col+) /依次考察每一列 for (pa=0; pa<A.tu; pa+) /在A中扫描整个三元组表 if (A.datapa.col=col ) /处理col列元素 B

41、.datapb.row= A.datapa.col ; B.datapb.col= A.datapa.row ; B.datapb.item= A.datapa.item; pb+; 3稀疏矩阵转置算法Trans2 void Trans2(SparseMatrix A, SparseMatrix &B) B.mu=A.nu; B.nu=A.mu; B.tu=A.tu;/设置行数、列数、元素个数if (B.tu>0) /有非零元素则转换 for (i=0; i<A.nu; i+) /A中每一列非零元素的个数初始化为0numi=0; for (i=0; i<A.tu; i

42、+)/求矩阵A中每一列非零元素的个数 j= A.datai.col; /取三元组的列号 numj+; cpot0=0; /A中第0列第一个非零元素在B中的位置为0for (i=1; i<A.nu; i+) /求A中每一列第一个非零元素在B中的下标cpoti= cpoti-1+numi-1; for (i=0; i<A.tu; i+)/扫描三元组表A j=A.datai.col; /当前三元组的列号 k=cpotj; /当前三元组在B中的下标 B.datak.row= A.datai.col ; B.datak.col= A.datai.row ;B.datak.item= A.da

43、tai.item;cpotj+; /预置同一列的下一个三元组的下标 4魔方阵void Square(int a , int n) p=0; q=(n-1)/2; a0q=1; /在第0行的中间位置填1 for (i=2; i<=n*n, i+) p=(p-1+n) % n; /求i所在行号 q=(q-1+n) % n; /求i所在列号 if (apq>0) p=(p+1) % n; /如果位置(p, q)已经有数，填入同一列下一行 apq=i; 5.广义表类定义enum Elemtag Atom, List; /Atom=0为单元素；List=1为子表template <cl

44、ass T>struct GLNode Elemtag tag; /标志域，用于区分元素结点和表结点 union /元素结点和表结点的联合部分 T data; /data是元素结点的数据域 struct GLNode *hp, *tp; /hp和tp分别指向表头和表尾 ptr; ;template <class T>class Listspublic: Lists( ) ls=NULL; /无参构造函数，初始化为空的广义表 Lists(Lists ls1, Lists ls2); /有参构造函数，用表头ls1和表尾ls2构造广义表 Lists( ); /析构函数，释放广义表中

45、各结点的存储空间 int Length( ); /求广义表的长度 int Depth(GLNode<T> *ls); /求广义表的深度 GLNode *Head( ); /求广义表的表头 GLNode *Tail( ); /求广义表的表尾private: GLNode<T> *ls; /ls是指向广义表的头指针;template <class T> Lists:Lists(Lists ls1,Lists ls2) ls = new GLNodels->tag = 1;ls->ptr.hp = ls1;ls->ptr.tp = ls2; 6求

46、广义表深度算法Depthtemplate <class T> int Lists:Depth(GLNode<T> *ls) if (ls=NULL) return 1; /空表深度为1if (ls->tag=0) return 0; /单元素深度为0max=0; p = ls;while (p) dep = Depth(p->ptr.hp); /求以p->ptr.hp为头指针的子表即表头的深度 if (dep>max) max = dep; p = p->ptr.tp; /准备求表尾的深度return max+1; /非空表的深度是各元素的

47、深度的最大值加1 7取广义表表头算法Headtemplate <class T>GLNode * Lists:Head( ) return ls->ptr.hp;8取广义表表尾算法Tailtemplate <class T>GLNode *Lists:Tail( ) return ls-> ptr.tp;实验四 树和二叉树实验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的：参照给定的二叉树类的程序样例，验证给出的有关二叉树的常见算法，并实现有关的操作。二、实验要求：1、掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。2、提交实验报告，报告内容

48、包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容： 1设计实现二叉树类，要求：（1）编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。（2）实现二叉树层次遍历的非递归算法。 （3）编写一主函数来验证算法实现。 2. 假设二叉树采用链式存储结构进行存储，编写一个算法，输出一个二叉树的所有叶子结点，并统计叶子结点个数。*3. 设计实现二叉线索链表类，要求：（1）编写一个程序，首先建立中序线索链表的二叉树，然后实现

49、中序线索链表的遍历算法。（2）编写一主函数来验证算法实现。*4. 编写求二叉树高度的函数。*5. 编写创建哈夫曼树和生成哈夫曼编码的算法。*6假设二叉树采用链式存储结构进行存储，试设计一个算法，输出从每个叶子结点到根结点的路径。*7假设二叉树采用链式存储结构进行存储，试设计一个算法，求二叉树的宽度（即具有结点数最多的层次上结点总数）四、程序样例二叉树二叉链表结点声明template <class T>struct BiNode T data; BiNode<T> *lchild, *rchild;二叉链表类声明template <class T>class BiTreepublic: BiTree( )root=NULL; /无参构造函数，初始化一棵空的二叉树 BiTree(BiNode<T> *root);