计算机考研 数据结构-树--总结者：刘尧涛
需积分: 0 71 浏览量
2009-06-02
16:33:07
上传
评论
收藏 43KB DOC 举报
树及二叉树
树型结构是一类重要的非线性结构。树是 n(n>=0)个结点的有限集 T
结点 数据元素的内容及其指向其子树根的分支统称为结点。
结点的度 结点的分支数。
终端结点（叶子） 度为 0 的结点。
非终端结点 度不为 0 的结点。
结点的层次 树中根结点的层次为 1，根结点子树的根为第 2 层，以此类推。
树的度 树中所有结点度的最大值。
树的深度 树中所有结点层次的最大值。 有序树、无序树 如果树中每棵子树从左向右的
排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。
叶子(leaf)——度为 0 的结点
孩子(child)——结点子树的根称为该结点的孩子
深度(depth)——树中结点的最大层次数
森林(forest)——m(m³0)棵互不相交的树的集合
定义：二叉树是由 n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点
及两棵互不相交的左右子树组成，并且左右子树都是二叉树即使只有一棵子树也要进行区分区
别
二叉树具有下列重要性质：
性质 1: 在二叉树的第 i 层上至多有 2i-1 个结点(i≥1)。
性质 2：深度为 k 的二叉树至多有 2k-1 个结点（k≥1)。
性质 3： 对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0＝n2＋1。
下面介绍两种特殊形态的二叉树： 满二叉树和完全二叉树
满二叉树：一棵深度为 k 且有 2k-1 个结点的二叉树称为满二叉树
完全二叉树：如果深度为 k、由 n 个结点的二叉树中每个结点能够与深度为 k 的顺序编号的
满二叉树从 1 到 n 标号的结点相对应
完全特点：所有的叶结点都出现在第 k 层或 k－1 层。
性质 4：具有 n 个结点的完全二叉树的深度为 ëlog2nû＋1
二叉树的存储结构：
1、顺序存储结构：在此约定，用一组地址连续的存储单元依次自上而下，自左至右存储完
全二叉树上的结点元素，
2、 二叉链表：二叉树的每一个结点最多有左、右两棵子树，故链表的结点结构除数据域
外可设两个链域：左孩子（lchild）、右孩子（ rchild）分别指向左、右孩子。
3、 三叉链表：有时为了便于找到双亲结点，另设一个指向双亲的链域，结点由三个链域
组成的链表称为三叉链表。
4、线索链表：用链表表示的二叉树中也会存在许多空链域。
遍历二叉树：是指按一定的次序系统地访问二叉树中所有结点，而且仅被访问一次
二叉树遍历：前序遍历，中序遍历，后续遍历（根的位置）
3）求二叉树的深度：算法基本思想：分析二叉树的深度和它的左、右子树深度之间的关系
最重要：给你一个先序、中序、后序的能唯一确定一棵树
以这种结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱与后继
的指针叫做线索，加上线索的二叉树称之为线索二叉树：线索二叉树基本实现
线索化的过程即为在遍历过程中修改空指针的过程。
树的存储结构：
1
评论0