详解二叉树讲.pptx

第7章树和二叉树7.1树的概念7.2二叉树的概念7.3二叉树的存储结构7.4二叉树基本运算及其实现7.8哈夫曼树7.7线索二叉树7.6二叉树的构造7.5二叉树的遍历7.9并查集1/26

树：T={D，R}。D是包含n个结点的有限集合（n≥0）。当n=0时为空树，否则关系R满足以下条件:有且仅有一个结点d0∈D，它对于关系R来说没有前驱结点，结点d0称作树的根结点。除根结点外，每个结点有且仅有一个前驱结点。D中每个结点可以有零个或多个后继结点。7.1.1树的定义形式化定义7.1树的概念2/26

树是由n（n≥0）个结点组成的有限集合（记为T）。其中：如果n=0，它是一棵空树，这是树的特例；如果n0，这n个结点中存在一个唯一结点作为树的根结点（root），其余结点可分为m（m≥0）个互不相交的有限子集T1、T2、…、Tm，而每个子集本身又是一棵树，称为根结点root的子树。?树中所有结点构成一种层次关系！rootT1T2Tm…递归定义3/26

思考题请你列出几个现实生活中属于树形结构的数据。4/26

7.1.2树的（逻辑）表示（1）树形表示法。使用一棵倒置的树表示树结构，非常直观和形象。ABCDEFGJHIKLM逻辑结构表示15/26

（2）文氏图表示法。使用集合以及集合的包含关系描述树结构。逻辑结构表示2AEFBCGJHDKLMIABCDEFGJHIKLM6/26

（3）凹入表示法。使用线段的伸缩关系描述树结构。逻辑结构表示3ABCDEFGJHIKLM7/26

（4）括号表示法。用一个字符串表示树。基本形式:根(子树1，子树2，…，子树m)ABCDEFGJHIKLMA(B(E，F)，C(G(J))，D(H，I(K，L，M)))8/26

1、结点的度与树的度：树中一个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为树的度，通常将度为m的树称为m次树或者m叉树。7.1.3树的基本术语度为3度为23次树ABCDEFGJHIKLM9/26

2、分支结点与叶结点：度不为零的结点称为非终端结点，又叫分支结点。度为零的结点称为终端结点或叶结点（或叶子结点）。度为1的结点称为单分支结点；度为2的结点称为双分支结点，依此类推。叶结点双分支结点ABCDEFGJHIKLM10/26

3、路径与路径长度：两个结点di和dj的结点序列（di，di1，di2，…，dj）称为路径。其中dx，dy是分支。路径长度等于路径所通过的结点数目减1（即路径上分支数目）。ABCDEFGJHIKLMA到K的路径为A，D，I，K，其长度为311/26

4、孩子结点、双亲结点和兄弟结点：在一棵树中，每个结点的后继，被称作该结点的孩子结点（或子女结点）。相应地，该结点被称作孩子结点的双亲结点（或父母结点）。具有同一双亲的孩子结点互为兄弟结点。ABCDEFGJHIKLMA的孩子结点有B、C、DB、C、D的双亲结点为AB、C、D的互为兄弟结点12/26

5、子孙结点和祖先结点：在一棵树中，一个结点的所有子树中的结点称为该结点的子孙结点。从根结点到达一个结点的路径上经过的所有结点被称作该结点的祖先结点。ABCDEFGJHIKLM所有结点都是A的子孙结点L的祖先结点为A、D、I13/26

6、结点的层次和树的高度：树中的每个结点都处在一个层次上。结点的层次从树根开始定义，根结点为第1层，它的孩子结点为第2层，以此类推，一个结点所在的层次为其双亲结点所在的层次加1。树中结点的最大层次称为树的高度（或树的深度）。ABCDEFGJHIKLM1234树的高度为4结点的层次或深度14/26

7、有序树和无序树：若树中各结点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。15届1班2班3班有序树15届2班3班1班无序树15/26

8、森林：n（n＞0）个互不相交的树的集合称为森林。只要把树的根结点删去就成了森林。反之，只要给n棵独立的树加上一个结点，并把这n棵树作为该结点的子树，则森林就变成了一颗树。独木也成林！！！16/26

性质1树中的结点数等于所有结点的度数之和加1。7.1.4树的性质EABCDFGJHIKLM证明?树中每个分支计为一个结点的度ABCDEFGJHIKLM?所有结点的度之和＝分支数17/26

?根结点加上一个分支ABCDEFGJHIKLMn=度之和+1这