数据结构实验报告

1、数据结构课程实验报告题 目： 互联网域名查询 姓 名： 学 院：信息科学与工程学院 班 级： 学 号： 26实验三 树和图应用类实验一、 问题定义及i需求分析1.问题描述互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域，如cn、com等，最底层（第四层）是叶子结点，如www等。因此，域名搜索可以看成是树的遍历问题。2. 实验要求设计搜索互联网域名的程序。（1）采用树的孩子兄弟链表等存储结构。（2）创建树形结构。（3）通过深度优先遍历搜索。（4）通过层次优先遍历搜索。3.数据输入的形式输入域名地址。如：4.数据输出的形式输出对应的ip地址或者出错时输出“找不到服务器或发生DN

2、S错误”二、概要设计（1）为了实现上述程序的功能，应该以孩子兄弟链表存储树，所以需要树的抽象数据类型。（2）存入磁盘文件时还需要另一种文件的抽象数据类型。（3）所有的域名和IP都是以串的形式存的，所以还需要串的抽象数据类型。（4）当用户输入站点的域名时，需要将域名分段存储，在搜索时从最根部依次提出来与树的节点域比较，由于用户输入是从最小级到最根级，弹出时与输入顺序相反，比如输入“”，其中：www是第三级，163是第二级，com是第一级，所以再与树节点比较时，首先比较com，然后比较163，最后才比较www。根据这种“后进先出”的关系，需要栈作为辅助工具，所以需要栈的抽象数据类型。具体内容：1）

3、树的抽象数据类型ADT Tree 数据对象D：站点域名的集合。数据关系R：H（1）D中存在惟一称为根的数据元素root，它在关系H下没有前驱。（2）D-root之后可划分为D1,D2,Dn（n>0）对任意的划分都两两不相交。对任意的i（1in），惟一的存在数据元素，有；（3）对应于D-root的划分，H-root ，Xi（i=1,2,n）有惟一的一个划分H1,H2,Hn （n>0），对任意的(ij,kn)有，并且对任意的i（1in）, 是Di上的二元关系，（Di，Hi）是一颗符合本定义的树，成为根root的子树。基本操作P：CreateChild（&T）初始条件：树根T已经

4、存在。操作结果：根据用户输入的域名建立此域名的树链，并以T为树根如用户输入，则在建立起以T为根，cn为T的第一个孩子，www为叶子的树链，所有的节点都链在孩子域。InitialTree（&T）操作结果：通过用户输入的数据，构造域名树。其实是将建好的域名树链有序地插到树中相应的位置。Insert（&T）初始条件：树T已经存在。操作结果：插入新的域名及IP。CreateTree（&T, *fp）初始条件：包含树的信息文件已经存在，fp 为指向文件的指针。操作结果：通过从文件中读取数据，构造域名树。DeleteTree（&T）初始条件：T已经存在。操作结果：销毁树，释

5、放空间。 ADT Tree2）文件的抽象数据类型ADT File 数据对象：D =aiaiElemSet, i1,2,n, n0数据关系：R =ai-1,aiai-1,aiD, i1,2,n基本操作：Save（&T）初始条件：树T存在。操作结果：先序遍历树，给叶子节点数据域赋IP值，同时把相关信息存入文件。 ADT File3）串的抽象数据类型ADT String 数据对象：D =aiaiElemSet, i1,2,n, n0数据关系：R =ai-1,aiai-1,aiD, i1,2,n基本操作：CopyChar（&s, *a）初始条件：a是字符串常量。操作结果：生成一个其值等

6、于a的串s。CopyStr（&s, a）初始条件：a是一个串。操作结果：生成一个值等于a的串s。CompareStr（a, b）初始条件：a和b是两个串。操作结果：若a>b返回值>0;若a=b,返回值=0;若a<b，返回值<0。DeleteString（&s）初始条件：串s存在。操作结果：销毁串。 ADT String4）栈的抽象数据类型ADT Stack 数据对象：D =aiaiElemSet, i1,2,n, n0数据关系：R =ai-1,aiai-1,aiD, i1,2,n约定为栈底，为栈顶基本操作：InitialStack（&s）操作结果

7、：构造一个空栈。GetTop（s，&e）初始条件：栈s已经存在且非空。操作结果：用e返回栈s的栈顶元素。Push（&s, e）初始条件：栈s已经存在且非空。操作结果：插入元素e为新的栈顶元素。Pop（&s, &e）初始条件：栈s已经存在且非空。操作结果：删除栈s的栈顶元素，并用e返回其值。DeleteStack（&s）初始条件：s已经存在。操作结果：销毁栈，释放空间。 ADT Stack5）本程序5个模块本程序有5个模块：主程序模块，树模块（实现树抽象数据类型），文件模块（实现文件抽象数据类型），串模块（实现串抽象数据类型），栈模块（实现栈抽象数据类型）

8、三、详细设计typedef unsigned char String30;/ 存放域名和IP的串结构typedef struct TreeNode / 树的节点ElemType data,IP;/ 数据域（用来放域名）和IP域（用来放IP）struct TreeNode *firstchild,*nextsibling;/ 指向孩子和兄弟的指针/ 兄弟表示同一层，孩子表示下一层 TreeNode,*Tree;typedef struct FileNode / 存入文件的节点ElemType data,IP;/ 数据域（用来放域名）和IP域（用来放IP）int ltag,rtag;/ 左右标志域

9、：0表示无孩子，1表示有孩子 FileNode;typedef struct SNode / 用户输入的域名存在栈节点SElemType data;/ 数据域（用来存放域名被 '.' 分开的一部分struct SNode *next;/ 指针域，指向域名下一部分 SNode,*Stack;（1）基本操作Stack CreateWeb（） / 用户输入域名时按 '.' 将域名分开分别放入链式栈中/ 最后将 "root" 入栈，为查找做准备，返回栈顶指针CopyChar（root,"root"）;/ 把 "root&

10、quot; 的值赋给串rootInitialStack（webside）;/ 初始化链式栈do a =getchar（）;/ 输入域名for （int i=0;a!='.'&&a!='n'i+）si=a; a=getchar（）;/ 得到两个 '.' 间的域名，将其值放入一个串中si='0'Push（webside,s）;/ 将串的值入栈 while（a!='n'）;Push（webside,root）;/ 将root入栈return webside;/ 返回栈顶的指针 / CreateWebvoi

11、d Search（Tree T,Stack &webside,Tree &p）/ 用递归算法通过域名查找相应的IP，返回相同层的指针/ 若存在则输出IP，若不存在则输出相应的出错信息if （T&&webside->next!=NULL）GetTop（webside,s）;/ 取得域名栈顶元素int t=CompareStr（s,T->data）;/ 比较域名和树的数据域if （t>0） Search（T->nextsibling,webside,p）;/ 若域名比树节点值大则递归搜索树节点兄弟else if（t=0）Pop（webside

12、,s）; p=T;/ 若域名和树节点相同则域名链式栈节点出栈Search（T->firstchild,webside,p）;/ 继续搜索树节点的孩子，即下一层 / end else / end if / Search（2）关于树的操作void CreateChild（Tree &T,Stack &webside） / 用户输入一个网址域名，域名已经被输入到栈中，为域名建立相应的域名树链if（webside->next!=NULL）t=new TreeNode;/ 新开一个节点Pop（webside,s）;/ 从栈中取出域名第一部分CopyStr（t->data

13、,s）;/ 把第一部分赋值给树节点的数据域t->firstchild=t->nextsibling=NULL;/ 把树节点的孩子和兄弟链域暂置空t->IP0='0'/ 把树节点的IP域置0T->firstchild=t;/ 让根节点的孩子域指向新建的树节点CreateChild（t,webside）;/ 再以此树节点为根建立新的树节点，/ 直到把域名全部赋值到树节点中去if（t->firstchild=NULL）cout<<"请输入域名IP"<<endl;/ 若是叶子节点则要求用户输入IPcin>&

14、gt;t->IP; / end if / end if / CreateChildvoid Insert（Tree &T）/ 将域名树链插入到树T中do cout<<"请输入站点域名:"<<endl;webside=CreateWeb（）;/ 为用户输入的域名建立链表栈Search（T,webside,p）;/ 在树中查找与域名节点相同的节点，/ 每一部分查找相匹配的树节点，返回指向/ 最后一个与域名节点相同的树节点的指针if（p->firstchild=NULL）if（p->IP0!='0'）/ 若发现输入

15、了重复的域名则给出提示cout<<"你输入了重复的域名"<<endl;else CreateChild（p,webside）;/ 若这个树节点没有孩子，则直接把新的/ 域名建立成新的树，并让这个树节点孩/ 子域指向次新开的域名树。/ 即将域名节点作为此树节点的第一个孩子 / end ifelse if（webside->next=NULL）/ 若发现输入了错误的域名，则给出相应/ 的提示cout<<"你输入了错误的域名!"<<endl;else GetTop（webside,s）;/ 若这个树节点有孩

16、子，则在他的孩子的/ 兄弟中找到新开域名树应该插入的位置，将其插入t=p->firstchild;a=CompareStr（t->data,s）;/ 比较域名与已经存在的兄弟节点if（a>0）CreateChild（p,webside）;/ 若域名比兄弟节点小，则前插p->firstchild->nextsibling=t; / end ifelse while（t->nextsibling!=NULL&&（a=CompareStr（t->nextsibling->data,s）<0）t=t->nextsibling;

17、/ 若域名比兄弟节点大，则后插q=new TreeNode;Pop（webside,s）;CopyStr（q->data,s）;q->firstchild=NULL;q->IP0='0'/ 给新开节点赋值q->nextsibling=t->nextsibling;/ 新开节点的兄弟指针指向插入处节/ 点的兄弟t->nextsibling=q;/ 插入处的节点的兄弟指针指向新开节点CreateChild（q,webside）;/ 把整个域名树链插入 / end else / end else / end elseDeleteStack（webs

18、ide）;cout<<"是否要继续输入新域名?（y/n）"<<endl;ch=getchar（）;/ 获得用户输入的字符getchar（）;/ 此为用户输入的回车 while（ch='y'）; / Insertvoid InitialTree（Tree &T）/ 第一次由用户输入网站域名和IP，建立节点有序的树T=new TreeNode;/ 新开一个树节点CopyChar（T->data,"root"）;/ 建立树的根节点T->firstchild=T->nextsibling=NULL

19、;T->IP0='0'Insert（T）;/ 把新的域名树链插入树中 / InitialTreevoid CreateTree（Tree &T,FILE *fp）/ 文件已经存在，从文件中读出数据，用递归算法先序遍历构建树的孩子，兄弟二叉链表结构if（!feof（fp）T=new TreeNode;/ 新建树节点f=new FileNode;/ 新建文件节点用于读取磁盘文件中的数据if（fread（f,sizeof（struct FileNode）,1,fp）!=1）cout<<"无法打开文件!"<<endl;CopyS

20、tr（T->data,f->data）;CopyStr（T->IP,f->IP）;/ 将文件节点的IP的值赋给树节点IPif（f->ltag）CreateTree（T->firstchild,fp）;/ 若树节点有孩子则递归建立其孩子else T->firstchild=NULL;/ 若无孩子则孩子链域置为空if（f->rtag）CreateTree（T->nextsibling,fp）;/ 若树节点有兄弟则递归建立其兄弟else T->nextsibling=NULL;/ 若无兄弟则兄弟链域置为空delete f; / end if

21、 / CreateTreevoid DeleteTree（Tree &T）/ 用递归算法销毁树，释放空间if（T）DeleteTree（T->firstchild）;/ 销毁树的左子树DeleteTree（T->nextsibling）;/ 销毁树的右子树delete T;/ 销毁树的根节点 / end if / DeleteTree（3）串的操作void CopyStr（String &a,String b）/ 将串b的值赋给串afor（int i=0;bi!='0'i+） ai=bi;/ 将b数组中的值一个一个赋给aai='0'

22、/ CopyStrvoid CopyChar（String &a,char* b）/ 将字符串b的值赋给串afor（int i=0;*b!='0'b+,i+） ai=*b;ai='0' / CopyStrint CompareStr（String a,String b） / 串a和b从第一个字符开始比较，直到出现第一个不相同的字符为止for（int i=0;ai!='0'&&bi!='0'i+）/ 如果a>b,return >0;if（ai!=bi） return ai-bi;/ 如果a<

23、b,return <0;if（ai!='0'） return 1;/ 如果a=b,return =0;else if（bi!='0'） return -1;else return 0; / CompareStr（4）栈的基本操作void InitialStack（Stack &s）/ 初始化空栈s=new SNode;/ 新建一个栈头节点s->next=NULL;/ 头节点指向空 / InitialStackvoid Push（Stack &s,SElemType e）/ 将元素e插入链式栈中，成为新的栈顶元素p=new SNode;

24、/ 为新的栈顶元素分配空间CopyStr（p->data,e）;/ 将e的值赋给新节点数据域p->next=s->next;/ 插入新的栈顶元素s->next=p;/ 修改栈顶指针 / Pushvoid Pop（Stack &s,SElemType &e） / 若栈为空则给出相应的信息，若不空则删除栈顶元素并将其值赋给e if（!s->next） cout<<"空栈!"<<endl;/ 栈空，给出信息CopyStr（e,s->next->data）;/ 取出栈顶元素的值赋给ep=s->n

25、ext;/ 删除栈顶元素s->next=p->next; delete p;/ 释放空间 / Popvoid GetTop（Stack& s,SElemType &e） / 将栈顶元素的值赋给e，但不删除栈顶元素if（!s->next）cout<<"空栈!"<<endl;else CopyStr（e,s->next->data）; / GetTopvoid DeleteStack（Stack &s）/ 将栈的链表节点一个一个删掉while（s->next!=NULL）p=s->next

26、;s->next=p->next ;delete p; / end whiledelete s; / DeleteStack（5）文件的操作void Save（Tree T,FILE *fp） / 用递归算法先序遍历树，为每一个节点建立一个对应的文件节点。/ 文件节点的数据域存储和树节点相同的数据，/ 文件节点的左右标志域分别表示树节点是否有孩子或兄弟if（T）f=new FileNode;/ 建立新的文件节点CopyStr（f->data,T->data）;/ 将树节点的数据域赋给文件节点数据域f->ltag=（T->firstchild=NULL?0:1

27、）;/ 给文件节点左标志赋值：0表示无孩子节点f->rtag=（T->nextsibling=NULL?0:1）;/ 给文件节点右标志赋值：0表示无兄弟节点CopyStr（f->IP,T->IP）; if（fwrite（f,sizeof（struct FileNode）,1,fp）!=1）cout<<"无法打开文件!"<<endl;/ 将文件节点的值写入磁盘delete f; Save（T->firstchild,fp）;/ 将左孩子树保存入文件Save（T->nextsibling,fp）;/将右兄弟子树保存文件

28、 / end if / Save（6）主函数Main（）a=getchar（）;/ 用户输入选择switch（a）case '1': / 1表示输入域名和IP建立树if（!（fp=fopen（"Internet","wb"） cout<<"无法打开文件!"<<endl;/ 打开文件InitialTree（T）;/ 初始化建立树Save（T,fp）;/ 将树以文件形式保存fclose（fp）;DeleteTree（T）;/ 删除树break;case '2':/ 2表示将用户输入的

29、新域名和IP插入已有树中if（fp=fopen（"Internet","rb"）=NULL） cout<<"无法打开文件!"<<endl;/ 打开文件并读取CreateTree（T,fp）;/ 从文件读取数据建立树fclose（fp）;/ 关闭文件if（!（fp=fopen（"Internet","wb"） cout<<"无法打开文件!"<<endl;/ 打开文件并写入Insert（T）;/ 将新的域名IP插入Save（T,fp

30、）;/ 将新的树保存到文件中fclose（fp）;/ 关闭文件break;case '3':/ 3表示查询用户输入的域名相应得IPif（fp=fopen（"Internet","rb"）=NULL） cout<<"无法打开文件!"<<endl;/ 打开并读取文件CreateTree（T,fp）;/ 根据文件建立树fclose（fp）;/ 关闭文件do cout<<"输入你想搜索的域名（请注意大小写）:"<<endl;webside=CreateWeb（

31、）;/ 建立域名树链Search（T,webside,p）;/ 查找域名if（p->firstchild=NULL&&webside->next=NULL） cout<<p->IP<<endl;else cout<<"无法找到服务器或DNS错误!"<<endl;cout<<"是否继续查询? y/n"<<endl;a=getchar（）;getchar（）; while（a='y'）;if（a='n'） control=

32、0;DeleteTree（T）;break;case '4': default:/ 4表示退出,其他的也退出control=0;break; / end switch / main四、调试分析1）基本操作算法的时间复杂度通过用户输入域名建立域名链表的函数CreateWeb是将域名按 '.' 分开入栈，时间复杂度为O(m），m是域名分的m个串。通过域名查询IP的函数Search是一个递归函数，通过和每个节点比较来搜索，由于树的同一层节点是升序排列的，所以一旦比较到域名比树节点小就退递归，因此可以节省时间，一般的时间复杂度为O(h），h为树高。但最坏时要把每个树节点

33、都遍历一遍。（2）树的操作算法的时间复杂度构造域名树链的算法CreateChild由用户输入网站域名，建立每个域名的树链是一个递归函数，通过先序遍历树的时间复杂度为O(n），n为域名长，比如域名的域名长是3。构造树的算法InitialTree把域名树链插入树中的相应位置，主要操作是插入算法Insert：若域名节点比树中要插入的那一层节点都小则时间复杂度为O(1），比如与比较之后应该插在edu为根的树下，cau比pku小则完成前插操作。若域名节点最大则时间复杂度是O(n），n是兄弟链的长度。从文件中读取数据并且建立树的算法CreateTree是一个递归函数，主要操作是通过先序遍历树读取文件建立树

34、的节点；算法DeleteTree是一个递归删除树的节点的函数，这两个算法的时间复杂度均为O(h），h为树高。（3）串的操作算法的时间复杂度串赋值算法CopyStr和CopyChar的时间复杂度都是O(k），k是串或字符串长。（4）栈的操作算法的时间复杂度初始化栈的算法InitialStack，入栈算法Push，取栈顶元素值的算法GetTop，出栈算法Pop的时间复杂度均为O(1）。删除算法DeleteStack的主要功能是将栈链表的节点一个一个删除，时间复杂度为O(n），n为链表的长度。（5）文件操作算法的时间复杂度建立文件的算法Save是一个递归函数，通过先序遍历树存入文件，主要操作是建立文

35、件节点并存储，时间复杂度为O(h），h为树高。（6）算法的空间复杂度由于InitialTree、Save、CreateTree、Search、DeleteTree都是递归函数，所以都要设栈。因此空间复杂度是O(h），h是树高。五、使用说明第一次程序运行后，用户根据提示输入站点域名和IP，用“回车键”作为间隔，程序将建立树节点，并存入文件。若是用户输入了重复的IP，或是用户输入了不合法的域名，程序会给出相应的提示：（1）用户可以选择插入新的域名IP，或是查询。（2）用户根据提示来输入要查询的站点域名，若此站点在树中存在程序将输出IP，若没有则输出相应的出错信息。 六、测试结果（1）建立树输入 域

36、 名IP域 名IP5568924038553S（提示出错）04903002591731216311210

37、.32.0.93704319733401（2）搜索 输入：输出：9输入：输出：无法找到服务器或DNS错误！七、附录（1）define.h#include <stdio.h>#include <iostream>#define MAXSIZE 400#define ElemType String#define SElemType Stringusing namespace std;/*

38、-typedef-*/typedef unsigned char String30;/ 存放域名和IP的串结构typedef struct TreeNode / 树的节点 ElemType data,IP;/ 数据域（用来放域名）和IP域（用来放IP） struct TreeNode *firstchild,*nextsibling;/ 指向孩子和兄弟的指针/ 兄弟表示同一层，孩子表示下一层 TreeNode,*Tree;typedef struct FileNode / 存入文件的节点 ElemType data,IP;/ 数据域（用来放域名）和IP域（用来放IP） int ltag,rta

39、g;/ 左右标志域：0表示无孩子，1表示有孩子 FileNode;typedef struct SNode / 用户输入的域名存在棧节点 SElemType data;/ 数据域，用来存放域名被'.'分开的一部分 struct SNode *next;/ 指针域，指向域名下一部分 SNode,*Stack;/*-Tree-*/void InitialTree(Tree&);/ 第一次构建树void CreateTree(Tree&,FILE*);/ 从文件中读取数据建立树void CreateChild(Tree &T,Stack &websid

40、e);void DeleteTree(Tree&);/*-String-*/int CompareStr(String,String);/ 比较两个串的大小void CopyStr(String&,String);/ 将一个串的值赋给另一个void CopyChar(String&,char*);/ 将以个字符串的值赋给一个串void DeleteString(String&);/*-Stack-*/void InitialStack(Stack&);/ 初始化栈void Push(Stack&,SElemType);/ 入栈操作void Pop

41、(Stack&,SElemType&);/ 出栈操作void GetTop(Stack&,SElemType&);/ 取栈头节点的值void DeleteStack(Stack&);/*-FileNode-*/void Save(Tree,FILE*);/ 先序遍历树并存储文件Stack CreateWeb();/ 创建用户输入域名的链表void Search(Tree,Stack&,Tree&);/ 搜索域名的IPvoid Insert(Tree&);/*end of define.h*/(2)function.h#includ

42、e <stdio.h>#include <iostream>#include "define.h"using namespace std;/*-String-*/void CopyStr(String &a,String b) int i;/ 将串b的值赋给串a for( i=0; bi!='0' i+) ai=bi; ai='0'void CopyChar(String &a, const char* b) int i;/ 将字符串b的值赋给串a for( i=0; *b!='0' b

43、+,i+) ai=*b; ai='0'int CompareStr(String a,String b) int i;/ 比较串a,b for( i=0; ai!='0'&&bi!='0' i+)/ 如果a>b,return >0; if(ai!=bi)return ai-bi;/ 如果a<b,return <0; if(ai!='0') return 1;/ 如果a=b,return =0; else if(bi!='0')return -1; else return 0;

44、void DeleteString(String s)/ 销毁串 delete s;/*-Tree-*/void CreateChild(Tree &T,Stack &webside)/ 用户输入一个网址域名，域名已经别输入到栈中，为域名建立相应的域名树 String s; if(webside->next!=NULL) Tree t=new TreeNode;/ 新开一个节点 Pop(webside,s);/ 从栈中取出域名第一部分 CopyStr(t->data,s);/ 把第一部分赋值给树节点的数据域 t->firstchild=t->nextsi

45、bling=NULL;/ 把树节点的孩子和兄弟链域暂置空 t->IP0='0'/ 把树节点的IP域置0 T->firstchild=t;/ 让根节点的孩子域指向新建的树节点 CreateChild(t,webside);/ 以此树节点为根建立新的树节点，/ 直到把域名全部赋值到树节点中去 if(t->firstchild=NULL) cout<<"请输入域名IP"<<endl;/ 若是叶子节点则要求用户输入IP cin>>t->IP; void Insert(Tree &T) Stack w

46、ebside; Tree t,q,p=NULL; String s; char ch;/int control=1; do cout<<"请输入站点域名:"<<endl; webside=CreateWeb();/ 为用户输入的域名建立链表栈 Search(T,webside,p);/ 在树中查找与域名节点相同的节点，/ 每一部分查找相匹配的树节点，返回指向/ 最后一个与域名节点相同的树节点的指针 if(p->firstchild=NULL) if(p->IP0!='0'&&webside->next

47、=NULL) cout<<"你输入了重复的域名"<<endl; else CreateChild(p,webside); / 如果这个树节点没有孩子，则直接把新的域名建立成新树，并让这个树节点的孩子域/ 指向次新开的域名树，即将域名节点作为此树节点的第一个孩子 else if(webside->next=NULL) cout<<"你输入了错误的域名!"<<endl; else GetTop(webside,s);/ 如果这个树节点有孩子，则在他的孩子的兄弟中/ 找到新开域名树应该插入的位置，将其插入

48、t=p->firstchild; int a=CompareStr(t->data,s);/ 比较域名与已经存在的兄弟节点 if(a>0) CreateChild(p,webside);/ 若域名比兄弟节点小，则前插 p->firstchild->nextsibling=t; else while(t->nextsibling!=NULL&&(a=CompareStr(t->nextsibling->data,s)<0) t=t->nextsibling;/ 若域名比兄弟节点大，则后插 q=new TreeNode;

49、Pop(webside,s); CopyStr(q->data,s); q->firstchild=NULL; q->IP0='0' q->nextsibling=t->nextsibling; t->nextsibling=q; CreateChild(q,webside); DeleteStack(webside); cout<<"是否要继续输入新域名?（y/n）"<<endl; ch=getchar(); getchar(); while(ch='y');void InitialTree(Tree &T)/ 第一次由用户输入网站域名和IP，建立节点有序的树 T=new TreeNode;/ 新开一个树节点 CopyChar(T->data,"root");/ 建立树的根节点 T->firstchild=T->nextsibling=NULL; T->IP0='0' Insert(T);/