1、6.2 二叉树6.2.1 二叉树的定义（1）定义）定义 二叉树（二叉树（Binary Tree）：是另一种树型结构。：是另一种树型结构。特点：特点：每个结点至多只有两棵子树（即二叉树中不存在度大于每个结点至多只有两棵子树（即二叉树中不存在度大于2 的结点）。的结点）。子树有左右之分，其次序不能任意颠倒。子树有左右之分，其次序不能任意颠倒。（2）图形表）图形表示示 (a)(b)(c)(d)(e)图图6.3二叉树的二叉树的5种基本形态种基本形态(a)空二叉树空二叉树(b)仅有根结点的二叉树仅有根结点的二叉树(c)右子树为空的二叉树右子树为空的二叉树(d)左、右子树均非空的二叉树左、右子树均非空的二
2、叉树(e)左子树为空的二叉树左子树为空的二叉树用归纳法用归纳法证明证明：i=1 层时，只有一个根结点，2i-1=20=1；假设对所有的 j，1 j i，命题成立;二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2i-2 2=2i-1。性质性质 1：在二叉树的第 i 层上至多有2i-1 个结点。(i1)6.2.2 二叉树的性质二叉树的性质证明：证明：基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+2k-1=2k-1 性质性质 2：深度为 k 的二叉树上至多含 2k-1 个结点（k1）证明：证明：设设 二叉树上结点总数 n=n0+n1+n2又又 二叉树上分支总数 b=n1+
3、2n2而 b=n-1=n0+n1+n2-1由此，由此，n0=n2+1性质性质 3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1除根结点外，其余结点都有一个分支进入，设除根结点外，其余结点都有一个分支进入，设b为分支总数，则为分支总数，则n=b+1。两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。123456789 10 11 12 13 14 15这种树的特点是每一层上的结点数都是最大结点数。完全二叉树完全二叉树：完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号为编号为 1 至
4、至 n 的结点的结点一一对应。abcdefghij可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左至右。由此可引出完全二叉树。完全二叉树的特点完全二叉树的特点（1）叶子结点只可能在层次最大的两层出现；（2）对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次为l或l+1。abcdefghij证明：证明：设设 完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n k 因为因为 k 只能是整数，因此，只能是整数，因此，k=log2n +16.3遍历二叉树和线索二叉树b6.3.1遍历二叉树b 如果按某条搜索路径巡访树中每个
5、结点，使得每个结点均被访问一次，而且仅被访问一次。ABCDGEF先序遍历二叉树的操作定义为：b 若二叉树为空，则空操作；否则b （1）访问根结点；b （2）先序遍历左子树；b （3）先序遍历右子树。b A B C D F E GABCDGEF中序遍历二叉树的操作定义为：b若二叉树为空，则空操作；否则b（1）中序遍历左子树；b（2）访问根结点；b（3）中序遍历右子树。b C B D F A G EABCDGEF中序遍历二叉树示例b中序遍历二叉树得:ba+b*(c-d)-e/f-+a*e/-fbdc后序遍历二叉树的操作定义为：b 若二叉树为空，则空操作；否则b （1）后序遍历左子树；b （2）后序遍历右子树；b （3）访问根结点。b C F D B G E AABCDGEF已知结点的先序序列和中序序列ACBEDFGABCDEFGABCFDEG
