二叉树是每个结点的度都为2的有序树,它的特点是每个结点至多有两棵子树。二叉树与树有区别:树至少应有一个结点,而二叉树可以为空;树的子树没有顺序,但如果二叉树的根结点只有一棵子树,必须明确区分它是左子树还是右子树,因为两者将构成不同形态的二叉树。因此,二叉树不是树的特例。它们是两种不同的数据结构。二叉树有5种基本形态:图-1二叉树的五种基本形态(a)空二叉树(b)只有根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左右子树均不为空的二叉树2、特殊形态的二叉树:满二叉树。满二叉树:定义:除最后一层无任何子结点外,每一层上的所有结点都有两个子结点。启发式教学示例法图示法深度为k,且有2k-1个结点的二叉树。图-2满二叉树1234567深度:K=3节点数:n=23-1叶子数:N=23-1二、遍历二叉树遍历二叉树:指按一定的规律对二叉树的每个结点,访问且仅访问一次的处理过程。遍历对线性结构是容易解决的。而二叉树是非线性的,因而需要寻找一种规律,使二叉树上的结点能排列在一个线性队列上,从而便于遍历。遍历的次序:假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树,规定先左后右,则只有前三种情况,分别规定为:DLR——先(根)序遍历,LDR——中(根)序遍历,LRD——后(根)序遍历。例题:图-3图-4先序遍历:先序遍历:ABDGCEFABDFHCEG中序遍历:中序遍历:DGBAECFDHFBACGE后序遍历:后序遍历:GDBEFCAHFDBGECA作业、思考题:课后题1、3、4、5、7题课后小结:本节课结合教学大纲对教材和学生进行充分的分析,通过复习检查,创设情景,导入新课,运用各种教学方法,讲授新课,并对重、难点逐个突破,讨论归纳,突出重点、难点,布置作业,延伸到下节课内容的教学过程,让学生达到我们预定的知识、能力、技能、素质目标,这节课的教学效果必定显著。
全文预览
