i/2 i+1 2i+3 +1)Q2i+3 (a)和计结点在同一层 (b)和计1结点不在同一层 图66完全二叉树中结点i和1 ●对于i>1,可分为两种情况: (1)设第(1 syslog2n层的第一个结点的编号为i(由二叉 树的定义和性质2可知i=21),则其左孩子必定为j+1层的 第一个结点,其编号为2=2×21=2i。如果2i>n,则无左孩 子 其右孩子必定为第j+1层的第二个结点,编号为2+1。若 2+1>n,则无右孩子 邮电大学自动化学院 16
北京邮电大学自动化学院 16 图6.6 完全二叉树中结点i和i+1 [i/2] i i+1 2i 2i+1 2(i+1) 2i+3 (a) i和i+1结点在同一层 i+1 2(i+1) 2i+3 i 2i 2i+1 (b)i和i+1结点不在同一层 ⚫ 对于i>1，可分为两种情况： ⚫ （1）设第j（1jlog2n)层的第一个结点的编号为i（由二叉 树的定义和性质2可知i＝2 j-1），则其左孩子必定为j＋1层的 第一个结点，其编号为2 j＝2×2 j-1＝2i。如果2i>n，则无左孩 子； ⚫ 其右孩子必定为第j＋1层的第二个结点，编号为2i＋1。若 2i+1>n，则无右孩子
i/2 i+1 2i+3 +1)Q2i+3 (a)和计结点在同一层 (b)和计1结点不在同一层 图66完全二叉树中结点i和1 (2)假设第(1slog2n层上的某个结点编号为(21s<2 1),且2i+1n,则其左孩子为2,右孩子为2+1 ●又编号为i+1的结点是编号为的结点的右兄弟或堂兄弟。若它有 左孩子,则其编号必定为2i+2=2×(i+1);若它有右孩子, 则其编号必定为2+3=2×(i+1)+1。 北京邮电大学自动化学院
北京邮电大学自动化学院 17 图6.6 完全二叉树中结点i和i+1 [i/2] i i+1 2i 2i+1 2(i+1) 2i+3 (a) i和i+1结点在同一层 i+1 2(i+1) 2i+3 i 2i 2i+1 (b)i和i+1结点不在同一层 ⚫ （2）假设第j（1jlog2n)层上的某个结点编号为i（2 j-1i<2j - 1)，且2i＋1<n，则其左孩子为2i，右孩子为2i＋1. ⚫ 又编号为i＋1的结点是编号为i的结点的右兄弟或堂兄弟。若它有 左孩子，则其编号必定为2i＋2＝2×（i＋1）；若它有右孩子， 则其编号必定为2i＋3＝2×（i＋1）＋1
i/2 3计qH+i+3Gi+Qi3 (a)i和+1结点在同一层 ●(b和+1结点不在同一层 图6.6完全二叉树中结点和i+1 当=1时,就是根,因此无双亲。 当i>1时,如果i为左孩子,即2×(i2)=i,则2是的双 亲;如果i为右孩子,i=2p+1,i的双亲应为p,p=(i 1)/2=2」。证毕 北京邮电大学自动化学院
北京邮电大学自动化学院 18 ⚫ 图6.6 完全二叉树中结点i和i+1 [i/2] i i+1 2i 2i+1 2(i+1) 2i+3 (a) i和i+1结点在同一层 i+1 2(i+1) 2i+3 i 2i 2i+1 ⚫ (b)i和i+1结点不在同一层 ⚫ 当i＝1时，就是根，因此无双亲。 ⚫ 当i>1时，如果i为左孩子，即2×（i/2)=i，则i/2是i的双 亲；如果i为右孩子，i＝2p+1，i的双亲应为p，p＝（i－ 1）/2=i/2。 证毕
6.23二叉树的存储结构 1、顺序存储结构 o define maX-TREE-SIZE 100 Typedef TelemType SqBitreeI MAX-TREE-SIzE] ● SaBitree bt; ●按照顺序存储结构的定义,在此约定,用一组地址连续的 存储单元依次自上而下,自左至右存储完全二叉树上的结 点元素,即将完全二叉树上编号为的的结点元素存储在 如上定义的一维数组中下标为1的分量中。 北京邮电大学自动化学院 19
北京邮电大学自动化学院 19 ⚫ 1、顺序存储结构 6.2.3 二叉树的存储结构 ⚫ #define MAX-TREE-SIZE 100 ⚫ Typedef TelemType SqBiTree[ MAX-TREE-SIZE]; ⚫ SqBitree bt; ⚫ 按照顺序存储结构的定义，在此约定，用一组地址连续的 存储单元依次自上而下，自左至右存储完全二叉树上的结 点元素，即将完全二叉树上编号为i的的结点元素存储在 如上定义的一维数组中下标为i-1的分量中
1、顺序存储结构 完全二叉树 面①①① 123456789101112 a bc def k 北京邮电大学自动化学院
北京邮电大学自动化学院 20 a b c d e f g h i j k l 1 2 3 4 5 6 7 8 9 10 11 12 a b c d e f g h i j k l 1、顺序存储结构 完全二叉树