《数据结构与算法(C语言版)》课后习题答案.pdf

《《数据结构与算法(C语言版)》课后习题答案.pdf》由会员分享，可在线阅读，更多相关《《数据结构与算法(C语言版)》课后习题答案.pdf（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课 后 习 题 答 案 模 块 1数 据 结 构 概 述 一、填 空 题 1、数 据 元 素 2、数 据 项 3、集 合 结 构、线 性 结 构、树 型 结 构、图 形 结 构 4、顺 序 存 储、链 式 存 储 5、有 穷 性、确 定 性、可 行 性、输 入、输 出 二、判 断 题 1、X 2、X 3、X 4、/5、J模 块 2 线 性 表 一、选 择 题 1、A 2,C 3、D 4、C 5、B 6、A 7、A 8、D二、填 空 题 1,(n-1)/22、主 要 是 使 插 入 和 删 除 等 操 作 统 一，在 第 一 个 元 素 之 前 插 入 元 素 和 删 除 第 一 个 结 点 不

2、 必 另 作 判 断。另 外，不 论 链 表 是 否 为 空，链 表 头 指 针 不 变。3、(1)数 据 元 素 的 前 后 顺 序(2)元 素 中 的 指 针 4、(1)顺 序(2)链 式 5、(1)0(1)(2)0(n)6、(1)4(2)27、从 任 一 结 点 出 发 都 可 访 问 到 链 表 中 每 一 个 元 素。8、(1)p-next(2)s-data(3)t9、14410、L-next-next=L三、判 断 题 1、X 2、X 3、X 4、5、M 6、X 7、8,X四、程 序 设 计 题 1、void Insert_SqList(SqList va,int x)/*把 x

3、插 入 递 增 有 序 表 va 中*/int i;if(va.length MAXSIZE)return;for(i=va.length-1;va.elemx&i=0;i一 一)va.elemi+l=va.elem;va.elemi+l=x;va.length+;/*Insert_SqList*/2、【算 法 分 析】比 较 顺 序 表 A 和 B,并 用 返 回 值 表 示 结 果，值 为 1,表 示 A B;值 为 T,表 示*B；值 为 0,表 示 A二 B。1)当 两 个 顺 序 表 可 以 互 相 比 较 时，若 对 应 元 素 不 等，则 返 回 值 为 1或 T；2)当 两 个

4、 顺 序 表 可 以 互 相 比 较 的 部 分 完 全 相 同 时，若 表 长 也 相 同，则 返 回 值 为 0;否 则，哪 个 较 长，哪 个 就 较 大【算 法 源 代 码】int ListComp(SqList A,SqList B)for(i=l;i=A.length&i=B.length;i+)if(A.elem!=B.elem)return A.elemB.elem?l：-l;if(A.length=B.length)return 0;return A.lengthB.length?1:T;/*当 两 个 顺 序 表 可 以 互 相 比 较 的 部 分 完 全 相 同 时，哪

5、个 较 长，哪 个 就 较 大*/*ListComp*/3、【算 法 分 析】1)单 链 表 ha的 头 结 点 作 为 连 接 后 的 链 表 的 头 结 点，即 hc=ha;2)查 找 单 链 表 ha的 最 后 一 个 结 点，由 指 针 p 指 向，即 p-next=NULL;3)将 单 链 表 hb的 首 元 结 点(非 头 结 点)连 接 在 p之 后，即 p-next=hb-next;4)回 收 单 链 表 hb的 头 结 点 空 间【算 法 源 代 码】void ListConcat(LinkList ha,LinkList hb,LinkList*hc)/*把 链 表 hb

6、接 在 ha后 面 形 成 链 表 he*/*hc=ha;p=ha;/*由 指 针 p 指 向 ha的 尾 元 结 点*/p=p-next;p-next=hb-next;free(hb);/*ListConcat*/4、【算 法 分 析】1)生 成 新 结 点 存 放 元 素 b,由 指 针 new指 向；2)将 new插 入 在 单 链 表 的 第 i个 元 素 的 位 置 上：若 i=l,new插 在 链 表 首 部；否 则 查 找 第 i T 个 结 点，由 指 针 P指 向，然 后 将 new插 在 p之 后。【算 法 源 代 码】void Insert(LinkList*L,int

7、i,int b)LinkList new;new=(LinkList*)malloc(sizeof(LNode);new-data=b;if(i=l)/*插 入 在 链 表 头 部*/New-next=*L;*L=new;else/*插 入 在 第 i 个 元 素 的 位 置*/P=*L;while(il)p=p-next;new-next=p-next;p-next=new;/*Insert*/5、【算 法 分 析】1)查 找 最 后 一 个 不 大 于 mink的 元 素 结 点，由 指 针 p指 向；2)如 果 还 有 比 mink更 大 的 元 素，查 找 第 一 个 不 小 于 ma

8、xk的 元 素，由 指 针 q 指 向；3)p-next=q,即 删 除 表 中 所 有 值 大 于 mink且 小 于 maxk的 元 素。【算 法 源 代 码】void Delete_Between(LinkList*L,int mink,int maxk)P=*L;while(p-next-datanext;/*p 是 最 后 一 个 不 大 于 mink的 元 素*/if(p-next)/*如 果 还 有 比 mink更 大 的 元 素*/q=p-next;while(q-datanext;/*q 是 第 一 个 不 小 于 maxk 的 元 素*/p-next=q;)/*Delete

9、_Between*/6、【算 法 务 析】1)初 始 化 指 针 P和 q,分 别 指 向 链 表 中 相 邻 的 两 个 元 素；2)当 p-next不 为 空 时，做 如 下 处 理：若 相 邻 两 元 素 不 相 等 时，P和 q都 向 后 推 一 步；否 则，当 相 邻 元 素 相 等 时，删 除 多 余 元 素。【算 法 源 代 码】void Delete_Equal(LinkList*L)P=(*L)-next;q=p-next;/*p和 q 指 向 相 邻 的 两 个 元 素*/while(p-next)if(p-data!=q-data)/*若 相 邻 两 元 素 不 相 等

10、时，p 和 q 都 向 后 推 一 步*/p=p-next;q=p-next;else while(q-data=p-data)/*当 相 邻 元 素 相 等 时 删 除 多 余 元 素*/r=q;q=q-next;free(r);)p-next=q;p=q;q=p-next;/*else*/*while*/*Delete_Equal*/7、【算 法 分 析】1)空 表 或 长 度 为 1的 表，不 做 任 何 处 理；2)表 长 大 于 2 时，做 如 下 处 理：首 先 将 整 个 链 表 一 分 为 二，即 从 链 表 的 第 一 元 素 结 点 处 断 开；逐 个 地 把 剩 余 链

11、表 的 当 前 元 素 Q插 入 到 链 表 的 头 部。【算 法 源 代 码】void LinkList_reverse(LinkList L)if(!L-next|!L-next-next)return;p=L-next;q=p-next;s=q-next;p-next=NULL;/*从 链 表 的 第 一 元 素 结 点 处 新 开*/while(s-next)q-next=p;p=q;q=s;s=s-next;/*把 L 的 元 素 逐 个 插 入 新 表 表 头*/q-next=p;s-next=q;L-next=s;/*LinkList_reverse*/8、【算 法 分 析】1)

12、初 始 化 指 针 P 指 向 链 表 A 的 当 前 元 素，指 针 q指 向 链 表 B 的 当 前 元 素；2)当 链 表 A 和 B 均 为 结 束 时，做 如 下 处 理：将 B 的 元 素 插 入 若 A 非 空，将 A 的 元 素 插 入 指 针 P 和 q 同 时 后 移【算 法 源 代 码】void mergel(LinkList A,LinkList B,LinkList*C)p=A-next;q=B-next;*C=A;while(p&q)s=p-next;p-next=q;/*将 B 的 元 素 插 入*/if(s)t=q-next;q-next=s;/*若 A 非 空

13、，将 A 的 元 素 插 入*/P=s；q=t；/*指 针 p和 q 同 时 后 移*/Awhile*/*mergel*/9、【算 法 分 析】按 从 小 到 大 的 顺 序 依 次 把 A 和 B 的 元 素 插 入 新 表 的 头 部 pc处，最 后 处 理 A 或 B 的 剩 余 元 素。【算 法 源 代 码】void reverse_merge(LinkList A,LinkList B,LinkList*C)LinkList pa,pb,pre;pa=A-next;pb=B-next;/*pa和 pb分 别 指 向 A 和 B 的 当 前 元 素*/pre=NULL;while(pa

14、|pb)if(pa-datadata|!pb)/*将 A 的 元 素 插 入 新 表*/pc=pa;q=pa-next;pa-next=pre;pa=q;else/*将 B 的 元 素 插 入 新 表*/pc=pb;q=pb-next;pb-next=pre;pb=q;pre=pc;)*C=A;A-next=pc;/*构 造 新 表 头*/*reverse_merge*/10、【算 法 分 析】先 从 B和 C 中 找 出 共 有 元 素，记 为 same,再 在 A 中 从 当 前 位 置 开 始，凡 小 于 same的 元 素 均 保 留(存 到 新 的 位 置)，等 于 same的 就

15、跳 过，到 大 于 same时 就 再 找 下 一 个 same。【算 法 源 代 码】void SqList_Intersect_Delete(SqList*A,SqList B,SqList C)i=0;j=0;k=0;m=0;/*i指 示 A 中 元 素 原 来 的 位 置，m 为 移 动 后 的 位 置*/whi le(i(*A).length&jB.length&.kC.length)if(B.elemjC.elemk)k+;else same=B.elemj;/*找 到 了 相 同 元 素 same*/while(B.elemj=same)j+;while(C.elemk=same

16、)k+;/*j 和 k 后 移 到 新 的 元 素*/while(i(*A).length&(*A).elemsame)(*A).elemm+=(*A).elemi+;/*需 保 留 的 元 素 移 动 到 新 位 置*/while(i(*A).length&(*A).elem=same)i+;/*跳 过 相 同 的 元 素*/)/*while*/while(inext!=NULL)/*链 表 不 为 空 表*/p=la-next-next;/*P指 向 第 一 结 点 的 后 继*/la-next-next=NULL;/*直 接 插 入 原 则 认 为 第 一 元 素 有 序，然 后 从 第

17、 二 元 素 起 依 次 插 入*/while(p!=NULL)r=p-next;/*暂 存 p 的 后 继*/q=la;while(q-next!=NULL&q-next-datadata)q=q-next;/*查 找 插 入 位 置*/p-next=q-next;/*将 p 结 点 链 入 链 表*/q-next=p;p=r;12、【算 法 分 析】1)在 双 向 链 表 中 查 找 数 据 值 为 x 的 结 点，由 指 针 p 指 向，若 找 不 到，直 接 返 回,否 则 执 行 第 2 步；2)修 改 x 结 点 的 访 问 频 度 freq,并 将 结 点 从 链 表 上 摘 下

18、；3)顺 结 点 的 前 驱 链 查 找 该 结 点 的 位 置，即 找 到 一 个 结 点 的 访 问 频 度 大 于 x 结 点 的 访 问 频 度，由 指 针 q 指 向；若 q 和 P 不 是 相 邻 结 点，调 整 位 置，把 P 插 在 q之 后。【算 法 源 代 码】DuLNode*Locate_DuList(DuLinkList*L,int x)p=(*L)-next;whi1e(p.data!=x&p!=(*L)p=p-next;if(p=(*L)return NULL;/*没 找 到 x结 点*/p-freq+;p-pre-next=p-next;p-next-pre=p-

19、pre;/*将 x 结 点 从 链 表 上 摘 下*/q=p-pre;whi 1 e(q-freqfreq&p!=(*L)q=q-pre;/*查 找 插 入 位 置*/if(q!=ppre)/*将 x 结 点 插 入*/q-next-pre=p;p-next=q-next;q-next=p;p-preq;/*调 整 位 置*/)return p;/*Locate_DuList*/13、【算 法 分 析】留 下 三 个 链 表 中 公 共 数 据，首 先 查 找 两 表 A 和 B 中 公 共 数 据，再 去 C 中 找 有 无 该 数 据。要 消 除 重 复 元 素，应 记 住 前 驱，要 求

20、 时 间 复 杂 度 0(m+n+p),在 查 找 每 个 链 表 时，指 针 不 能 回 溯。【算 法 源 代 码】LinkList Common(LinkList A,LinkList B,LinkList C)pa=A-next;pb=B-next;pc=C-next;/*pa,pb 和 pc 是 工 作 指 针*/pre=A;while(pa&pb&pc)/*当 三 表 均 不 空 时，查 找 共 同 元 素*/while(pa&pb)if(pa-datadata)/*处 理 pa 结 点，后 移 指 针*/u=pa;pa=pa-next;free(u);)else if(pa-dat

21、a pb-data)pb=pb-next;else if(pa&pb)/*处 理 A和 B 表 元 素 值 相 等 的 结 点*/while(pc&pc-datadata)pc=pc-next;if(pc)if(pc-datapa-data)/*处 理 pa 结 点，后 移 指 针*/u=pa;pa=pa-next;free(u);)elseif(pre=A)/*结 果 表 中 第 一 个 结 点*/pre-next=pa;pre=pa;pa=pa-nextelse if(pre-data=pa-data)/*重 复 结 点 不 链 入 A 表*/u=pa;pa=pa-next;free(u)

22、;elsepre-next=pa;pre=pa;pa=pa-next;/*将 新 结 点 链 入 A 表*/pb=pb-next;pc=pc-next;/*链 表 的 工 作 指 针 后 移*/elseif(pa=NULL)pre-next=NULL;/*若 A 表 已 结 束，置 A 表 表 尾*/else/*处 理 原 A 表 未 到 尾 而 B 或 C 到 尾 的 情 况*/pre-next=NULL;/*置 A 表 表 尾 标 记*/while(pa!=NULL)/*删 除 原 A 表 剩 余 元 素。*/u=pa;pa=pa-next;free(u);)14、【算 法 分 析】本 题

23、 要 求 将 一 个 链 表 分 解 成 两 个 链 表，两 个 链 表 都 要 有 序，两 链 表 建 立 过 程 中 不 得 使 用 malloc申 请 空 间，这 就 是 要 利 用 原 链 表 空 间，随 着 原 链 表 的 分 解，新 建 链 表 旗 之 排 序。【算 法 源 代 码】discreat(LinkList p,LinkList q,LinkList head)p=NULL;q=NULL;/*p和 q链 表 初 始 化 为 空 表*/s=head;while(s!=NULL)r=s-next;/*暂 存 s 的 后 继*/if(s-data%2=0)/*处 理 偶 数*/

24、if(p=NULL)p=s;p-next=NULL;/*第 一 个 偶 数 结 点*/else pre=p;if(pre-datas-data)s-next=pre；p=s;/*插 入 当 前 最 小 值 结 点*/elsewhile(pre-next!=NULL)if(pre-next-datadata)pre=pre-next;/*查 找 插 入 位 置*/s-next=pre-next;/*链 入 结 点*/pre-next=s;else/*处 理 奇 数 链 if(q=NULL)q=s;q-next=NULL;/*第 一 奇 数 结 点*/elsepre=q;if(pre-datas-

25、data)s-next=pre;q=s;/*修 改 头 指 针*/elsewhile(pre-next!=NULL)/*查 找 插 入 位 置*/if(pre-next-datadata)pre=pre-next;s-next=pre-next;/*链 入 结 点*/pre-next=s;/*结 束 奇 数 链 结 点*/s=r;/*s指 向 新 的 待 排 序 结 点*/模 块 3 枝 一、选 择 题 1,B、A、C、C、A 2、B 3、B 4、A 5、C 6、A 7、D 8、C 9、D 10、B二、填 空 题 1、操 作 受 限（或 限 定 仅 在 表 尾 进 行 插 入 和 除 操 作）

26、、（后 进 先 出）的 原 则 2、栈 3、3 1 24、topl+l=top2,5、链 式 存 储 结 构 6、先 将 top加 1,然 后 push元 素 模 块 4 队 列 一、选 择 题 1,D 2,D 3、C二、填 空 题 1、为 了 克 服 假 溢 出 时 大 量 移 动 数 据 元 素 2、先 进 先 出 表 3、LinkedList、sizeof（LNode）4、牺 牲 一 个 存 储 单 元、设 标 记 三、判 断 题 1、X 2、X 3、M 4、X 5、M 6、X 7、四、应 用 题 1、答：队 列 是 允 许 在 一 端 插 入 而 在 另 一 端 删 除 的 线 性 表

27、,尾，允 许 删 除 的 一 端 叫 队 头。最 先 插 入 队 的 元 素 最 先 离 开 称 先 进 先 出（FIFO）表。2、答：用 常 规 意 义 下 顺 序 存 储 结 构 的 一 维 数 组 表 示 队 列,M 8M允 许 插 入 的 一 端 叫 队（删 除），故 队 列 也 常 由 于 队 列 的 性 质（队 尾 插 入 和 队 头 删 除），容 易 造 成“假 溢 出”现 象，即 队 尾 已 到 达 一 维 数 组 的 高 下 标，不 能 再 插 入，然 而 队 中 元 素 个 数 小 于 队 列 的 长 度（容 量）。循 环 队 列 是 解 决“假 溢 出”的 一 种 方 法

28、。通 常 把 一 维 数 组 看 成 首 尾 相 接。在 循 环 队 列 下，通 常 采 用“牺 牲 一 个 存 储 单 元”或“作 标 记”的 方 法 解 决“队 满”和“队 空”的 判 定 问 题。五、算 法 设 计 题 答：题 目 分 析 逆 波 兰 表 达 式（即 后 缀 表 达 式）求 值 规 则 如 下：设 立 运 算 数 栈 0PND,对 表 达 式 从 左 到 右 扫 描（读 入），当 表 达 式 中 扫 描 到 数 时，压 入 0PND栈。当 扫 描 到 运 算 符 时，从 0PND退 出 两 个 数，进 行 相 应 运 算，结 果 再 压 入 0PND栈。这 个 过 程 一

29、 直 进 行 到 读 出 表 达 式 结 束 符$,这 时 0PND栈 中 只 有 一 个 数，就 是 结 果。float expr（）从 键 盘 输 入 逆 波 兰 表 达 式，以$表 示 输 入 结 束，本 算 法 求 逆 波 兰 式 表 达 式 的 值。float 0PNDE30;/OPND 是 操 作 数 栈。init(OPND);两 栈 初 始 化。float num=0.0;数 字 初 始 化。scanf(%c”,&x)；x 是 字 符 型 变 量。while(x!$)switchcase=x=O&x=O&x=,9)num=num+(ord(x)-ord()/scale;scale

30、=scale*10;scanf(“%c”,&x);/elsepush(OPND,num);num=0.0;/数 压 入 栈，下 个 数 初 始 化 case x=，：break;遇 空 格，继 续 读 下 一 个 字 符。case x=，+:push(OPND,pop(OPND)+pop(OPND);break;case x=:xl=pop(OPND);x2=pop(OPND);push(OPND,x2-xl);break;case x=，*:push(OPND,pop(OPND)*pop(OPND);break;case x=，/:xl=pop(OPND);x2=pop(OPND);push

31、(OPND,x2/xl);break;default:其 他 符 号 不 作 处 理。结 束 switchscanf(“枇，&x);读 入 表 达 式 中 下 一 个 字 符。结 束 while(x!=$)printf(“后 缀 表 达 式 的 值 为/f”，pop(OPND);/算 法 结 束 o算 法 讨 京 储 设 输 入 的 后 缀 表 达 式 是 正 确 的，未 作 错 误 检 查。算 法 中 拼 数 部 分 是 核 心。若 遇 到 大 于 等 于 0 且 小 于 等 于 9,的 字 符，认 为 是 数。这 种 字 符 的 序 号 减 去 字 符 0的 序 号 得 出 数。对 于 整

32、 数，每 读 入 一 个 数 字 字 符，前 面 得 到 的 部 分 数 要 乘 上 10再 加 新 读 入 的 数 得 到 新 的 部 分 数。当 读 到 小 数 点，认 为 数 的 整 数 部 分 已 完，要 接 着 处 理 小 数 部 分。小 数 部 分 的 数 要 除 以 10(或 10的 帚 数)变 成 十 分 位，百 分 位，千 分 位 数 等 等，与 前 面 部 分 数 相 加。在 拼 数 过 程 中，若 遇 非 数 字 字 符，表 示 数 已 拼 完，将 数 压 入 栈 中，并 且)恃 变 量 num恢 复 为 0,准 备 下 一 个 数。这 时 对 新 读 入 的 字 符 进

33、 入+、*、7 及 空 格 的 判 断，因 此 在 结 束 处 理 数 字 字 符 的 case后，不 能 加 入 break语 句。模 块 5 树 一、选 择 题 1,A 2、D 3,C 4、B 5,D 6、B 7,C 8,A 9、D 10、B二、判 断 题 1、X 2、X 3、M 4、X 5、6、M 7、M 8、X 9、v/10、M三、填 空 题 1.p-lchild=null&p-rchlid=null2.(l)2k-l(2)2k-l3.644.2n n-l n+15.先 序 遍 历 后 序 遍 历 中 序 遍 历 6.(l)2k-2+l(第 k 层 1个 结 点，总 结 点 个 数 是

34、 2H-1,其 双 亲 是 2H-l/2=2k-2)(2)log2i+17.48.任 何 结 点 至 多 只 有 右 子 女 的 二 叉 树。9.二 叉 排 序 树 四、应 用 题 1.树 和 二 叉 树 逻 辑 上 都 是 树 形 结 构，树 和 二 叉 树 的 区 别 有 三：一 是 二 叉 树 的 度 至 多 为 2,树 无 此 限 制；二 是 二 叉 树 有 左 右 子 树 之 分，即 使 在 只 有 一 个 分 枝 的 情 况 下，也 必 须 指 出 是 左 子 树 还 是 右 子 树，树 无 此 限 制；三 是 二 叉 树 允 许 为 空，树 一 般 不 允 许 为 空(个 别 书

35、 上 允 许 为 空)。二 叉 树 不 是 树 的 特 例。2.【解 答】具 有 3个 结 点 的 二 叉 树 3.解 答：先 根 序 列：A B C D E F G H I J;中 根 序 列：B C D A F E H J I G;后 根 序 列：D C B F J I H G E A o4.(l)kx(h 为 层 数)(2)因 为 该 树 每 层 上 均 有 K-个 结 点，从 根 开 始 编 号 为 1,则 结 点 i的 从 右 向 左 数 第 2 个 孩 子 的 结 点 编 号 为 kio设 n 为 结 点 i 的 子 女，则 关 系 式(i-l)k+2=nl)的 前 一 结 点 编

36、 号 为 n-1(其 最 右 边 子 女 编 号 是(nT)*k+l),故 结 点 n 的 第 i个 孩 子 的 编 号 是(n-l)*k+l+i。(4)根 据 以 上 分 析，结 点 n 有 右 兄 弟 的 条 件 是，它 不 是 双 亲 的 从 右 数 的 第 一 子 女，即(n-l)%k!=0,其 右 兄 弟 编 号 是 n+1。6.(1)图 略；(2)前 序 序 列 中 序 序 列 后 序 序 列(3)图 略。A B C E D F H G IJE C B H F D J I G AE C H F J I G D B A7.字 符 A,B,C,D 出 现 的 次 数 为 9,1,5,3

37、。其 哈 夫 曼 编 码 如 下 A:1,B:000,C:01,D:001五、算 法 设 计 题 1.题 目 分 析 二 叉 树 是 递 归 定 义 的，以 递 归 方 式 建 立 最 简 单。判 定 是 否 是 完 全 二 叉 树，可 以 使 用 队 列，在 遍 历 中 利 用 完 全 二 叉 树“若 某 结 点 无 左 子 女 就 不 应 有 右 子 女”的 原 则 进 行 判 断。BiTree Great()建 立 二 叉 树 的 二 叉 链 表 形 式 的 存 储 结 构 ElemType x;BiTree bt;scanf(“%d”，&x);本 题 假 定 结 点 数 据 域 为 整

38、 型 if(x=0)bt=null;else if(x0)bt=(BiNode*)malloc(sizeof(BiNode);bt-data=x;bt-lchild=creat();bt-rchild=creat();else error(输 入 错 误)；return(bt);/结 束 BiTreeint JudgeComplete(BiTree bt)判 断 二 叉 树 是 否 是 完 全 二 叉 树，如 是，返 回 1,否 则，返 回 0int tag=0;BiTree p=bt,Q;/提 队 列，元 素 是 二 叉 树 结 点 指针，容 量 足 够 大 if(p=null)return

39、(1);Queuelnit(Q);Queuein(Q,p);初 始 化 队 列，根 结 点 指 针 入 队 while(JQueueEmpty(Q)p=QueueOut(Q)：出 队 if(p-lchiId&!tag)Queuein(Q,p-lchild);/庄 子 女 入 队 else if(p-lchild)return 0;前 边 已 有 结 点 为 空，本 结 点 不 空 else tag=l;首 次 出 现 结 点 为 空 if(p-rchiId&!tag)Queuein(Q,p-rchild);/名 子 女 入 队 else if(p-rchild)return 0;else ta

40、g=l;/whilereturn 1;/JudgeComplete算 法 讨 论 完 全 二 叉 树 证 明 还 有 其 他 方 法。判 断 时 易 犯 的 错 误 是 证 明 其 左 子 树 和 右 子 数 都 是 完 全 二 叉 树，由 此 推 出 整 棵 二 叉 树 必 是 完 全 二 叉 树 的 错 误 结 论。2.题 目 分 析 后 序 遍 历 最 后 访 问 根 结 点，即 在 递 归 算 法 中，根 是 压 在 栈 底 的。采 用 后 序 非 递 归 算 法，栈 中 存 放 二 叉 树 结 点 的 指 针，当 访 问 到 某 结 点 时，栈 中 所 有 元 素 均 为 该 结 点

41、 的 祖 先。本 题 要 找 P和 q 的 最 近 共 同 祖 先 结 点 r,不 失 一 般 性，设 P在 q 的 左 边。后 序 遍 历 必 然 先 遍 历 到 结 点 P,栈 中 元 素 均 为 P 的 祖 先。将 栈 拷 入 另 一 辅 助 栈 中。再 继 续 遍 历 到 结 点 q 时，招 栈 中 元 素 从 栈 顶 开 始 逐 个 到 辅 助 栈 中 去 匹 配，第 一 个 匹 配(即 相 等)的 元 素 就 是 结 点 P 和 q 的 最 近 公 共 祖 先。typedef structBiTree t;int tag;/tag=0表 示 结 点 的 左 子 女 已 被 访 问，

42、tag=l表 示 结 点 的 右 子 女 已 被 访 问 stack;stack s,si口；栈，容 量 够 大 BiTree Ancestor(BiTree ROOT,p,q,r)求 二 叉 树 上 结 点 p和 q 的 最 近 的 共 同 祖 先 结 点 r。top=0;bt=ROOT;while(bt!=null|top0)while(bt!=null&bt!=p&bt!=q)结 点 入 栈 s+topL t=bt;stop.tag=0;bt=bt-lchild;/沿 左 分 枝 向 下 if(bt=p)不 失 一 般 性，假 定 P在 q 的 左 侧，遇 结 点 P 时，栈 中 元 素

43、 均 为 P 的 祖 先 结 点 for(i=l;i0;i)/;将 栈 中 元 素 的 树 结 点 到 si去 匹 配 pp=si.t;for(j=topl;j0;j)if(slj.t=pp)printf(p 和 q 的 最 近 共 同 的 祖 先 已 找 到);return(pp);)while(top!=0&stop.tag=l)top一;退 栈 if(top!=0)s top.tag=l;bt=s top.t-rchiId;沿 右 分 枝 向 下 遍 历 结 束 while(bt!=null|top0)return(null);/q,P 无 公 共 祖 先)结 束 Ancestor3.解

44、 答：本 算 法 要 借 用 队 列 来 完 成，其 基 本 思 想 是，只 要 队 列 不 为 空，就 出 队 列，然 后 判 断 该 结 点 是 否 有 左 孩 子 和 右 孩 子，如 有 就 依 次 输 出 左、右 孩 子 的 值,然 后 让 左、右 孩 子 进 队 列。void layorder(bitreptr T)initqueue(q)if(T!=NULL)printf(%f”,T-data);enqueue(q,T);while(not emptyqueue(q)outqueue(q,p);if(p-lchild!=NULL)printf(“%f”，p-lchild-data)

45、;/*队 列 初 始 化*/*入 队 列*/*若 队 列 非 空*/*出 队*/enqueue(q,p-lchi Id);/*入 队 列*/)if(p-rchild!=NULL)printf(“”,p-rchild-data);enqueue(q,p-rchiId);/*入 队 列*/)4.【解 答】Void PreOrder(BiTree root)/*先 序 遍 历 二 叉 树 的 非 递 归 算 法*/(InitStack(&S);p=root;while(p!=NULL|!IsEmpty(S)if(p!=NULL)(Visit(p-data);push(&S,p);p=p-Lchild

46、;elsePop(&S,&p);p=p-RChild;5.void InOrder(BiTree bt)BiTree s,p=bt;s是 元 素 为 二 叉 树 结 点 指 针 的 栈，容 量 足 够 大 int top=0;while(p I|top0)while(p)s+top=p;bt=p-lchild;中 序 遍 历 左 子 树 if(top0)p=stop-;printf(p-data);p=p-rchild;退 栈,访 问，转 右 子 树 6.BiTree Copy(BiTree t)复 制 二 叉 树 tBiTree bt;if(t=null)bt=null;else bt=(B

47、iTree)malloc(sizeof(BiNode);bt-data=t-data;bt-lchild=Copy(t-lchiId);bt-rchild=Copy(t-rchiId);)return(bt);结 束 Copy7.题 目 分 析 叶 子 结 点 只 有 在 遍 历 中 才 能 知 道，这 里 使 用 中 序 递 归 遍 历。设 置 前 驱 结 点 指 针 pre,初 始 为 空。第 一 个 叶 子 结 点 由 指 针 head指 向，遍 历 到 叶 子 结 点 时，就 将 它 前 驱 的 rchild指 针 指 向 它，最 后 叶 子 结 点 的 rchiId为 空。Linke

48、dList head,pre=null;全 局 变 量 LinkedList InOrder(BiTree bt)中 序 遍 历 二 叉 树 bt,将 叶 子 结 点 从 左 到 右 链 成 一 个 单 链 表，表 头 指 针 为 headif(bt)InOrder(bt-lchild);中 序 遍 历 左 子 树 if(bt-lchild=null&bt-rchild=nul 1)叶 子 结 点 if(pre=null)head=bt;pre=bt;处 理 第 一 N 十 子 结 点 elsepre-rchild=bt;pre=bt;将 叶 子 结 点 链 入 链 表 InOrder(bt-

49、rchiId);中 序 遍 历 左 子 树 pre-rchild=null;设 置 链 表 尾)return(head);/InOrder时 间 复 杂 度 为 0(n),辅 助 变 量 使 用 head和 pre,栈 空 间 复 杂 度 0(n)8.题 目 分 析 删 除 以 元 素 值 x 为 根 的 子 树，只 要 能 删 除 其 左 右 子 树，就 可 以 释 放 值 为 x 的 根 结 点，因 此 宜 采 用 后 序 遍 历。删 除 值 为 x 结 点，意 味 着 应 将 其 父 结 点 的 左(右)子 女 指 针 置 空，用 层 次 遍 历 易 于 找 到 某 结 点 的 父 结

50、点。本 题 要 求 删 除 树 中 每 一 个 元 素 值 为 x 的 结 点 的 子 树，因 此 要 遍 历 完 整 棵 二 叉 树。void DeleteXTree(BiTree bt)删 除 以 bt 为 根 的 子 树 DeleteXTree(bt-lchiId);DeleteXTree(bt-rchild);删 除 bt 的 左 子 树、右 子 树 free(bt);/DeleteXTree 释 放 被 删 结 点 所 占 的 存 储 空 间 void Search(B:Tree bt,ElemType x)在 二 叉 树 上 查 找 所 有 以 x 为 元 素 值 的 结 点，并