数据结构导论讲义-第四章　树和二叉树

VIP免费

2024-11-16 1 0 557KB 19 页 5.9玖币

侵权投诉

第四章　树和二叉树

　　—、学习目的与要求

　　树形结构用于表示具有分支和层次结构，有着广泛的应用背景。树和二叉树是重要的树形结构。

　　本章总的要求是：理解树形结构的基本概念和术语；深刻领会二叉树的定义及其存储结构，理解二

叉树的遍历的概念并掌握二叉树的遍历算法；掌握树和森林的定义、树的存储结构以及树、森林与二叉树

之间的相互转换方法；熟练掌握构造哈夫曼树和设计哈夫曼编码的方法。

　　二、课程内容

　　4.1 树的基本概念

　　4.1.1 树的概念

　　线性结构中的一个结点至多只有一个直接后继，而树形结构中一个结点可以有一个或多个直接后继。

例图 4－1 所示的树形结构老虎家族关系。

　　树（Tree）是一类重要的数据结构，其定义如下：

　　树是 n（n≥0）个结点的有限集合，一棵树满足以下两个条件：

　　（1）当 n=0 时，称为空树；

　　（2）当 n>0 时，有且仅有一个称为根的结点，除根结点外，其余结点分为 m（m≥0）个互不相交的

非空集合 T1，T2，…，Tm，这些集合中的每一个都是一棵树，称为根的子树。

　　如图 4－2 所示的几种结构都不是树。

　　4.1.2 树的相关术语

　　结点的度：树上任一结点所拥有的子树的数目称为该结点的度。

　　叶子：度为 0 的结点称为叶子或终端结点。

　　树的度：一棵树中所有结点的度的最大值称为该树的度。

　　一个结点的子树的根称为该结点的孩子（或称子结点）。相应地该结点称为孩子的双亲（也称父结

点）。

　　结点的层次：从根开始算起，根的层次为 1，其余结点的层次为其双亲的层次加 1。树的高度：一棵

树中所有结点层次数的最大值称为该树的高度或深度。

　　有序树：若树中各结点的子树从左到右是有次序的，不能互换，称为有序树。有序树中最左边子树的

根称为第 1 个孩子，左边第 i 个子树的根称为第 i 个孩子。

　　无序树：若树中各结点的子树是无次序的，可以互换，则称为无序树。

　　树的基本运算有：

　　（1）求根

　　（2）求双亲

　　（3）求孩子

　　（4）建树

　　（5）剪枝

　　（6）遍历

　　4.2 二叉树

　　4.2.1 二叉树的基本概念

　　二叉树（Binary Tree）是 n（n≥0）个元素的有限集合，该集合或者为空，或者由一个根及两棵互

不相交的左子树和右子树组成，其中左子树和右子树也均为二叉树。

　　二叉树的任一结点都有两棵子树（它们中的任何一个都可以是空子树），并且这两棵子树之间有次

序关系。如图 4－3a、b、c 分别是含两个结点 A、B 且以 A 为根的二叉树和树的示意图。

　　a）右子树为空的二叉树　b）左子树为空的二叉树　c）含一棵子树的树

　　二叉树有五种基本形态如图 4－4 所示其中方块表示子树

　　a）空二叉树　b）左右子树均为空的二叉树　c）右子树为空的二叉树　d）左子树为空的二叉树　

e）左、右子树都非空的二叉树

　　二叉树的基本运算：

　　（1）初始化

　　（2）求双亲

　　（3）求左孩子

　　（4）建立二叉树

　　（5）先序遍历

　　（6）中序遍历

　　（7）后序遍历

　　（8）层序遍历

　　4.2.2 二叉树的性质

　　性质 1：二叉树第 i（i≥1）层上至多有 2i-1 个结点。

　　性质 2：深度为 k（k≥1）的二叉树至多有 2k-1 个结点。

　　性质 3：对任何一棵二叉树，若度数为 0 的结点（叶结点）个数为 n0，度数为 2 的结点个数为 n2，则

n0=n2+1。

　　满二叉树：深度为 k（k≥1）且有 2k-1 个结点的二叉树称为满二叉树。

　　完全二叉树：如果对满二叉树按从上到下，从左到右的顺序编号，并在最下一层删去部分结点（删

后最后一层仍有结点），如果删除的这些结点的编号是连续的且删除的结点中含有最大编号的结点，那

么这棵二叉树就是完全二叉树。

　　图 4－5 满二叉树、完全二叉树和非完全二叉树

　　a）满二叉树　b）完全二叉树　c）非完全二叉树　d）非完全二叉树

　　对于完全二叉树，还有以下两个重要性质：

　　性质 4：含有 n 个结点的完全二叉树的深度为。

　　性质 5：如果将一棵有 n 个结点的完全二叉树按层编号，按层编号是指：将一棵二叉树中的所有 n 个

结点按从第一层到最大层，每层从左到右的顺序依次标记为 1，2，…，n。则对任一编号为 i（1≤i≤n）

的结点 A 有：

　　（1）若 i=1，则结点 A 是根；若 i>1，则 A 的双亲 Parent（A）的编号为；

　　（2）若 2*i>n，则结点 A 既无左孩子，也无右孩子；否则 A 的左孩子 Lchild（X）的编号为 2*i；

　　（3）若 2*i＋1>n，则结点 A 无右孩子；否则，A 的右孩子 Rchild（A）的编号为 2*i＋1。

　　图 4－6 完全二叉树上父、子结点编号之间的关系

　　a）i 为偶数 b）i 为奇数

　　4.3 二叉树的存储结构

　　二叉树通常有两类存储结构：顺序存储结构和链式存储结构。

　　4.3.1 二叉树的顺序存储结构

　　二叉树的顺序存储结构可以用一维数组来实现，二叉树上的结点按某种次序分别存入该数组的各个

单元中。图 4－7 为完全二叉树的顺序存储，图 4－8 为非完全二叉树的顺序实现。

　　图 4－7 完全二叉树的顺序存储示例

　　a）—棵完全二叉树 b）顺序存储示意

　　图 4－8 非完全二叉树的顺序实现

　　a）—棵非完全二叉树 BT　b）增设虚拟结点后的 BT

　　c）BT 的一种不恰当的顺序存储　d）BT 的顺序存储

　　4.3.2 二叉树的链式存储结构

　　二叉树有不同的链式存储结构，其中最常用的是二叉链表与三叉链表。二叉链表和三叉链表的结点形

式如图 4－9a、b 所示。

　　图 4－9 二叉链表和三叉链表结点结构

　　a）二叉链表的结点　b）三叉链表的结点

　　二叉链表的类型定义如下：

　　typedef struct btnode

　　{

　　DataType data;

　　//指向左右孩子的指针

　　struct btnode *lchild, *rchild;

　　}*BinTree;

　　三叉链表的类型定义如下：

　　typedef struct ttnode

　　{

　　datatype data;

　　struct ttnode * lchild, *parent, *rchild;

　　}*TBinTree;

　　TBinTree root;

　　二叉树的链式存储示意图如图 4－10 所示：

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

第四章　树和二叉树　　—、学习目的与要求　　树形结构用于表示具有分支和层次结构，有着广泛的应用背景。树和二叉树是重要的树形结构。　　本章总的要求是：理解树形结构的基本概念和术语；深刻领会二叉树的定义及...

展开>> 收起<<

数据结构导论讲义-第四章　树和二叉树.doc

共19页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

数据结构导论讲义-第四章　树和二叉树

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择:

数据结构导论讲义-第四章 树和二叉树

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择:

数据结构导论讲义-第四章　树和二叉树