第6章树和二叉树1
6.2二叉树6.3遍历二叉树6.4二叉树与树、森林之间的转换6.5哈夫曼树及其应用6.1树的基本概念2
树：是包含n个结点的有限集合（n≥0）。当n=0时为空树，n0时为非空树:有且仅有一个结点作为树的根结点；除根结点以外的其余结点可以分为m（m0）个互不相交的有限集T1，T2，…Tm，其中每个子集本身又是一颗树，称为根结点的子树(SubTree)。6.1.1树的定义ABCABCDEFGJHIKLM递归特性6.1树的基本概念3
中国河北省…石家庄市…山东省…济南市…几个现实生活中属于树形结构的数据。4
（a）文氏图表示法。使用集合以及集合的包含关系描述树结构。文氏图表示树的其他（逻辑）表示ABCDEFGJHIKLMAFBCJHDKLMIEG5
（b）凹入表示法。使用线段的伸缩关系描述树结构。凹入表示法ABEFCGJDHIKLMABCDEFGJHIKLM6
（c）括号表示法。用一个字符串表示树。基本形式：根(子树1，子树2，…，子树m)A(B(E(J)，F)，C(G)，D(H，I(K，L，M)))ABCDEFGJHIKLM括号表示法7
InitTree(T)：初始化一棵空树T；DestroyTree(T)：销毁树，释放树T占用的存储空间；TreeHeight(T)：求树T的高度；Partent(T,p)：求树T中结点p的双亲结点；Child(T,p,i)：求树T中结点p的第i个孩子结点；Brother(T,p)：求树T中结点p的所有兄弟结点；Traverse(T)：遍历树，按某种次序依次访问树T中所有结点，并且每个结点只被访问一次。树的基本运算8
1、结点的度与树的度：树中一个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为树的度，通常将度为m的树称为m次树或者m叉树。度为3度为23次树ABCDEFGJHIKLM6.1.2树的基本术语9
2、分支结点与叶结点：度为零的结点称为终端结点或叶结点（或叶子结点）。度不为零的结点称为非终端结点，又叫分支结点。度为1的结点称为单分支结点；度为2的结点称为双分支结点，依此类推。叶结点双分支结点ABCDEFGJHIKLM双分支结点：BD单分支结点：CE叶子结点：JFGHKLM10
3、路径与路径长度：两个结点di和dj的结点序列（di，di1，di2，…，dj）称为路径。其中dx，dy是分支。路径长度等于路径所通过的结点数目减1（即路径上分支数目或边的数目）。ABCDEFGJHIKLMA到K的路径为（A，D，I，K），其长度为311
4、孩子结点、双亲结点和兄弟结点：在一棵树中，每个结点的后继，被称作该结点的孩子结点（或子女结点）。相应地，该结点被称作孩子结点的双亲结点（或父母结点）。具有同一双亲的孩子结点互为兄弟结点。ABCDEFGJHIKLMA的孩子结点有B、C、DB、C、D的双亲结点为AB、C、D的互为兄弟结点12
5、子孙结点和祖先结点：在一棵树中，一个结点的所有子树中的结点称为该结点的子孙结点。从根结点到达一个结点的路径上经过的所有结点被称作该结点的祖先结点。所有结点都是A的子孙结点L的祖先结点为A、D、IABCDEFGJHIKLM13
6、结点的层次和树的高度：树中的每个结点都处在一个层次上。结点的层次从树根开始定义，根结点为第1层，它的孩子结点为第2层，以此类推，一个结点所在的层次为其双亲结点所在的层次加1。树中结点的最大层次称为树的高度（或树的深度）。ABCDEFGJHIKLM1234树的高度为4结点的层次14
7、有序树和无序树：若树中各结点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。24级1班2班3班有序树23级2班3班1班无序树默认为有序树15
8、森林：n（n0）个互不相交的树的集合称为森林。把含有多棵子树的树的根结点删去就成了森林。ABCDEFGJHIKLMBCDEFGJHIKLM删去根结点A16
给m（m1）棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了一棵树。ABCDEFGJHIKLMABCDEFGJHIKLM17
证明?树中每个分支计为一个结点的度（每条分支线从一个结点引出来的）?所有结点的度之和＝分支数分支数=12结点的度之和=12EABCDFGJHIKLM树的性质1树中的结点数等于所有结点的度数之和加1。18
?除了根结点，每条分支线都指向一个结点。给根结点加上一个分支：n=度之和+1这样分支数与结点数相同?实际分支数=