《2023年数据结构二叉树遍历实验报告.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构二叉树遍历实验报告.pdf（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数 据 结 构 之 二 叉 树 实 验 报 告 题 目:二 叉 树 的 遍 历 和 子 树 互 换 指 导 老 师：杨 政 宇 班 级：通 信 1 2 0 2姓 名:徐 江需 求 分 析 1.演 示 程 序 分 别 用 多 种 遍 历 算 法 遍 历 二 叉 树 并 把 数 据 输 出。2.输 入 字 符 序 列，递 归 方 式 建 立 二 叉 树。3.在 演 示 过 程 序 中，用 户 敲 击 键 盘，输 入 数 据，即 可 看 到 数 据 的 输 出。4.实 现 链 式 存 储 的 二 叉 树 的 多 种 遍 历 算 法。遍 历 算 法 涉 及：a）中 序 递 归 遍 历 算 法、前 序
2、递 归 遍 历 算 法【选】b）中 序 遍 历 非 递 归 算 法 c）先 序 或 后 序 遍 历 非 递 归 算 法 d）建 立 中 序 线 索，并 进 行 中 序 遍 历 和 反 中 序 遍 历 5.实 现 二 叉 树 的 按 层 遍 历 算 法 6.设 计 一 个 测 试 用 的 二 叉 树 并 创 建 相 应 的 内 存 二 叉 树，可 以 测 试 自 己 算 法 的 边 界（涉 及 树 节 点 数 为 0、1以 及 1 的 不 同 情 形）。7.测 试 数 据：输 入 数 据：一+a*b-c d-e f概 要 设 计 说 明:本 程 序 在 递 归 调 用 中 用 到 了 链 表,在
3、 非 递 归 调 用 时 用 到 了 栈。1.栈 的 抽 象 数 据 类 型 ADT Stac k 数 据 对 象:D=ai I ai G char,i=1,2,3.数 据 关 系：R=|a i-i,ai WD,i=2,3 基 本 操 作：In i tS ta c k（&S）操 作 结 果：构 造 一 个 空 栈S tackEmpty(S)。初 始 条 件:栈 S 已 存 在。A 操 作 结 果:若 S 为 空 栈，则 返 回 0K,否 则 返 回 E R R O RoPush(&S,e)。初 始 条 件:栈 S 已 存 在。操 作 结 果:插 入 元 素 e 为 新 的 栈 顶 元 素。Po
4、 p(&S,&e)初 始 条 件：栈 S 已 存 在 且 非 空。A。操 作 结 果:删 除 S 的 栈 顶 元 素，并 用 e 返 回 其 值。G e tT o p(S,&e 0初 始 条 件：栈 S 已 存 在 且 非 空。操 作 结 果:用 e 返 回 S 的 栈 顶 元 素。2.二 叉 树 的 抽 象 数 据 类 型 A D T Bin a r yTree数 据 对 象 D：D 是 具 有 相 同 特 性 的 数 据 元 素 的 集 合。A 数 据 关 系 R：若=，则 R=0,称 BinaryTre e 为 空 二 叉 树；A。若 Dr，则 R=H,H 是 如 下 二 元 关 系；“
5、(1)在 D 中 存 在 惟 一 的 称 为 根 的 数 据 元 素 root,它 在 关 系 H 下 无 前 驱；A。(2)若 口 一 004网),则 存 在 口-001=但 1,口 1,且 口 1 门 口=;。(3)若 D 屏，则 D 1 中 存 在 惟 一 的 元 素 xl,H,且 存 在 D I 上 的 o o 关 系 Hl UH;若 D/，则 D r 中 存 在 惟 一 的 元 素 x r,eH,且 g。存 在 上 的 关 系 H r U H；H=,H 1,Hr);。(4)(D 1,H1)是 一 棵 符 合 本 定 义 的 二 叉 树，称 为 根 的 左 子 树；(Dr,Hr)是 一
6、。棵 符 合 本 定 义 的 二 叉 树，称 为 根 的 右 子 树。基 本 操 作:Cr e at e BiTr e e(&T)4。初 始 条 件:给 出 二 叉 树 T 的 定 义。操 作 结 果：按 规 定 构 造 二 叉 树 T。Pr e 0 r d erTr a v e r se_ r e(T,p r int()A 00初 始 条 件：二 叉 树 T 存 在,p rin t是 二 叉 树 所 有 结 点 输 出 的 应 用 函 数。，操 作 结 果:先 序 递 归 遍 历 T,对 每 个 结 点 调 用 函 数 p r i n t 一 次 且 仅 一 次。一 旦。pri n t()失
7、 败,则 操 作 失 败。In O r derTr a vers e(T,pri n t()A 初 始 条 件:二 叉 树 T 存 在,p r i n t是 二 叉 树 所 有 结 点 输 出 的 应 用 函 数。4。操 作 结 果:中 序 非 递 归 遍 历 T,对 每 个 结 点 调 用 函 数 p r i n t 一 次 且 仅 一 次。一。旦 p rintf()失 败，则 操 作 失 败。I n OrderTrav e rse_re(T,p r int()。初 始 条 件：二 叉 树 T 在 在,pri n t是 二 叉 树 所 有 结 点 输 出 的 应 用 函 数。操 作 结 果：
8、中 序 递 归 遍 历 T,对 每 个 结 点 调 用 函 数 p rin t一 次 且 仅 一 次。一 旦。pr i ntf()失 败，则 操 作 失 败。PreOrd e rTra v e rse(T,print()初 始 条 件：二 叉 树 T 存 在,p rin t 是 二 叉 树 所 有 结 点 输 出 的 应 用 函 数。操 作 结 果:先 序 非 递 归 遍 历 T,对 每 个 结 点 调 用 函 数 p r i n t 一 次 且 仅 一 次。一。旦 p rin t()失 败，则 操 作 失 败。Le v e lor d e r(T)初 始 条 件:二 叉 树 T 在 在。操
9、作 结 果:分 层 遍 历 二 叉 树 T,并 输 出。InOrde r Thread i ng(Thrt,T);初 始 条 件:二 叉 树 T 在 在。操 作 结 果:中 序 遍 历 二 叉 树，并 将 其 中 序 线 索 化。I n O r de r Tra v erse_ T hr(T,pri n t);初 始 条 件:二 叉 树 T 在 在。操 作 结 果：中 序 非 递 归 遍 历 二 叉 线 索 树 TInThreadin g(p)；初 始 条 件:结 点 P 在 在。操 作 结 果:结 点 p 及 子 树 线 索 化。3.主 程 序 的 流 程：void main()0初 始 化
10、；提 醒；，执 行 二 叉 数 A D T 函 数；)4.本 程 序 包 含 三 个 模 块 1)主 程 序 模 块 v oid ma in()初 始 化；(接 受 命 令；显 示 结 果；2)链 表 模 块。递 归 调 用 时 实 现 链 表 抽 象 数 据 类 型。3)栈 模 块。非 递 归 调 用 时 实 现 栈 的 抽 象 数 据 类 型。具 体 设 计 1.宏 定 义 及 全 局 变 量#d efin e TElemTy p e ch a r#d efine SEI e m T ype B i Tr e e#define OK 1#d ef i ne OV E RFLOWO#d e
11、f i n e ERROR 0#d e fine STACK_ I N IT _SIZ E 1 0 0#d efine STAC K INC R E M E N T 1 0SqS t ack S；BiThrTree p r e;BiThrTr e e i；2.函 数 定 义 i n t C r e a teBiTree(BiTr e e&T)；。/创 建 二 叉 树 void PreOrder T rav e rs e _ r e(B iTree T,void(*prin t)(TElemType e)；/先 序 递 归 遍 历 二 叉 树 v oid I nOr d e r Trave r
12、se(B i T ree T,i n t(*pri n t)(T E lemTyp ee);“中 序 非 递 归 遍 历 二 叉 树 v oid I n Ord e rTra v er s e_ r e(BiTr e e T,i n t(*print)(TEl e mT y pe e);/中 序 递 归 遍 历 二 叉 树 v o i d P r eOr d e r Tra v e r s e(BiTree T,in t(*print)(TEl e mTy p e e)；先 序 非 递 归 遍 历 二 叉 树 int pr i nt(TElemT y p e e);打 印 元 素 void I
13、n i tS t ack(Sq S tack&S)产 栈 的 初 始 化 vo i d P o p(S q S t a c k&S,S E lem T y p e&e);vo i d P u sh(S q S t ack&S,SE 1 emTy p e&e);int S tac k Empty(SqS t ack S);i n t G e tTop(S qS t a c k S,SElemType&e);void Lev e lorde r(BiTree T)；v oid InO rderThrea d ing(B iT h rTree&Thrt,BiT h r Tr e e T)；int I
14、 n 0 r derTraverse_Thr(BiThrTr e e T,int(*pr i nt)(T E 1 emType e);voi d I n Threa d i n g(B i ThrTree p);3.二 叉 树 链 表 数 据 结 构：ty p e d e f struct Bi T NodeT El e mT y p e d ata；o s t r uc t BiTNode*lchild,*rchi 1 d;Foint e rTag LTag,R T a g；Bi T N o de,*B iTree,BiT h rNo d e,*Bi ThrT r ee?基 本 操 作：a)
15、构 造 二 叉 树 Ti n t Cr e a t e B iTr e e(BiTre e&T)(char c h；scan f(c，&ch);“f(c h=，)T=NULL;e l s e(if(!(T=(B i TN ode*)m a 1 loc(si z eof(BiTNode)return E R RO R;。T-d a t a=ch;i f(Cr e a t e B iT r ee(T-lchild)T-L T ag=L i n k;3 if(C re a t eBi T ree(Trchild)T-RT a g=L in k;。r e t u r n OK;)b)先 序 递 归 遍
16、 历 二 叉 数 T,并 输 出 所 有 结 点 值。v o i d PreOrderTra v e r se_ r e(Bi T r e e T,int(*pri n t)(TElemType e)(if(T)(if(p r int(T-d a t a)r eOrder T r a verse_ re(T 1 child,print);P r e O rde r Traver s e_ r e(T-rch i 1 d,p r int);r e t u r n;)e l s eoreturn;)c)中 序 非 递 归 遍 历 二 叉 树 T,并 输 出 所 有 结 点 值 voi d InOr
17、de r Travers e(BiT r e e T,i n t(*prin t)(TElemTyp e e)(3s q Stack S;eS.base=NULL;S.top=NULL;s S Elem T ype p=NULL；JnitS t a c k(S);P u s h(S,T);bv h i 1 e(!S t ackEmp t y(S)b(wh i 1 e(GetTop(S,p)&p)a-P u s h(S,p-1 child);oPop(S,p);s if(!S ta c k E mpty(S)(。Pop(S,p)；g叩 r i nt(p-d a t a);。P u sh(S,p-
18、rc h ild);r etu r n;)d)中 序 递 归 遍 历 二 叉 树 T,并 输 出 所 有 结 点 值 v o i d I n O rderTraverse_ re(B iTre e T,int(*pr i n t)(T E 1 e mTypee)(i f(T)(I nOrde r T r averse_ r e(T-1 c h i l d,print);p r int(T-da t a);I n 0 rd e r T r av e rs e _ r e(T-rc h i 1 d,print)；e）中 序 遍 历 二 叉 树 T,并 将 其 中 序 线 索 化，T h r t指
19、向 头 结 点 v o id InOrderThreading(BiThrTree&T h rt,B i T h rT r e e T)3Thl，t=(B i ThrTree)m a llo c(s i z eof(B i ThrNode);oThrt-L T a g=L i n k;/建 头 结 点 3Th r t RTag=Threa d;Th r t-rchild=T h r t；右 指 针 回 指 i f(!T)Thrt-l c hild=Th r t;e 1 se(。T hrt-lchild=T;o p r e=T h rt;I n Thr e a ding(T);/中 序 遍 历
20、进 行 中 序 线 索 化 8P r e-rchild=T hr t；p r e-RTag=T h read;/最 后 一 个 结 点 线 索 化 3T h r t-r chil d=p r e；)i=T hrt;/I nOrderT h r eadingf)结 点 P线 索 化 void InT h r e a d i n g(B i T h r Tree p)if(P)I n Threading(p-lchi I d);/左 子 树 线 索 化“f(!p-lchild)/建 前 驱 线 索。p-LTag=T h r e a d；p lchil d=p r e；。i f(!pr e-r c
21、h il d)/建 后 继 线 索“pre-R T ag=Thr e ad;pr e-rc h ild=p;P r e=p;/保 持 p re指 向 p 的 前 驱。I nThr e ading(p rchild)；/右 子 树 线 索 化 0)/InThrea d i n gg)/中 序 遍 历 线 索 化 二 叉 树 in t I nOrderTravers e _ T h r(B iT h r Tre e T,i n t(*pr i nt)(TElemTypee)(BiThrTre e p=N U LL;p=T-lchild；ew h ile(p!=T)3 wh i 1 e(p-LTag
22、=L i nk)。i p=p-1 chi 1 d;i f(!p r i n t(p-da t a)“r e t u r n ERR 0 R;owhi 1 e(p R T ag=T h r ea d&p-rc h i 1 d!=T)(8叩=p rch i l d;o p r i nt(p data);gp=p-r c hi 1 d;return O K;)4.栈 数 据 结 构：typedef s t ru c t SElemType base;SEl e mType*top;in t stac k size；S q S t ack；基 本 操 作：a)创 建 一 个 空 栈 voi d Ini
23、tStac k(Sq S t ack&S)(S.b ase=(S ElemType*)malloc(STA C K _IN IT_SIZE*s izeo f(SEIe mT y pe);S.top=S.b a s e；。/初 始 为 空 S.stacksi z e=S T A C K _ I NIT_SIZE;oretu r n；)b)栈 顶 插 入 元 素 void Pu s h(SqS t a ck&S,S E 1 em T y pe&e)(bif(S.top-S.b ase=S.s t ack s i z e)o S.base=(S E 1 e m Ty p e*)reall o c(S
24、.b a se,(STACK NIT_SIZE+STACK I NC REMENT)*sizeof(S ElemTy p e);S,top=S.b ase+S.s t a cksize；S.stack s ize+=S T ACKINCREMENT;)*S.top+=e；)c)栈 顶 删 除 元 素 v o i d Pop(S q Stack&S,SElem T y p e&e)(i f(S.to p=S.base)re t u r n；e=*-S.top；r e tu r n；)d)判 断 栈 是 否 为 空 栈 i n t S t ac k Empty(Sq S tack S)。(“f(S
25、.t o p=S.b ase)return 0 K;照 1 se8r e t urn E RRO R;)e)e 返 回 S 的 栈 顶 元 素 i nt G etTo p(Sq S t a ck S,SElemTy p e&e)i f(S.t o p=S.ba s e)r e turn ERR O R；e=*(S.t op-1);r e t u rn OK;5,主 函 数 void mai n()i nt f 1 ag;BiT ree T;BiThrTree T h rt;op rintf(”*n);叩 ri n tf(*实 验 12 二 叉 树 的 遍 历*n);p r i n t f(*1
26、.实 现 二 叉 树 的 不 同 遍 历 算 法 和 二 叉 树 的 中 序 线 索 化 算 法*n);print f(*a)中 序 递 归 遍 历 算 法；*n);p r intf(*b)先 序 递 归 遍 历 算 法；*n);prin t f(*c)中 序 遍 历 的 非 递 归 算 法；*n)；P r i n tf(*d)先 序 或 后 序 遍 历 非 递 归 算 法 之 一；*n”)；叩 ri n tf(*e)建 立 中 序 线 运 用 线 索 进 行 中 序 遍 历 和 反 中 序 遍 历。*n);p r in t f(*2.实 现 二 叉 树 的 按 层 遍 历 算 法。*n);p
27、 r intf(”*H)pri n tf(n选 择 操 作：n t L先 序 与 中 序 遍 历 算 法 n t 2.中 序 线 索 的 中 序 遍 历 和 反 中 序 遍 历 算 法 n t 3.按 层 遍 历 算 法 n请 选 择:)；s c a n f C%d;&f la g)；swit c h(flag)cas e I:。叩 r intf(前 序 递 归 创 建 二 叉 树(空 格 表 达 此 结 点 为 空):n”)；“getchar();。ooCre a teB i Tr e e(T)；皿 printf(中 序 递 归 遍 历 输 出：”)；MnOr d e r Traverse_
28、r e(T,print)；-p r i ntf(”n 前 序 递 归 遍 历 输 出:“)；g P r e Order T ra v e r s e_re(T,print);gprin t f(”n 中 序 非 递 归 遍 历 输 出：”)；In 0 rde r Tr a verse(T,print);g P rin t f(n 前 序 非 递 归 遍 历 输 出：”)；PreOr d e r T r a verse(T,prin t);“3 printf(n,r)；“b r eak;c ase 2：叩 rintf(前 序 递 归 创 建 二 叉 树(空 格 表 达 此 结 点 为 空):n)
29、;getchar()；Cr e a t e BiTr e e(T);。叩 r in t f(n 中 序 遍 历 线 索 化 二 叉 树：);“InOrde r T hrea d i n g(Th r t,T)；4nO r d e rTraver s e_ T hr(Thrt，print)；a b rea k；case 3:pri n t f(前 序 递 归 创 建 二 叉 树(空 格 表 达 此 结 点 为 空):nn);eg g e tc h ar()；CreateBiT r ee(T)；P rint f（”n 按 层 遍 历 输 出:）；Levelorder(T);*p ri n tf(n
30、 H);8gbrea k;b d e f ault:r e t u r n;6,函 数 间 调 用 关 系 CreateBitInOrderTr PreOrder InOrderTr PreOrderT InOrderTh InOrderTraStack 操 Threading调 试 分 析 1、二 叉 树 的 分 层 遍 历，开 始 时 想 用 队 列 来 做，但 考 虑 到 比 较 麻 烦，因 而 改 为 数 组 模 拟 队 列,简 朴 易 懂，课 后 可 自 行 尝 试 用 队 列 来 做。2.在 线 索 化 二 叉 树 时 考 虑 到 假 如 将 两 种 存 储 结 构 分 开 将 导
31、 致 两 个 类 型 的 指 针 不 能 互 相 传 值,导 致 许 多 麻 烦。比 较 两 种 存 储 结 构 发 现，线 索 二 叉 树 比 二 叉 树 多 了 两 个 标 志 域 LTag,Rtag。于 是 把 两 种 存 储 结 构 合 并 为 BiThrNode,并 在 建 立 二 叉 树 时 把 LTag,Rtag均 置 为 L in k。程 序 正 常 运 营。3.进 入 演 示 程 序 B iT re e,c p p,完 毕 编 译，连 接（即 按 下 C t r l F5）进 入 演 示 界 面，或 直 接 打 开 执 行 文 献 Bi T r e e.ex e,产 生 如
32、下 图 所 示 的 界 面：1.用 户 需 根 据 用 户 提 醒 信 息 操 作，输 入 二 叉 树（以 空 格 表 达 空 结 点），输 入 完 毕 后 按 回 车 键，屏 幕 上 打 印 出 相 应 于 该 二 叉 树 的 各 种 遍 历 结 果。如 下 图:”C:UsersduduDesktopS653SW ZlSagnifRlkStSB=DebugBiTree.ex.dd二 如;-c树 丕 1-遍-e:a.出 出*b叉 出 出 科+a-d帮 历 历.化 C历 历 索 实 誉 递 WS-Syl!wy!tv贮 郑 圣 堂 建 整.2的 晦 爰 六*i历 和 F霍 M的 算 窗；霸 邂-S
33、0SSb归 归 速 递 历 历*递 递 层 序 T中 前 史 法 中 io算 行 能 归 进 期 按 任 意 键 退 出 P*ess any key to c o n tin u e六、测 试 结 果 输 入：-+a*b c d-e屏 幕 输 出：中 序 递 归 遍 历 输 出：a+b*c-d前 序 递 归 遍 历 输 出：+a*b-cd中 序 非 递 归 遍 历 输 出:a+b*c-d前 序 非 递 归 遍 历 输 出：+a*b-cd按 层 遍 历 输 出：+a*b cd中 序 遍 历 线 索 化 二 叉 树：a+b*c-d七、附 录 BiT r ee.c p pBi T r ee.e x
34、e#inclu d e#i n c lu d e#def i ne Q El e mT y pe BiTNode#defi n e TElemT y pe c h a r#define OK 1#de f ine OVERFLOW O#d e f i ne ERROR 0#define S TACK_INIT_S I Z E 100#d efine S TACKIN C REMENT 10t y pe d ef e n um Point e rT ag Lin k,T h read;o/Lin k=0,指 针,Thre a d=1,线 索 typ e def s t ruct BiTNodeT
35、E 1 e mT y pe data;s t r u c t Bi TN o de*lchild,*r c hild;aPoi n terTa g LT a g,RT a g;Bi TNo d e,*Bi Tree,B iT h rN o d e,*B iThrTree;/二 叉 树#d e f i ne Q E lemT y pe BiTNode#d efine SE 1 emT ype BiTre et ype d e f s t r u c tSElemType*base;o S Ele m Type*top；i n t stacks i ze；SqSt a ck；全 局 变 量S qS
36、t a c k S;B i T hrT r ee pr e;B i T h rT ree i;/*函 数 声 明*/int Creat e BiTree(B iTree&T);。/创 建 二 叉 树 void PreOr d e rTraverse_re(BiT r ee T,v oid(*p r i nt)(TElem Ty p e e);/先 序 递 归 遍 历 二 叉 树 vo i d InO r d e rT rave r se(BiT r ee T,in t(*p ri n t)(TE lemType e);“/中 序 非 递 归 遍 历 二 叉 树 void I n O r d e
37、 rTraverse_re(B i T r ee T,in t(p r i nt)(T E I emType e);/中 序 递 归 遍 历 二 叉 树 void Pr e Ord e r T r averse(BiTree T,in t(Sprint)(TElem Type e);先 序 非 递 归 遍 历 二 叉 树 int prin t(TE 1 emTy p e e);。/打 印 元 素 v o id I nitS t a c k(SqSta c k&S)“/栈 的 初 始 化 v o i d Pop(Sq S t a ck&S,SElemTy p e&e);voi d Push(Sq
38、Stack&S,SEIemType&e)；i nt S t ackE mpty(SqStack S);int Get T o p(SqSt a ck S,S ElemTyp e&e);vo i d L e v e l o r d e r(B i Tree T)；v oid InOrd e rThre a d i n g(BiThrT r e e&Thr t,Bi T h r T r e e T);int I n Ord e rT raver s e_Thr(Bi ThrT r ee T,in t(*p r in t)(T E lem T ype e);vo i d InThreadi n g(
39、B i Thr T r e e p);/*二 叉 树 的 创 建 递 归 创 建*/int CreateBi T ree(B i Tree&T)。c har c h；s canf(n%c,&ch);。i f(c h=)o T=N U L L;e 1 s e(。if(!(T=(Bi TNode*)ma 1 1 o c(s izeof(B i T N od e)。retu rn ERROR；。T-data=ch;o if(CreateBiTre e(T-1 c hi 1 d)T-L T ag=L i n k；gif(C r eate B i Tree(T-rchild)T RT a g=L i n
40、 k;)。r e turn O K；/*/*先 序 递 归 遍 历 输 出*/*v o id P r eOrderTravers e _re(BiTree T,int(大 p rint)(TE 1 em T y p e e)(if(T)(i f(p r i nt(T-da t a)r eOr d e r T r a vers e _ r e(T-1 c hiki,print)；。PreOrde r Tr a verse_re(T-rchild,pri n t);“r et u m；)f elsereturn;)/*/*中 序 非 递 归 遍 历 输 出*/*/vo i d I n Ord e
41、r T r av e r s e(BiTree T,i n t(*prim)(T E lemType e)(SqS t a c k S;S.base=NULL;S.top=NU LL;oSEl e mTy p e p=N U L L;4n i t S t a c k(S);o P u sh(S,T)；wh i 1 e(!Stac k Empt y(S)(gwh i le(GetT o p(S,p)&p)。Push(S,p-lchild);“Pop(S,p);i f(!StackEm p t y(S)(。Pop(S,p);p r i nt(p-da t a);P u s h(S,p-rc h i
42、ld);return;)/*/*中 序 递 归 遍 历 输 出*/*/void I n OrderT r a v e r s e _ r e(Bi Tree T,i n t(*p r i n t)(TE 1 emTyp e e)if(T)(InOr d e r Tr a verse_ re(T-lch i 1 d,p ri n t);p r int(T-data);I n O r d e r T r a v e r se_re(T-rc h ild,prin t)；)r e t urn;)/*/*按 照 前 序 非 递 归 遍 历 二 叉 树:栈*/*/v o id PreOr d e rTr
43、av e rse(BiT r ee T,int(*p rint)(TElemT y p e e)6qSt a ck S;0 S.b ase=N U L L：S.to p=N U L L；S El e mT y p e p=T;/p指 向 当 前 访 问 的 结 点 InitSta c k(S);w h i le(p|!Stac k Empt y(S)if(P)(print(p-d a t a)；P u s h(S,p);p=p-lchil d;)else(Pop(S,p);p=p-rc h il d;r etum;v oid I n O r d e rTh r eading(B iThrT r
44、e e&Thr t,B i ThrT r ee T)/中 序 遍 历 二 叉 树 T,并 将 其 中 序 线 索 化，T h rt指 向 头 结 点(T hr t=(B i T hrT r ee)malloc(s i z e of(B i ThrN o d e)；oThr t-LTag=Li n k;建 头 结 点 Thrt-RTag=Th r e a d;Th r t-rc h ild=T h rt;/右 指 针 回 指 if(!T)Thr t-lchild=Thrt；e l s e(。订 h rt-l c h i ld=T;。pre=Thrt;MnTh r e adi n g(T)：中 序
45、 遍 历 进 行 中 序 线 索 化 叩 r e-rchild=Thr t；p r e-R T a g=T h r e a d;最 后 一 个 结 点 线 索 化 h r t r chil d=pre;)i=Th r t；/InO r d e rT h r eadingv o id I nThread i n g(Bi T h rTree p)if(p)InThre a din g(p-lchild)；/左 子 树 线 索 化 if(!p-l c hil d)/建 前 驱 线 索 p LTag=Thr e a d;p-1 c h i 1 d=p re；i f(!pre-rchi I d)/建
46、后 继 线 索 pre-RTa g=Thr e ad;p r e-r c hild=p;pre=p；/保 持 p re指 向 p 的 前 驱 InThrea d ing(p-rchil d);/右 子 树 线 索 化/I nThreadingi n t InO r derT r a v e r s e_T h r(B iThr T r ee T,in t(*print)(T E lemType e)/中 序 遍 历 线 索 化 后 的 二 叉 树(。B iThrTree p=NU L L;叩=1 c h i Id：while(p!=T)wh i 1 e(p-LTag=L i nk)op=p-l
47、 c hil d;。i f(!print(p-d a t a)M e t u rn ERROR;w h i 1 e(p-R T ag=Thread&p r ch i Id!=T)0 g p=prchild;s p r i nt(p-d a t a);6)s p=p-rch i Id；r e turn O K;)/*大*以 下 为 辅 助 函 数*火 火*/i n t pri n t(TEIemType e)op r i n tf(n%cn,e);re t urn OK；/*栈 函 数*/*栈 的 初 始 化*/void InitStac k(S qSt a ck&S)(o S.base=(SE
48、lemType*)mall o c(STAC K_INI T _ S IZE*s iz e o f(S El e m T y p e);oS.top=S.b a s e;“/初 始 为 空 S.sta c k s i z e=S TACKJN I T_SIZ E;r e turn;)/*栈 顶 插 入 元 素 刃 void Push(SqSt a ck&S,SElemTyp e&e)(i f(S.top-S.b a se=S.stac k size)oS.b a s e=(S E le mType*)r ealloc(S.ba s e,(ST A C K _ I N I T_SIZE+STAC
49、K I NCREMENT)*s iz e。f(SElem Type)；Q S.top二 S.base+S.stack s ize;“S.st a c k size+=S T ACKINC R EM E NT;。求 S.t o p+=e;)/*栈 顶 删 除 元 素*/void P o p(S qStac k&S,SEI e mT y pe&e)A f(S.t o p=S.b a s e)r e t u r n;e=*S.top;r e turn;)in t StackE m pty(S q S t a c k S)。/*若 栈 为 空 栈，则 返 回 O K,否 则 返 回 ERROR*/(i
50、 f(S.top=S.base)return O K;o e 1 s eo retur n ERROR;)int Ge t Top(SqS t ac k S,S E 1 e mType&e)(i f(S.to p=S.ba s e)。好 e turn E R RO R;oe=*(S.top-1);return OK：)/*/*按 层 次 顺 序 建 立 一 棵 二 叉 树*/*/v o id L evelord e r(BiT r e e T)in t i,j;Bi T Nod e*q 2 0,*p;/*q 20用 于 模 拟 队 列，存 储 入 队 的 结 点*/P=T;i f(p!=N U