数据结构及算法5.pptVIP

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