数据结构课程试验报告

1、等中利技次掌课程实验报告课程名称:数据结构计算机科学与技术学院1 课程实验概述1.2 实验一基于顺序结构的线性表实现2.1 问题描述2.2.2 系统设计2.2.3 系统实现7.2.4 效率分析1.1.3 实验二基于链式结构的线性表实现3.1 问题描述 系统设计 系统实现 效率分析2.2.4 实验三基于二叉链表的二叉树实现4.1 问题描述 系统设计 系统实现 效率分析4.3.5 实验总结与评价4.5.1 课程实验概述上机实验是对学生的一种全面综合训练，是与课堂听课、自学和练习相辅相成的必不可少的一个教学环节。实验

2、目的着眼于原理与应用的结合，使学生学会如何把书上的知识用语解决实际问题，能够理解和运用常用的数据结构，如线性表、栈、队列、树、图、查找表等，并在此基础上建立相应的算法；通过上机实验使学生了解算法和程序的区别，培养学生把算法转换为程序的能力，提高学生解决实际问题的能力；学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。2 实验一 基于顺序结构的线性表实现2.1 问题描述编写一个程序，实现顺序表的各种基本运算，并在此基础上完成以下功能1)初始化顺序表；2) 释放顺序表；3) 判断顺序表L是否为空；4)

3、输出顺序表L的长度；5) 输出顺序表L 的第i个元素；6)输出元素e的位置；7)输出元素e的前一个元素；8)输出元素e的后一个元素；9) 在第 i 个元素位置上插入f 元素；10) 删除 L 的第 i 个元素；11)输出顺序表L；12) 保存顺序表L 的数据。2.2 系统设计1、数据类型顺序表：typedef structElemType * elem; /线性表首地址int length;/线性表当前长度int listsize;/线性表最大长度SqList;数据类型：int (可以在头文件中更改数据类型) 输入形式：文件读取、键盘输入输入范围：-2A152A162、函数返回状态判断为真：T

4、RUE 0判断为假：FALSE -1函数正确执行：OK -2函数执行错误：ERROR -3元素不存在：NOTEXIST -4内存分配溢出：OVERFLOW -53、函数设计InitList(&L)操作前提：L 是一个未初始化的线性表。操作结果：将L 初始化为一个空的线性表。DestroyList(&L)操作前提：线性表L 已存在。操作结果：销毁线性表L。ListEmpty(L)操作前提：线性表L 已存在。操作结果：若L为空表，则返回TURE,否则返回FALSE。ListLength(L)操作前提：线性表L 已存在。操作结果：返回L 中数据元素个数。GetElem(L, i,&a

5、mp;e)操作前提：线性表L已存在，1 w i & ListLength (L)。操作结果：用e返回L中第i个元素的值。LocateElem (L,e)操作前提：线性表L 已存在。操作结果：返回L中第一个e的位序。若这样的数据元素不存在，则返回值为0。PriorElem (L,e,&proi)操作前提：线性表L 已存在。操作结果：返回L中第一个e的前一个数据元素。若这样的数据元素不存在，则返回值为0。NextElem (L,e,&next)操作前提：线性表L 已存在。操作结果：返回L中第一个e的后一个的数据元素。若这样的数据元素不存在，则返回值为0。ListInsert

6、 (&L,i ,e)操作前提：线性表 L已存在，1 wi&ListLength (L) +1。操作结果：在L 中第 i 个位置之前插入新的数据元素e， L 的长度 +1。ListDelete (&L,i, e)操作前提：线性表L已存在且非空，1 w i & ListLength (L)。操作结果：删除L 的第 i 个元素数据，并用e 返回其值，L 的长度 1DisplayList(L)操作前提：线性表L 已存在。操作结果：打印表中元素。SaveList(L)操作前提：线性表L 已存在。操作结果：保存表中元素。4、主要函数流程图ProiElem：这里的查找元素操作

7、可直接调用 LocateElem函数返回元素的位置，NextElem 函数的流程图与此相似，这里不在赘述）结束Listinsert:这个函数最主要的部分就是检查参数与元素的移位操作，若参数不合法（传入空线性表、插入位置在线性表之外）极易出现访问数组外元素问题；元素移位操作要在不丢失数据的前提下（从最后一个元素开始）进行。ListDelete删除函数同样最主要的部分就是检查参数与元素的移位操作，若参数不合法（传入空线性表、删除位置在线性表之外）极易出现访问数组外元素问题；元素 移位操作要在不丢失数据的前提下（从被删除的元素开始）进行。2.3 系统实现这里也只给出主要函数的代码，完整代码会在附录给

8、出函数名：LocateElem参数：线性表L、要查找的元素返回值：若元素存在，返回位置，否则返回错误信息函数功能：获取元素的位置status LocateElem(SqList L,ElemType e)if( !L.elem )return ERROR;for( int i=1; i<L.length+1; i+ )if( e = L.elemi ) return i;return NOTEXIST;函数名：PriorElem参数：线性表L、查找的元素、带回元素值的形参返回化函数执行情况成功为 OK,否则ERROR函数功能：获取元素的前继节点元素status PriorElem(SqL

9、ist L,ElemType cur,ElemType & pre_e)/*不可获取线性表长度之外的元素，第0 号元素不用*/if( !L.elem )return ERROR;int pos;pos = LocateElem( L, cur );if( pos<1 )return ERROR;if( pos = 1 )return NOTEXIST;pre_e = L.elempos-1;return OK;函数名：ListInsert参数：线性表L (引用)、要插入的位置及元素返回值：是否插入成功函数功能：插入元素到指定位置status ListInsert(SqList &

10、amp; L,int i,ElemType e)/*不可获取线性表长度之外的元素，第0 号元素不用*/if( !L.elem | i>L.length+1 | i<1 ) return ERROR;if( L.length = L.listsize ) return OVERFLOW;for( int j=L.length+1; j>i; j- )L.elemj = L.elemj-1;L.elemi = e;L.length+;return OK;函数名：ListDelete参数：线性表L (引用)、位置、带回被删除的元素e返回值：是否删除元素成功函数功能：删除指定位置的元

11、素并带回元素status ListDelete(SqList & L,int i,ElemType & e)/*不可获取线性表长度之外的元素，第0 号元素不用*/if( !L.elem | i>L.length | i<1 ) return ERROR;e = L.elemi;for( int j=i; j<L.length; j+ )L.elemj = L.elemj+1;L.length-;return OK;调试分析(1)调试过程中主要遇到哪些问题？是如何解决的？调式过程中发现总是粗心大意忘了加分号或者打错字，所以学习C语言一定要细心仔细，不能着急。用D

12、isplayList函数时出现了问题，后来经过询问同学和查阅书本对程序进行了 改正，使其能够正确进行。(2)经验和体会通过这次上机实验，对顺序表的各功能有了进一步的了解和学习，也对 C语知识进行了巩固。1、2、3、4、5、6、7、8、9。实验结果截图 实验测试数据为: 这里依然只给出主要函数结果。1)查找元素位置：2）查找前继元素：r D:codeblo ckLin eaclj bk b inDe b u gLine rTablMenu fox Linear Table On Sequence StructureIntiaList7, LocateHlemDestroyListS. Prior

13、Ele>CleaxList9, NextElemLi stEnpty10. ListlnsertLi stLengthIL ListDelete氏GetElem12. ListTr abverse13,SaveData0. Esj-tI 请选择你的操作0*3： & 请输入要访问的元素；T 元素吊的前名玩素是由 请输入ENTE唯住续3）插入元素:” D： 118de bl5ck'.LinearTabl ebmDeb ugLinear-Table.eJ<eMenu for Linear Table Cta. Sequence Structure1.IntxaList7.

14、LicateElem2.D号mt工oyLit8.FirioTEl 即3.CLcaiLijts.Nn-t£ln4ListEmp'y10.Listlnsext5.Li目七Length11.ListDelete6.C«tEL«m12,LiutTsrabuoxu。IXSaveDati0.Exit话选择你的谟作。“13kle I清输只想使施人的元素：1。 谑输入想要抽入的位置：10 插入成功！ 请输入ENIE唬续4）删除元素:" Decode blockUn earT atleXbi nC'eb ugLin earTable.exeMenu fox

15、 Lineax Table On.-Sequence Struetriiz-e* 1. In+iaList?,LocateEleJii2.Dc?troyListB.PsrisEl 所3. CleaiListg.NextElen4. ListEwptyID,Listlnsert5> LifftLcngtli11.LiotDoloto% GatElem12.L is tTrab verse13. SaveD.ata).Exiti请选择你的操作。口3：11请满人想要删除的元素位置上 5删除元素E成功！请输入EN7E视续L_ _T"5)遍历线性表：厂” D:'. code bl

16、 ockMinearlable'-b i nDebu gLi nearTa bl e.exe1. IntiaList7.LocateEleni2. DestryL151e.PxzorElcm3. ClesrlList9.NestElem4,. ListEjipty10.ListIdsext6. LifftLsngithii.ListDcletc6. GetElem12.ListTxabvexse13. SarreData0.Exit请选择你的操作。口3：12- -1- all olomontD-1 -> 23 -> 4 "> 6 "> 7 &

17、quot;> 8 -> 9 ->iB语输入EMTE破代续中文阖体）-微软拼音新体险输入风格半：2.4 效率分析由于线性表具有随机访问的特性，所以线性表操作的时间基本来自于线性表的遍历、插入及删除操作。假定线性表中有n 个元素。1）获取元素位置：最好的情况：第一个元素即为所要查找的元素，执行1 次操作；最坏的情况：最后一个元素为要查找的元素，执行n 次操作；若所有元素访问的概率相等，则要执行（n+1） /2 次操作。总体来说时间复杂度为O（n）。2）插入元素：最好的情况：插入到线性表尾，执行1 次操作；最坏的情况：插入到线性表头，执行n 次操作；若所有元素访问的概率相等，则要执

18、行（n+1） /2 次操作。总体来说时间复杂度为O（n）。3）删除元素：最好的情况：删除线性表尾元素，执行1 次操作；最坏的情况：删除线性表头元素，执行n 次操作；若所有元素访问的概率相等，则要执行（n+1） /2 次操作。总体来说时间复杂度为O（n）。结果分析：线性表比较适合经常访问但修改较少的实际运用。3 实验二 基于链式结构的线性表实现3.1 问题描述编写一个程序，实现线性链表的各种基本运算，并在此基础上完成以下功能1)初始化线性链表；2) 释放线性链表；3) 判断线性链表L是否为空；5) 输出线性链表L的长度；5) 输出线性链表L 的第i个元素；6)输出元素e的位置；7)输出元素e的前

19、一个元素；8)输出元素e的后一个元素；9) 在第 i 个元素位置上插入f 元素；10) 删除 L 的第 i 个元素；11)输出线性链表L；12) 保存线性链表L 的数据。3.2 系统设计1、数据类型线性链表：struct LinkListElemType data; /链表元素LinkList *next; / 指向后继节点的指针数据类型：int (可以在头文件中更改数据类型)输入形式：文件读取、键盘输入输入范围：-2A152A162、函数返回状态判断为真：TRUE 0判断为假：FALSE -1函数正确执行：OK -2函数执行错误：ERROR -3元素不存在：NOTEXIST -4内存分配溢出

20、：OVERFLOW -53、函数设计InitList(&L)操作前提：L 是一个未初始化的线性表。操作结果：将L 初始化为一个空的线性表。DestroyList(&L)操作前提：线性表L 已存在。操作结果：销毁线性表L。ListEmpty(L)操作前提：线性表L 已存在。操作结果：若L为空表，则返回TURE,否则返回FALSE。ListLength(L)操作前提：线性表L 已存在。操作结果：返回L 中数据元素个数。GetElem(L, i,&e)操作前提：线性表L已存在，1 w i & ListLength (L)。操作结果：用e返回L中第i个元素的值。Loca

21、teElem (L,e)操作前提：线性表L 已存在。操作结果：返回L中第一个e的位序。若这样的数据元素不存在，则返回值为0。PriorElem (L,e,&proi)操作前提：线性表L 已存在。操作结果：返回L中第一个e的前一个数据元素。若这样的数据元素不存在，则返回值为0。NextElem (L,e,&next)操作前提：线性表L 已存在。操作结果：返回L中第一个e的后一个的数据元素。若这样的数据元素不存在，则返回值为0。ListInsert (&L,i ,e)操作前提：线性表 L已存在，1 wi&ListLength (L) +1。操作结果：在L 中第 i

22、个位置之前插入新的数据元素e， L 的长度 +1。ListDelete (&L,i, e)操作前提：线性表L已存在且非空，1 w i & ListLength (L)。操作结果：删除L 的第 i 个元素数据，并用e 返回其值，L 的长度 1DisplayList(L)操作前提：线性表L 已存在。操作结果：打印表中元素。SaveList(L)操作前提：线性表L 已存在。操作结果：保存表中元素。4、主要函数流程图NextElem:ProiElem 函这里的查找元素操作可直接调用LocateElem函数返回元素的位置,数的流程图与此相似，这里不在赘述）Listinsert:这个函数最

23、主要的部分就是检查参数与节点的插入操作，若参数不合法（传入空线性链表、插入位置在线性链表之外）极易出现访问链表外元素问题；若插 入首节点，要注意修改头指针，插入其他节点注意不要丢失指针， 应先保存后继 节点指针后，再修改前驱节点的后继。州除首元素输出ERRYOR删除位走 .是否合诙ListDelete删除函数同样最主要的部分就是检查参数与节点的删除操作，若参数不合法（传入空线性链表、删除位置在线性链表之外）极易出现访问链表外元素问题； 若删除首节点，要先保存首节点的后继节点，再释放首地址，再修改头指针；删 除其他节点要注意查找到它的前继节点，再修改前继节点的后继，释放节点。/融0K取第咋元素的

24、值取第个元累的地址首地址普空长度- i释独咋元素的空 间长度工3.3 系统实现这里也只给出主要函数的代码，完整代码会在附录给出函数名：LocateElem参数：线性表L、要查找的元素返回值：若元素存在，返回位置，否则返回错误信息函数功能：获取元素的位置status Link:LocateElem(Link L, ElemType e)if( L.head=NULL )return ERROR;int loc = 0;L.cur_p = head;while( L.cur_p ) loc+;if( L.cur_p->data = e ) return loc;L.cur_p = L.cur

25、_p->next;return NOTEXIST;函数名：NextElem参数：线性表L、查找的元素、带回元素值的形参返回化函数执行情况成功为 OK,否则ERROR函数功能：获取元素的后继节点元素status Link:NextElem(Link L, ElemType cur, ElemType &e) if( L.head=NULL )return ERROR;int pos;pos = LocateElem( L, cur );if( pos<1 )return ERROR;if( pos = L.length )return NOTEXIST;GetElem( L,

26、 pos+1, e );return OK;函数名：ListInsert参数：线性表L (引用)、要插入的位置及元素返回值：是否插入成功函数功能：插入元素到指定位置status Link:ListInsert( Link &L, int i, ElemType e )if( i<1 | i>L.length+1 ) return ERROR;if( !L.head )L.head = (LinkList*)malloc( sizeof(LinkList) );if( !L.head )return OVERFLOW;L.head->data = e;L.head-&g

27、t;next = NULL;L.length = 1;return OK;L.cur_p = L.head;for( int j=1; j<i-1; j+ )L.cur_p = L.cur_p->next;if( !L.cur_p ) return ERROR;L.tail = (LinkList*)malloc( sizeof(LinkList) );if( !L.tail )return OVERFLOW;L.tail->data = e;if( i=1 )L.tail->next = L.head;L.head = L.tail; elseL.tail->n

28、ext = L.cur_p->next;L.cur_p->next = L.tail;L.length+;return OK;函数名：ListDelete参数：线性表L （引用）、位置、带回被删除的元素返回值：是否删除元素成功函数功能：删除指定位置的元素并带回元素status Link:ListDelete(Link & L,int i,ElemType & e) if( !L.head | i<1 | i>L.length )return ERROR;L.cur_p = L.head;if( i = 1 )L.head = L.head->nex

29、t;free(L.cur_p);L.length-;return OK;for( int j=1; j<i-1; j+ )L.cur_p = L.cur_p->next;if( !L.cur_p )return ERROR;L.tail = L.cur_p->next;L.cur_p->next = L.cur_p->next->next;free(L.tail);L.tail = NULL;L.length-;return OK;调试分析(1)调试过程中主要遇到哪些问题？是如何解决的？调式过程中发现总是无法插入到首节点，后来发现是没单独考虑首节点的插入操

30、作。用删除t函数时若删除第一个元素就出现异常退出，经调试发现操作的空指针，是未考虑删除首节点导致的。(2)经验和体会通过这次上机实验，对顺序链表的各功能有了进一步的了解和学习，也对 C语知识进行了巩固。实验结果截图实验数据：1、2、3、4、5、6、7、8、91)获取元素位置：2)获取后继元素:3）插入元素: 口 Woe efclcclt,in 吐诂t，. bi r .Debug L.inkLi >t fkfM？/ill for Lineii List On S&cuenre StmcturG1. Inti-sLst2. DestrorList3. ClearLlSt4. List

31、Em5tyE. Li_stLength6. GetElen13. £aveDam工 Lee at eEi sir.8. FriorEleji Kez-tELei»LO. Liffxlasejt 二L ListDelete 12. ListTrabTeise 0. Ejn-t-22 1 7Bs-"P 黜燔&4）删除元素:DXcodetl ockkJn kLi bi r De b j q'- L i n kL i 式 e 促Mnn fox Llmax List On Secuetjce Structme1.IntiaLiiStT,Loe fit eEi

32、 en.DesiZoyListB.FriorEleii3.Cle-arLlsI:包Kez tE 二 em4.ListEmpty10.Listinselt5.ListLengthLLListDelete6.GetElen12.ListTrabverse13.£ aveData0.EklI清选择东的操作。"1打式工 诸轴人想要触条的元素位型S 删除元素丽t门I 谙轴入E1H展塞实5）遍历线性链表:3.4 效率分析由于线性链表不具有随机访问的特性，所以线性表操作的时间都来自于线性表的遍历操作。假定线性表中有n 个元素。1）获取元素位置：最好的情况：第一个元素即为所要查找的元素，执

33、行1 次操作；最坏的情况：最后一个元素为要查找的元素，执行n 次操作；若所有元素访问的概率相等，则要执行（n+1） /2 次操作。总体来说时间复杂度为O（n）。链式结构使得插入，删除操作不需要移动其他元素，只要更改指针指向，所但同时也有一个问题，链表的空间使用效率不是很高，而且一个节点内存储的数据越少，利用率越低。4 实验三 基于二叉链表的二叉树实现4.1 问题描述编写一个程序，实现二叉树的各种基本运算，并在此基础上完成以下功能1)初始化二叉树；2) 释放二叉树；3) 判断二叉树是否为空；6) 输出二叉树的深度；5) 先序遍历二叉树；6) 中序遍历二叉树；7) 后序遍历二叉树；8) 层序遍历二

34、叉树；9) 在二叉树上插入f 元素；10) 删除二叉树的元素e；11)保存二叉树的数据。4.2 系统设计二叉树节点的定义struct BiTreeNodeElemType data; /节点元素BiTreeNode *parents;BiTreeNode *Lson; / 指向左后继节点的指针BiTreeNode *Rson; / 指向右后继节点的指针;队列，层序遍历二叉树时使用struct QueueBiTreeNode *node; / 保存二叉树节点Queue *next;1、数据类型数据类型：int (可以在头文件中更改数据类型)输入形式：文件读取、键盘输入输入范围：-2A152A16

35、2、函数返回状态判断为真：TRUE 0判断为假：FALSE -1函数正确执行：OK-2函数执行错误：ERROR-3元素不存在：NOTEXIST -4内存分配溢出：OVERFLOW -53、函数设计注：所有函数在BiTree 类中实现，所以函数没传根指针InitBiTree()操作前提：B 是一个未初始化的二叉树。操作结果：将B 初始化为一个空的二叉树。DestroyBiTree()操作前提：二叉树B 已存在。操作结果：销毁二叉树B。BiTreeEmpty()操作前提：二叉树B 已存在。操作结果：若B为空树，则返回TURE,否则返回FABSE。BiTreeDepth()操作前提：二叉树B 已存在

36、。操作结果：返回B 的深度。GetRoot()操作前提：二叉树B 已存在。操作结果：返回二叉树的根指针。Value (e)操作前提：二叉树B已存在，e是二叉树中的某个节点。操作结果：返回节点e的数据。Assign (&e， valuei)操作前提：二叉树B已存在，e是B中的一个节点。操作结果：节点e 的值改为value。Parent(e)操作前亚：二叉树B已存在，e是B中的一个节点。操作结果：返回e 的双亲节点。LeftChild(e)操作前提：二叉树B已存在，e是B中的一个节点。操作结果：返回e 的左子树根节点。RightChild(e)操作前提：二叉树B已存在，e是B中的一个节点。

37、操作结果：返回e 的右子树根节点。LeftSibling(e)操作前提：二叉树B已存在，e是B中的一个节点。操作结果：返回e的左兄弟节点，若e为B左子树，则返回空RightSibling(e)操作前提：二叉树B已存在，e是B中的一个节点。操作结果：返回e的右兄弟节点，若e为B右子树，则返回空BiTreeInsert (e)操作前提：二叉树B 已存在。操作结果：在B 中插入新的数据元素e。BiTreeDeBete (e)操作前提：二叉树B 已存在且非空。操作结果：删除B 的元素数据e。PreOrderTraverse()操作前提：二叉树B 已存在。操作结果：先序遍历二叉树。InOrderTrav

38、erse()操作前提：二叉树B 已存在。操作结果：中序遍历二叉树。PostOrderTraverse()操作前提：二叉树B 已存在。操作结果：后序遍历二叉树。LevelOrderTraverse()操作前提：二叉树B 已存在。操作结果：层序遍历二叉树。SaveBiTree(B)操作前提：二叉树B 已存在。操作结果：保存表中元素。4、主要函数流程图BiTreeDepth求二叉树的深度最关键的是找到二叉树最底下的一个节点， 这个可由层序遍 历函数获取，层序遍历函数后面会给出；获取二叉树的最后一个节点后，由此节 点开始回溯，每回溯一级，深度加一，直到回到二叉树的根节点，返回深度。BiTreeinse

39、rt由排序二叉树的规则（左子树的所有节点小于根节点，右子树的所有节点大 于根节点）进行插入。从二叉树的根节点开始，如果元素大于节点的值，则递归 插入到右子树，如果元素小于节点的值，则递归插入到左子树；直到到达叶子节 点，记录其双亲节点，申请新的节点存储元素 e,然后将节点连接到二叉树上。BiTreeDelete由搜索函数查找元素e,若没找到，则返回没找到；如果是叶子节点，直接 删除节点；如果是根节点，删除节点，根指针置空；如果不是叶子节点，节点如 果有左子树，则查找左子树的最大节点替换所要删除的节点，节点如果没有左子 树，则查找右子树的最小节点替换所要删除的节点。PreOrderTravers

40、e先访问根节点，再递归访问左子树的根节点，直到左子树为空，如果右子树 存在，再递归访问右子树，若右子树访问完全，则回溯到上一节点，如果上一节 点是其双亲节点的右子树，则一直回溯，直到上一节点是双亲节点的左子树； 如 果其双亲节点没有右子树，再回溯，直到有右子树，如果回溯到了根节点则结束 遍历，否则再递归访问右子树。InOrderTraverse先查找左子树的根节点，直到左子树为空，访问节点，如果右子树存在，再 递归访问右子树，若右子树访问完全，则回溯到上一节点，如果上一节点是其双 亲节点的右子树，则一直回溯，直到上一节点是双亲节点的左子树； 如果其双亲 节点没有右子树，访问节点，再回溯，直到有

41、右子树，如果回溯到了根节点则结 束遍历，否则再递归访问右子树。PostOrderTraverse先查找左子树的根节点，直到左子树为空，如果右子树存在，再递归访问右 子树，若右子树访问完全，访问节点，回溯到上一节点，如果上一节点是其双亲 节点的右子树，访问节点，一直回溯，直到上一节点是双亲节点的左子树；如果 其双亲节点没有右子树，访问节点，再回溯，直到有右子树，如果回溯到了根节 点则结束遍历，否则再递归访问右子树。LevelOrderTraverse层序遍历需要用到队列来辅助实现，首先根节点入队，再出列一个节点，访 问节点，如果有左子树，则左子树入队，如果有右子树，则右子树入队，判断队 列头是否

42、为空，不空则出列，否则结束遍历。4.3 系统实现函数名：BiTreeDepth参数： depth (带回深度值)返回值：是否得到二叉树深度函数功能：求二叉树的深度status BiTree:BiTreeDepth(int &depth)if( !root )return ERROR;/* 根节点入队*/InQueue( root );BiTreeNode *p = NULL;while( queue_head )/* 出列 */if( OutQueue( p ) != OK )return OVERFLOW;if( p->Lson )/* 左子树入队*/InQueue( p-&g

43、t;Lson );if( p->Rson )/* 左子树入队*/InQueue( p->Rson );depth = 0;while( p->parents )p = p->parents;depth+;return OK;函数名：BiTreeInsert参数：元素e返回值：是否插入成功函数功能：插入一个元素到二叉树中status BiTree:BiTreeInsert( ElemType e )/* 如果是一棵空树，创建新的根节点*/if( root = NULL )root = (BiTreeNode *)malloc(sizeof(BiTreeNode);/* 检

44、查存储空间申请是否成功*/if( !root )return OVERFLOW;root->data = e;root->parents = NULL;root->Lson = NULL;root->Rson = NULL;return OK;/* 如果二叉树存在*/BiTreeNode *par = root;BiTreeNode *son = root;/* 查找可以插入的叶子节点*/while( son )if( e > son->data )son = par->Rson;elseson = par->Lson;if( son )par

45、= son;/* 申请新的空间存储数据*/son = (BiTreeNode *)malloc(sizeof(BiTreeNode);if( !son )return OVERFLOW;son->data = e;son->parents = par;son->Lson = NULL;son->Rson = NULL;/* 将新的节点连接到二叉树上*/if( e > par->data )par->Rson = son;elsepar->Lson = son;return OK;函数名：BiTreeDelete参数：元素e返回值：元素删除是否成功

46、函数功能：删除二叉树的一个元素status BiTree:BiTreeDelete( ElemType e )/* 如果是一棵空树*/if( !root )return ERROR;/* 如果二叉树存在*/BiTreeNode *son = NULL;BiTreeNode *cur = root;/* 查找删除节点*/while( cur )if( e > cur->data )cur = cur->Rson;else if( e < cur->data )cur = cur->Lson;elsebreak;/* 如果没有找到节点*/if( !cur )re

47、turn NOTEXIST;/* 如果删除节点没有右子树，* 则将左子树的根节点替换它* 以达到删除节点的目的* /if( cur->Lson )son = cur->Lson;/* 查找左子树的最大节点*/while( son->Rson )son = son->Rson;/* 节点转移 */cur->data = son->data;if( cur->Lson = son )son->parents->Lson = son->Lson;elseson->parents->Rson = son->Lson;if(

48、son->Lson )son->Lson->parents = son->parents;free(son);return OK;else if( cur->Rson ) son = cur->Rson;/* 查找右子树的最小节点*/while( son->Lson )son = son->Lson;/* 节点转移 */cur->data = son->data;if( cur->Rson = son )son->parents->Rson = son->Rson;elseson->parents->

49、;Lson = son->Rson;if( son->Rson )son->Rson->parents = son->parents;free(son);elseif( cur = root ) free(cur);root = NULL; return OK;son = cur;cur = son->parents;if( son = cur->Lson )cur->Lson = NULL; elsecur->Rson = NULL;free(son);return OK;函数名：PreOrderTraverse参数： void返回值：先

50、序遍历是否成功函数功能：先序遍历二叉树status BiTree:PreOrderTraverse()if( !root )return ERROR;BiTreeNode *p = root;while( p )/* 先访问根元素，再一次遍历右子树*/while( p->Lson )visit( p );p = p->Lson;visit( p );/* 如果有右子树，则遍历右子树*/if( p->Rson )p = p->Rson;continue;/* 回溯到右子树未访问的根节点*/while( p->parents )if( p = p->parent

51、s->Rson ) p = p->parents;else break;p = p->parents;/* 如果根节点没有右子树，则再回溯*/while( p && !p->Rson )p = p->parents;/* 遍历右子树*/if( p )p = p->Rson;return OK;函数名：InOrderTraverse参数： void返回值：中序遍历是否成功函数功能：中序遍历二叉树status BiTree:InOrderTraverse()if( !root )return ERROR;BiTreeNode *p = root;

52、while( p )/* 遍历左子树*/while( p->Lson )p = p->Lson;/*访问左子树*/visit( p );/*遍历右子树*/if( p->Rson )p = p->Rson;continue;/* 回溯到右子树未访问的根节点*/while( p->parents )if( p = p->parents->Rson )p = p->parents;elsebreak;p = p->parents;visit(p);*/* 如果根节点没有右子树，则再回溯while( p && !p->Rson

53、 )p = p->parents;visit( p );/* 遍历右子树*/if( p )p = p->Rson;return OK;函数名：PostOrderTraverse参数： void返回值：后序遍历是否成功函数功能：后序遍历二叉树status BiTree:PostOrderTraverse()if( !root )return ERROR;BiTreeNode *p = root; while( p ) /* 遍历左子树*/while( p->Lson )p = p->Lson;/* 遍历右子树*/if( p->Rson )p = p->Rson; continue;visit( p );while( p->parents )/* 若右子树访问完*/if( p = p->parents->Rson )