文档介绍：该【数据结构第六章-二叉树 】是由【明月清风】上传分享，文档一共【48】页，该文档可以免费在线阅读，需要了解更多关于【数据结构第六章-二叉树 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。1
第6章 二叉树和树
单击此处添加副标题
单击此处添加正文，文字是您思想的提炼，请尽量言简意赅的阐述观点。
线索二叉树的建立、使用；
树的各种存储结构及其特点；
树、森林与二叉树之间的转换；
树、森林的遍历。
【掌 握】：
【重点掌握】：
二叉树的结构特性;
二叉树的各种存储结构的特点及适用范围;
二叉树各种遍历策略的递归算法，且能灵活运用遍历算法实现二叉树的其它操作；
最优二叉树的特性，建立最优树和哈夫曼编码的方法。
线性结构的特点是逻辑结构简单，易于进行查找、删除、插入等操作。其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。
非线性结构是指在该结构中至少存在一个数据元素有两个或两个以上的直接前驱或直接后继。
树形结构是一类重要的非线性结构。树形结构是结点之间有分支、并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。
图形结构是十分重要的非线性结构，可以用来描述客观世界中广泛存在的网状结构的关系。
二叉树
二叉树的基本概念
(Binary Tree)
(1)定义：二叉树是n（n>=0）个数据元素的集合，该集合或为空，或含有唯一的称为根的元素，且其余元素分成两个互不相交的子集，每个子集自身也是一棵二叉树，分别称为左子树和右子树。
说明:
1）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念
2）二叉树中每个结点最多有两棵子树,二叉树每个结点度小于等于2
A
B
C
D
E
F
G
5
3）左、右子树不能颠例
二叉树结点的子树要区分左子树和右子树：即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。
A
B
A
B
两棵不同的二叉树
(2) 二叉树的 5 种基本形态
φ
空二叉树
根和空的左右子树
根和左子树
根和右子树
根和左右子树
2. 二叉树的基本术语
1) 孩子(child)：结点的子树的根称为该结点的孩子；左孩子，右孩子。
2) 双亲(parents)：孩子结点的上层结点。
3) 兄弟(sibling)：同一双亲的孩子结点；堂兄弟、祖先结点、子孙结点
4) 叶子(leaf)：终端结点，左右子树均为空的结点；反之，分支结点。
5) 结点的度(degree)：结点拥有的子树数。
6) 二叉树的度： 树中最大的结点度。
7) 结点层(level)：从根结点开始算起，根为第一层；根的孩子为第2层结点；……
8）二叉树的深度(depth)：二叉树中叶子结点的最大层次数。
※二叉树的基本性质
性质1：一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。
此树的深度k=4，共有24-1=15个结点
性质2：一棵深度为k的二叉树中，最多有2k-1个结点（k≥1)。
深度为k的二叉树取最多结点时，二叉树中的每层上均应取最多结点。根据性质1得到每层上的最大结点数为2i-1，则二叉树中的总结点数为：20 + 2 1+……+ 2 k-1 = 2k-1。
9
性质3：对于非空二叉树，如果叶子结点数为n0，度为2的结点数为n2，则有n0=n2+1。
证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：
N＝n0＋n1＋n2 (6-1)
再看二叉树中的分支数，除根结点外，其余结点都由一个分支与其双亲相连接，设B为二叉树中的分支总数，则有：
N＝B＋1 （6-2)
由于这些分支都是由度为1和2的结点射出的，所以有：
B＝n1+2*n2 （6-3)
即：N＝B＋1＝n1＋2×n2＋1
由式（6-1）得到：n0+n1+n2=n1+2*n2+1
即：n0＝n2＋1
n0=3
n2=2
A
B
C
D
E
F
G
k=4的满二叉树
※ 两种特殊的二叉树
(1) 满二叉树：如果深度为k的二叉树有2k-1个结点，则称为满二叉树。
特点：每一层上都含有最大结点数。