在线教务辅导网:Р教材其余课件及动画素材请查阅在线教务辅导网РQQ:349134187 或者直接输入下面地址:Рhttp://shop106150152.Р第5章二叉树Р5.1Р二叉树概述Р5.2Р二叉树的存储结构Р5.3Р遍历二叉树Р5.4Р哈夫曼树及哈夫曼编码Р本章讨论二叉树,它是一种重要的非线性数据结构,有着广泛的用途。? 本章主要介绍以下几个方面的内容:?二叉树的定义及性质;?二叉树的存储实现(顺序存储和链式存储);?遍历二叉树(即对二叉树存储结点访问的各种形式);?哈夫曼树及编码。Р5.1 二叉树概述Р所谓“二叉树”,是一个由结点组成的有限集合。这个集合或为空,或由一个称为根的结点以及两棵不相交的二叉树组成,这两棵二叉树分别称为根结点的左子树和右子树。Р5.1.1 二叉树的基本概念Р当二叉树非空时,通过结点间的边来表示从一个结点到它的两个子结点间的联系,这个结点称为父结点,两个子结点称为父结点的孩子。二叉树有如下的特征:Р二叉树可以是空的,空二叉树没有任何结点;?二叉树上的每个结点最多可以有两棵子树,这两棵子树是不相交的;?二叉树上一个结点的两棵子树有左、右之分,次序是不能颠倒的。Р图5-2 两棵不同的二叉树Р从二叉树中的一个结点往下,到达它的某个子、孙结点时所经由的路线,称为一条“路径”。对于路径来说,从开始结点到终止结点,中间经过的结点个数,称为路径的“长度”。从根结点开始、到某个结点的路径长度,称为该结点的“深度”。Р在二叉树中,由于每个非根结点只有一个父结点,所以从二叉树的任一结点到它的子、孙结点的路径都是唯一的。? 二叉树是一种层次结构。通常,把它的根算作第0层,其余结点的层次值,为其父结点所在层值加1。在二叉树里位于相同层的结点的深度都是相同的。? 一棵二叉树的“高度”,是指该二叉树的最大层次数值。
全文预览
