2、完全二叉树 (1)定义:当一棵二叉树,除最底层以外的每一层的 结点个数都达到最大值,而最底层的结点又集中在从最 左边开始的若干连续位置上,则该树称为完全二叉树。 (2)特点 在层数为H的完全二叉树中,位于第K(K<H)层上的 结点数应为2K-1个而第H层上的结点数不能确定。 在完全二叉树中,度为1的结点只能在最底层,且叶 结点也在最底层,而非最底层的结点的度只能为2。 满二叉树一定是完全二叉树。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 2、完全二叉树 （１）定义：当一棵二叉树，除最底层以外的每一层的 结点个数都达到最大值，而最底层的结点又集中在从最 左边开始的若干连续位置上，则该树称为完全二叉树。 （２）特点： 在层数为H的完全二叉树中，位于第K（K<H)层上的 结点数应为2 K－1个,而第H层上的结点数不能确定。 在完全二叉树中，度为１的结点只能在最底层，且叶 结点也在最底层，而非最底层的结点的度只能为２。 满二叉树一定是完全二叉树
(3)完全二叉树的图例如图5-7所示 A B E 图5-7层次高废为四的完全二又树的示意图 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 (3) 完全二叉树的图例如图5－７所示 图5－7层次高度为四的完全二叉树的示意图 A B C D E F G H I J K L
四、二叉树的存储表示 1、二叉树的顺序存储表示 (1)完全二叉树的顺序存储 存储方法:设完全二叉树中有n个结点,对 这n个结点按层次从上到下、同一层从左往有 的原则,用自然数1~n依次编号,作为该结 点的号数,并设置一个一维数组作为存储该树 的存储区,而结点的号数又是该结点在数组中 的下标值,用这种方法存储的完全二叉树,称 为完全二叉树的顺序存储。 例如,图5-6给出的满二叉树的顺序存储表示 如图5-8所示。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 1、二叉树的顺序存储表示 （1) 完全二叉树的顺序存储 存储方法：设完全二叉树中有ｎ个结点，对 这ｎ个结点按层次从上到下、同一层从左往右 的原则，用自然数１～ｎ依次编号，作为该结 点的号数，并设置一个一维数组作为存储该树 的存储区，而结点的号数又是该结点在数组中 的下标值，用这种方法存储的完全二叉树，称 为完全二叉树的顺序存储。 例如，图5－6给出的满二叉树的顺序存储表示 如图5－8所示。 四、二叉树的存储表示
23456789101112131415 Tree ABICIDEFGHIIJKILMIN O 图5-8完全二又树的顺序存储表示示意图 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 N A B C D E F G H I J K L M O 图5－８完全二叉树的顺序存储表示示意图 Tree １ 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Ａ B C D E F G H I J K L M N O
存储特点: 在用顺序存储方法存储的完全二叉树中,查 找其孩子结点及双亲结点都十分方便。这是因 为:该完全二叉树的根序号为1,其根的左子 树结点的序号就是2;右子树结点的序号为3 (若存在的话),显然,设某一个结点的序号 为i,则其左孩子结点的序号为2i(当然2 i<=n),而右孩子结点的序号为2i+1 (2i+1<=n);当i=1时,该结点无 双亲结点,当立>1时,其双亲结点的序号是 i/2取整。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 存储特点： 在用顺序存储方法存储的完全二叉树中，查 找其孩子结点及双亲结点都十分方便。这是因 为：该完全二叉树的根序号为１，其根的左子 树结点的序号就是２；右子树结点的序号为３ （若存在的话），显然，设某一个结点的序号 为ｉ，则其左孩子结点的序号为２ｉ（当然２ ｉ<=n)，而右孩子结点的序号为２ｉ＋１ （２ｉ＋１<=n）；当ｉ＝１时，该结点无 双亲结点，当ｉ>1时，其双亲结点的序号是 ｉ／２取整