二叉树遍历课件

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