第九章树知识要点：•(根)树•二叉树•线索二叉树•二叉树的应用•树、森林与二叉树的相互转换•树和森林的遍历9.1概述1、树的定义树是由m(m≥0)个结点构成的有限集合。在任何一个非空树中：(1)有且仅有一个称为根的结点；(2)除根结点外，其余结点被分成n(n≥0)个互不相交的子集；(3)每个子集又是一棵树。(它们都是根的子树)A只有根结点的树ABCDEFGHIJKLM有子树的树根子树2、树的三种形态：（b）只有根的树（a）空树（c）具有根和子树的树Ø3、树型结构和线性结构的比较:线性结构线性结构树结构树结构第一个数据元素根结点（只有一个）无前驱无双亲最后一个数据元素叶子结点(可以有多个)无后继无孩子其它数据元素其它结点一个前驱,一个后继一个双亲,多个孩子一对一一对多一对一一对多4、基本术语结点：“数据元素”在树中的另一种称谓。分支是关系的表示，表示树中两个结点之间的关系。用直线或弧线表示。结点的度该结点的子树数目。树的度树中结点度数的最大值。根据结点度数的不同，结点可分为：叶子结点(终端结点)：度数为0的结点分支结点(非终端结点)：度数不为0的结点树中结点之间的关系①孩子与双亲的关系是指沿着同一个分支向上看，上面的结点是下面结点的双亲（parent）；沿着同一分支向下看，下面的结点是上面结点的孩子（children）。②兄弟与堂兄弟的关系同一双亲的结点间是兄弟（sibling）的关系；双亲互为兄弟的结点间是堂兄弟（Cousin）的关系。③祖先与子孙的关系一个结点的子孙（descendant）是其子树中的所有结点；一个结点的祖先（ancesor）是指结点沿着向上的分支到达根结点，沿路所经过的所有结点均是它的祖先。结点的层次规定：ⅰ根结点所在的层是第一层ⅱ根结点的孩子所在的层是第二层ⅲ第k层结点的孩子所在的层是第k+1层有序树和无序树如果将树中结点的各个子树看成从左至右是有次序的（即不能互换位置），则称该树为有序树，否则称为无序树。路径（path）即结点序列K1K2…Kn，其中Ki是Ki+1的双亲(1≤i≤n-1)。路径的长度路径所经过的分支数。树的路径长度从树根到树中每个结点的路径长度之和。森林m(m≥0)棵树的集合。结点v的高度是指从结点v到叶子中最长路径的长度加1。结点v的深度是指根结点到v的路径长度加1。树的高度（height）是指从根结点到叶子中最长路径的长度加1（即根结点的高度）。树的深度（depth）是指最深叶子结点的深度。根据树的高度和树的深度的定义可知，一棵树的高度在数值上等于该树的深度。【思考题9.1】（详见教材P102）（1）这棵树的根结点是？（2）这棵树的叶子结点有？（3）结点D的度？（4）这棵树的度？（5）结点D的孩子是？（6）结点D的双亲是？（7）结点G的有兄弟吗？（8）结点G有堂兄弟吗？（9）结点D的子孙是？（10）结点K的祖先是？（11）结点D的深度是多少？（12）结点D的高度是多少？（13）这棵树的高度是？BADCEFHGILKJ5、树的存储结构双亲数组表示法孩子链表表示法左孩子右兄弟表示法每个结点对应的存储映像：存储结点信息及双亲关系双亲数组表示法dataparent其中：data—存储结点的信息parent—存储结点的双亲信息一棵具有n个结点的树，对应n个上述的存储映像，如何来组织这些存储映像呢？我们用一组地址连续的存储单元(即一个一维数组)按照结点的编号依次存储这n个存储映像。此时每个存储映像中的parent数据项存放的就是该结点双亲在一维数组中的下标(也就是该结点双亲的编号)。双亲数组表示法类型定义#defineMAX100typedefstruct{DataTypedata;intparent;}PATreeNode;typedefstruct{PATreeNodenodes[MAX];intn;}PATree;双亲数组表示法树T的双亲数组表示法存储结构图T：BADCEFHGILKJ01234567891011【思考题9.2】根据上图所示的存储结构图，回答下述问题。（详见教材P113）1）请写出查找结点i（i为结点编号）的双亲结点的程序段；2）请写出查找结点H的双亲结点的程序段；3）请写出查找结点i（i为结点编号）的所有祖先的程序段；4）请写出查找结点H的所有祖先的程序段；5）请写出查找结点i（i为结点编号）的所有孩子结点的程序段；6）请写出查找结点B的所有孩子结点的程序...
