用数组实现完全二叉树 完全二叉树的下标公式 按层次顺序将一氰有n个结点的完金二叉树的所有结点从0到n-】 编号,就得到结点的一个性序列 从结点的编号就可以推知其父母、子女、兄弟 的编号 ■当2i+1<n时,结点的左子女是结点2i+1,否则 结点没有左子女 当2+2<n时,结点的右子女是结点2+2,否则 吧四结点没有右子女 完全二叉树的下标公式 454穿线二叉树 当0<i<n时,结点的父母是结点L(1)/2」 穿线树:在二叉链表中 空左指针指向结点在某种周游序列下的前驱 当i为偶数且0<i<n时,结点左兄弟是结点-1 空的右指针指向结点在同一种周游序列下的后继 否则结点没有左兄弟 中序穿线树,前序穿线树,后序穿线树 半索vs全到 当为奇数且i+1<n时,结点的右兄弟是结点 ■目的:利用空指针的存储空间,建立周游线索 i+1,否则结点没有右兄弟 叔有。轨印当究 口 张鲁写 前有,聊脂究 穿线二叉树 中序穿线二叉树:示例 ■标志位1Tag和rTag:区分线索和指针 ∏Tag=0,left为左子女指针 打Tag=1,left为前驱线索 ■A rTag=0, righti为右子女指针 rTag=1, right为后继指针 4D画 leftITag WHIA ■ 真大_血单 大息 1111 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 61 用数组实现完全二叉树 0 1 2 3 4 5 6 7 8 按层次顺序将一棵有n个结点的完全二叉树的所有结点从0到n-1 编号，就得到结点的一个线性序列 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 62 完全二叉树的下标公式 „ 从结点的编号就可以推知其父母、子女、兄弟 的编号 „ 当2i+1<n时，结点i的左子女是结点2i+1，否则 结点i没有左子女 „ 当2i+2<n时，结点i的右子女是结点2i+2，否则 结点i没有右子女 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 63 完全二叉树的下标公式 „ 当0<i<n时，结点i的父母是结点 ⎣(i-1)/2⎦ „ 当i为偶数且0<i<n时，结点i的左兄弟是结点i-1， 否则结点i没有左兄弟 „ 当i为奇数且i+1<n时，结点i的右兄弟是结点 i+1，否则结点i没有右兄弟 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 64 4.5.4 穿线二叉树 „ 穿线树：在二叉链表中 „ 空左指针指向结点在某种周游序列下的前驱 „ 空的右指针指向结点在同一种周游序列下的后继 „ 中序穿线树，前序穿线树，后序穿线树 „ 半索 vs 全索 „ 目的：利用空指针的存储空间，建立周游线索 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 65 穿线二叉树 „ 标志位lTag和rTag：区分线索和指针 „ lTag = 0, left为左子女指针 „ lTag = 1, left为前驱线索 „ rTag= 0, right为右子女指针 „ rTag = 1, right为后继指针 left lTag info rTag right 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 66 中序穿线二叉树 ：示例 ∧ ∧ A B E C F G H I t D