第+6+章+二叉树

《第+6+章+二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二叉树引言在前面几章里讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。而现实中的许多事物的关系并非如此简单，如人类社会的族谱、各种社会组织机构以及城市交通、通讯等，这些事物中的联系都是非线性的，采用非线性结构进行描绘会更明确和便利。所谓非线性结构，是指在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树结构和图结构是非常重要的非线性结构。1.熟练掌握二叉树的结构特性，了解相应的证明方法。2.熟悉二叉树的各种存储结构的特点及适用范围。3.遍历二叉树是二叉树各种操

2、作的基础。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。4.理解二叉树线索化的实质.熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。[学习目标]【重点和难点】重点：二叉树和树的遍历及其应用难点：编写实现二叉树的各种操作的递归算法知识点二叉树的类型定义二叉树的存储表示二叉树的遍历以及其它操作的实现线索二叉树最优树和赫夫曼编码1、二叉树的概念（二叉树的定义、术语、ADT定义）；2、二叉树性质；3、二叉树的存储结构（顺序、链式表示）；4、二叉树的遍历及二叉树遍历算法的应用5、线索二叉树6、哈夫

3、曼树、哈夫曼编码。教学内容树型结构（非线性结构）结点之间有分支具有层次关系例自然界：树人类社会家谱行政组织机构计算机领域编译：用树表示源程序的语法结构数据库系统：用树组织信息算法分析：用树描述执行过程国务院山东省北京市西藏自治区…泰安市青岛市威海市…泰山区岱岳区…宁阳市6.1二叉树的概念与性质二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树均可与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。6.2.1二叉树的定义及相关术语二叉树是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右

4、子树的二叉树组成。定义特点1、每个结点最多有俩孩子(二叉树中不存在度大于2的结点)。2、子树有左右之分，其次序不能颠倒。3、二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。树当结点只有一个孩子时，就无须区分它是左还是右。（也就是二叉树每个结点位置或者说次序都是固定的，可以是空，但是不可以说它没有位置，而树的结点位置是相对于别的结点来说的，没有别的结点时，它就无所谓左右了），因此二者是不同的。这是二叉树与树的最主要的差别。二叉树不是树的特殊情况，它们是两个概念。注AB具有两个结点的树只有一种状

5、态ABAB具有两个结点的二叉树有两种状态二叉树的5种基本形态(a)空二叉树(b)根和空的左右子树(c)根和左子树(d)根和右子树(e)根和左右子树注：虽然二叉树与树概念不同，但有关树的基本术语对二叉树都适用。树的逻辑结构：树中任一结点都可以有零个或多个直接后继结点但至多只能有一个直接前趋结点。T3T2T1基本术语：结点的度：结点拥有的子树数。度=0叶子终端结点度≠0分支结点非终端结点根结点以外的分支结点称为内部结点树的度：树内各结点的度的最大值。双亲孩子兄弟结点的祖先：从根到该结点所经分支上的所有结点。结点的子孙：以某结点为根的子树中的任一结点。第1层第2层第3层树的深度：树中结点的最大层

6、次。有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子）。无序树：树中结点的各子树无次序。结点：数据元素+指向子树的分支根结点：非空树中无前驱结点的结点森林：是m(m≥0)棵互不相交的树的集合。一棵树可以看成是一个特殊的森林。把根结点删除树就变成了森林。给森林中的各子树加上一个双亲结点，森林就变成了树。树森林一定是不一定是EFGHIABCDJKLM第4层堂兄弟双亲在同一层的结点满二叉树(Fullbinarytree)特点：每一层上的结点数都达到最大。叶子全部在最底层。编号规则：从根结点开始，自上而下，自左而右。一棵二叉树中，如果所有分支结点都存在左子树和右子树并且所有叶子结点在同

7、一层上，称为满二叉树。245367124531完全二叉树(Completebinarytree)深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树。特点：叶子只可能分布在层次最大的两层上。对任一结点，如果其右子树的最大层次为l，则其左子树的最大层次必为l或l+1。满二叉树完全二叉树是定一不一定是245361完全二叉树245361非完全二叉树正则二叉树