资源描述：
《《数据结构与算法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构（数据结构及其算法）冯耀霖Chap5树树的基本概念二叉树二叉树遍历树的存储结构树结构是元素之间具有分层关系的结构，它类似于自然界中的树，是一种很重要的非线性数据结构。一方面，计算机应用中常出现嵌套的数据，树结构提供了对该类数据的自然表示；另一方面，利用树结构可以有效地解决一些算法问题。因此，树结构有着广泛的应用。树结构常采用递归方式定义，被称为递归数据结构，有关树的许多算法是递归的。§1树的基本概念▲树的定义▲基本术语▲树的基本操作1.1树的定义层次结构的数据在现实世界中大量存在。例如，一个国家包括若干省，一个省有若干市，每个市管辖若干个县、区。又
2、如，书的内容可以分成章节，章节编号也是有层次的。所有上级和下级、整体和部分、祖先和后裔的关系都是层次关系的例子。1.树（Tree）的一般定义树T=(D,R)，其中，D是包含n个结点的有限非空集合，R是D上的关系的集合，R满足以下特性：(1)有且仅有一个结点r∈D，不存在任何结点v∈D，v≠r，使得∈R，称r为树的根（root）；(2)除根之外的所有结点u∈D，都有且仅有一个结点v，v≠u，使得∈R。(3)树中任一结点x∈D，都可以有m（m≥0）个结点yi（i≥0），使得∈R。从上述定义可知，树不为空集合，树中至少有一个根结点，根结点
3、没有前驱，其余结点都有唯一的前驱结点，而每个结点又都可以有0或多个后继结点。因此，树形成了层次结构。2.树的递归定义树是包含n个结点的有限非空集合T，其中一个特定的结点r称为根，其余结点(T-{r})划分成m（m≥0）个互不相交的子集T1,T2,…Tm，其中每一个子集都是树，被称为根r的子树。图5.1树的示例AACBDGEFKLHIJM（a）（b）在图5.1中，（a）是只有一个根结点的树；(b)是有13个结点的树，其中A是根，其余结点分成3个互不相交的子集：T1={B,E,F,K,L}，T2={C,G}，T3={D,H,I,J,M}；T1,T2,T3都是根A的子树
4、，且本身也是一棵树。例如T1，其根为B，其余结点分成2个互不相交的子集：T11={E,K,L}，T12={F}。T11和T12都是B的子树。在T11中，E是根，{K}和{L}是E的两棵互不相交的子树，其本身又是只有一个根结点的树。可以看出，上述两种关于树的定义是完全一致的。1.2基本术语结点：树中的每个元素分别对应一个结点，结点包含数据元素值及其逻辑关系信息（后继／子树的指针）。结点的度：一结点拥有的子树数目。树的度：树中结点度的最大值。叶子结点：度为0的结点，简称叶子，又称终端结点。分支结点：度大于0的结点，又称非终端结点。子结点和父结点：如果一结点有子树，则子
5、树的根结点称为该结点的子结点，反之，该结点是子结点的父结点。结点的层次：树有明显的层次关系。根结点为第一层，根结点的子结点处于第二层，以此类推。树的深度：树中结点的最大层次，也称树的高度。兄弟结点：同一父结点的结点互为兄弟。堂兄弟结点：在同一层上但父结点不同的结点互为堂兄弟。祖先结点：从根结点到某个结点路径上的所有结点都是该结点的祖先结点。子孙／后裔结点：一个结点的所有子树上的任何结点都是该结点的后裔。路径：从某个结点到另一个结点的分支（边）构成这两个结点之间的路径。有序树：如果将树中根结点的各子树看成是从左到右有次序的，则称该树是有序树。从左到右，可分别称这些子
6、树为第一子树、第二子树等。无序树：如果根结点的各子树之间不存在确定的次序关系，可以交换位置，则称该树是无序树，也就是通常所说的树。森林：是树的集合。与现实世界的森林不同，在数据结构中，森林和树只有微小的差别，删去树根，树变成森林，对森林加上一个结点作为树根，森林即成为树。但是需要注意的是，森林可以是空森林，但树不能是空树。图5.2树和森林的例子FEBAGCDLMNJXYZUEFBADCGJLNMT1T2T3(a)树T1和T2组成的森林(b)树T3在图5.2(a)中，T1和T2是两棵树，组合在一起成为森林。如果树是无序的，则图5.2(a)中的树T1和图5.2(b)中
7、的树T3是相同的树，否则它们是不相同的树。在树T1中，结点A、F、和B是结点E的子结点，结点E是A、F、B的父结点，A、F和B互为兄弟。结点E、F、C和L都是结点N的祖先，F的后裔结点有C、L、M、N、D和J。结点E的度为3。根结点E的层次是1，F的层次是2，树T1的深度为5，T2的深度为3。在树T1中，G、M、N、J和B是叶子结点，其余结点是分支结点。就逻辑结构而言，任何一棵树是一个二元组Tree=(root,F)，其中，root是数据元素，称作树的根结点；F是m（m≥0）棵树的森林，F=(T1,T2,…,Tm)，其中Ti=(ri,Fi)称作根root的第i棵子
8、树；当m≠
