树与二叉树(一).ppt

树与二叉树 内 容 树、树林和二叉树的基本概念； 树、树林和二叉树的存储结构 树和二叉树常见的运算； 二叉树的周游算法； 树的应用 哈夫曼树 树的定义 “树”是包括ｎ（ｎ≥０）个结点的有穷集合Ｔ，当Ｔ非 空时满足：　 （ａ）有且仅有一个特别标出的称作根的结点；　 （ｂ）除根结点之外，其余结点分为ｍ≥０个不相交的 非空集合T1, T2,…，Tm，而这些集合中的每一个又都是 树。树T1, T2,…，Tm，都称作这个根的子树。　 说明： 只包括一个结点的树必然仅由根结点构成 当n＞1时，n个结点的树借助于少于ｎ个结点的树来定义 空树：不包括任何结点的树，把它称作“空树” （引入空树的概念将为后边的一些运算和叙述带来方便） 树的示意图 树的特点 树描述的是层次结点，数据元素之间存 在一对多或多对一的关系 树的根结点没有前趋结点，除了根接点之 外的所有结点都有且只有一个前驱结点 树中所有结点可以有零个或多个后继结点 基本术语 父结点、子结点、边 若结点y是结点x的一棵子树的根，则x称作y的“父结点” （或父母）；y称作x的“子结点”（或子女）；有序对x， y称作从x到y的“边” 例如树t中，C是E的父结点，E是C的子结点，C，E是从C 到E的边（它对应着图中的有向线段CE 兄弟　 具有同一父母的结点彼此称作“兄弟” 树t中B，C，D互为兄弟，F，G互为兄弟 注意，E和F并不是兄弟 基本术语(续) 祖先 、子孙 若结点y在以结点x为根的一个子树（或树）中，且y≠x，则称x是y的“祖先”，y是x的“子孙” 例如树t中，A是其它各结点的祖先；C是E，H，I，J的 祖先 路径、路径长度　 如果x是y的一个祖先，又有x＝x0，x1，…，xn＝y，满足 xi（i＝0，1，…，n-1）为xi+1的父结点，则称x0，x1，…，xn为从x 到y的一条路径。n称为这条路径的长度。路径中相邻的两个 结点可以表示成一条边。 例如树t中A，C，E，I，J是从A到J的一条路径，其长度为4 基本术语（续） 结点的层数、树的层数 规定根的层数为0，其余“结点的层数”等于其父母结点的层数 加1。树中层数最大的结点的层数称作“树的层数” 例如t中，0层的结点是A，1层的结点有B，C，D，4层的结点是 J，树的层数是4　 树的深度或高度 树中结点的最大层数称为“树的深度”或“树的高度” 例如树t中，树的深度为4 基本术语（续） 结点的度数、树的度数　 结点的子女个数叫作结点的“度数”。树中度数最大的结点的 度数叫作“树的度数” 例如t中A，C，E，J的度数分别为3，1，2，0； t的度数为3　 树叶、分支结点　 度数为0的结点称作“树叶”（又叫终端结点） 度数大于0的结点称作“分支结点” 例如树t中B，F，G，H，J都是树叶，其余结点都是分支结点 注意，结点的度数为1时，虽然只有一个子女，也叫分支结点。 这两个术语对于根结点也不例外 基本术语（续） 无序树、有序树　 对子树的次序不加区别的树叫作“无序树”。对子树之间的次序加 以区别的树叫作“有序树” 例如在下图中，按无序树的概念t和t’是同一棵树，按有序树的 概念则是不同的树，本章讨论的树一般是有序树 基本术语（续） 结点的次序　 在有序树中可以从左到右地规定结点的次序 例如图5-3中，结点2，3，4是从左到右排序的；可以说结 点3是结点2右边的结点，是结点4左边的结点 把这种说法进一步推广，我们还可以说结点3的所有子女都 在结点2及其子女的右边，而在结点4及其子女的左边 注意：祖先与子孙之间不存在左右的概念。因此我们不能 说结点3在结点5的右边或结点3在结点6的左边等等 树林概念 “树林”是由0个到多个不相交的树所组成的集合 树林中每棵树的根彼此称为“兄弟”，与自然界的 树林有所不同，这里的树林可以是一个空集。如 果从一棵树中将根结点（连同根结点到各子结点 的边）删除，便得到一个树林 树的基本运算 1.创建一棵空树； 2.判断某棵树是否为空； 3.求树中的根结点，若为空树，则返回一特殊值； 4.求树中某个指定结点的父结点，当指定结点为根 时，返回一特殊值； 5.求树中某个指定结点的最左子结点，当指定结点 为树叶时，它没有子女，则返回一特殊值； 6.求树中某个指定结点的右兄弟结点，当指定结点 没有右兄弟时，返回一特殊值； 7.树的周游，即按某种方式访问树中的所有结点， 并使每个结点恰好被访问一次 树的存储表示 树的父指针表示法　 方法：用一个数组顺序地存放树的各个结点，结点存放 的次序是任意的 结点类型定义为： struct ParTreeNode /* 树中结点结构 */