《二叉树》-课件.ppt

二叉树 二叉树是一类非常重要的特殊的树形结构，它递归定义下： 二叉树T是有限个结点的集合，它或者是空集，或者由一个根结 点u以及分别称为左子树和右子树的2棵互不相交的二叉树u(1) 和u(2)组成。子树u(1)和u(2)有时分别称为T的第一和第二 子树。 二叉树与树的区别 判断：1 二叉树是度小于等于2的有序树。 判断：2 二叉树的度小于等于2。 二叉树性质 高度为h=0的二叉树至少有h+1个结点。 高度不超过h的二叉树至多有2的h+1次方-1个结点。 含有h=1个结点的二叉树的高度至多为n-1。 含有h=1个结点的二叉树的高度至少为[logn]。 满二叉树与近似二叉树 一棵高度为h且有2的h+1次方-1个结点的二叉树称为满二叉树。 若一棵二叉树至多只有最下面的2层上结点的度数可以小于2，并且最下面一层上的结点都集中在该层的最左边，则称这种二叉树为近似满二叉树（有时也称为完全二叉树）。 二叉树的遍历 二叉树的遍历与树遍历的递归过程一致。 二叉树的前、后序结果与树的前后序过程完全一样。 由于二叉树严格分左右，中序遍历的结果与树有区别。 二叉树前序遍历可简单记成:根左右。 二叉树中序遍历可简单记成:左根右。 二叉树后序遍历可简单记成:左右根。 二叉树中序遍历演示 二叉树数目： 含有n个结点的不同二叉树的数目有 第7章 习题判断 树 前序和中序无法确定树 后序和中序无法确定树 前序和后序可以确定树 二叉树 前序和中序可以确定二叉树 后序和中序可以确定二叉树 前序和后序无法确定二叉树 已知后中序如何确定二叉树 已知一棵二叉树的中序序列 BDCEAFHG，后序序列 DECBHGFA， 请画出该二叉树。再求出前序。 已知后中序如何确定二叉树 已知一棵二叉树的中序序列 BDCEAFHG，后序序列 DECBHGFA， 请画出该二叉树。再求出前序。 已知后中序如何确定二叉树 已知一棵二叉树的中序序列 BDCEAFHG，后序序列 DECBHGFA， 请画出该二叉树。再求出前序。 已知后中序如何确定二叉树 已知一棵二叉树的中序序列 BDCEAFHG，后序序列 DECBHGFA， 请画出该二叉树。再求出前序。 树和二叉树的转换 任意一棵树（森林）都可以通过左儿子右兄弟的对应法则对应唯一一棵二叉树。 任意一棵二叉树也可以通过左儿子右兄弟的对应法则对应一棵森林。 树和二叉树转换演示 树和二叉树三序遍历的关系 树中结点和度之间的关系 假设树A的度为K，且度为0的结点(叶子)有 个。 二叉树中公式变形 线索二叉树 第7章树：习题 由3个结点可以构造出多少种不同的二叉树____【福建2007专升本】 A 2 B 3 C 4 D 5 一棵非空二叉树中，(设根结点在第0层)，在第i层上最多有____个结点【福建2006专升本】 A 2的i+1次方 B 2i C 2的i-1次方 D 2的i次方 一个有n个结点的k叉树,树中所有结点的度数之和为____【福建2006专升本】 A k+n B n-1 C k*n D n*n 树是结点的集合,它____根结点【福建2009专升本】 A 有0个或者1个 B 有0个或多个 C 有且只有1个 D 有1个或1个以上 第7章 习题 二叉树的前序遍历序列和中序遍历序列相同的条件是_____ 若一棵度为4的树中度为1、2、3、4的结点个数分别为4、3、2、2，则该树叶子结点的个数是多少？总结点个数是多少 在一棵二叉树中，度为2的结点个数为100 则叶子结点有____个 已知二叉树有50个叶子结点，则该二叉树的总结点数至少为___个 第7章 习题 多项选择 下列说法正确的有: 若有一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点。 若有一个结点是某二叉树的前序遍历的最后一个结点，则它必是该二叉树的中序遍历最后一个结点。 若有一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点。 若有一个叶子是某二叉树的前序遍历的最后一个结点，则它必是该二叉树的中序遍历最后一个结点。 已知某二叉树的后序遍历序列是DABEC,中序遍历序列是DEBAC，它的前序遍历序列是：_________ 已知某二叉树的前序遍历序列是ABCDEFG,中序遍历序列是CBEDAFG,则其二叉树为：__________ 第7章 习题判断 树和二叉树都是分支结构 二叉树是度为2的树 满二叉树的结点个数必为奇数 前序遍历和后序遍历可唯一确定一个二叉树 树中元素之间是多对多关系 用树的前序遍历和中序序列可以导出树的后序序列 在前序、中序、后序遍历序列中，叶子结点出现的相对次序