3.基本术语(一) 结点包括一个数据元素及若干个指向其它 子树的分支;例如,A,B,C,D等。 ●叶结点无后继结点为叶;如K,L,M。 ●支结点度不为0的结点为支结点;如B,C, D等。 ●根结点无前趋的结点为根;例如,A结点。 结点度结点拥有的子树数数目;例如,A 的度为3。 ●树的度树中结点的最大度数;上述树的度 为3。 停止放映 第11页
下一页 上一页 停止放映 第 11 页 3.基本术语（一） ⚫ 结点 包括一个数据元素及若干个指向其它 子树的分支；例如，A，B，C，D等。 ⚫ 叶结点 无后继结点为叶；如K，L，M。 ⚫ 支结点 度不为0的结点为支结点；如B，C， D等。 ⚫ 根结点 无前趋的结点为根；例如，A结点。 ⚫ 结点度 结点拥有的子树数数目；例如，A 的度为3。 ⚫ 树的度 树中结点的最大度数；上述树的度 为3
基本术语(二) 子结点某结点子树的根为该结点的子结点; 例如,结点A的子结点为B,C,D。 父结点相对于某结点子树的根,称该结点为 子树根的父结点;例如子结点C,B,D的父结 点为A ●兄弟结点同一父亲的孩子之间互为兄弟结点 ( Sibling);H,I,J互为兄弟。 ●路径结点的序列n1,n2,…,nk(K1)是一条 路径. 停止放映 ●长度长度等于路径中结点数-1 第12页
下一页 上一页 停止放映 第 12 页 基本术语（二） ⚫ 子结点 某结点子树的根为该结点的子结点； 例如，结点A的子结点为B，C，D。 ⚫ 父结点 相对于某结点子树的根，称该结点为 子树根的父结点；例如子结点C，B，D的父结 点为A。 ⚫ 兄弟结点 同一父亲的孩子之间互为兄弟结点 （Sibling）；H，I，J互为兄弟。 ⚫ 路径 结点的序列n1，n2，…,nk(K1)是一条 路径. ⚫ 长度 长度等于路径中结点数-1
基本术语(三) ●阶层(层次)结点的特性值,根结点的阶 层为1,子结点为2,依次类推。如阶层1有 结点A,阶层2有结点B,C,D。 高度(探度)一棵树的最大阶层值为树的高 度或深度。例如,结点A到M的高度为4。 森林0棵或多棵互不相交的树的集合。对 树中每个结点而言,其子树的集合即为森林。 ●有序字如果将树中结点的各子树看成从左至 右是有顺序的(即不能互换),则称该树为 有序树。否则,称为无序树。 停止放映 第13页
下一页 上一页 停止放映 第 13 页 基本术语（三） ⚫ 阶层（层次） 结点的特性值，根结点的阶 层为1，子结点为2，依次类推。如阶层1有 结点A，阶层2有结点B，C，D。 ⚫ 高度（深度）一棵树的最大阶层值为树的高 度或深度。例如，结点A到M的高度为4。 ⚫ 森林 0棵或多棵互不相交的树的集合。对 树中每个结点而言，其子树的集合即为森林。 ⚫ 有序 如果将树中结点的各子树看成从左至 右是有顺序的（即不能互换），则称该树为 有序树。否则，称为无序树
4.树的操作 ● PARENT(n,T)得到树中n的父亲结点; ●ROOT(T) 求树的根,返回树根的位置。 ● CHILD(T,x,i)求树T中结点x的第i个孩子 结点。 ● CREATE(x,T1,T2,…,Tk)生成一个结点x, 下带子树T1,T2,,Tk。 DELETE(x,i)删除结点x的第i个子树。 ● TRAVERSE(T)遍历树T。按次序依此访问树 中各个结点,且使每个结点只能被访问一次。 停止放映 第14页
下一页 上一页 停止放映 第 14 页 4.树的操作 ⚫ PARENT（n，T） 得到树中n的父亲结点； ⚫ ROOT（ T） 求树的根，返回树根的位置。 ⚫ CHILD（T，x，i）求树T中结点x的第i个孩子 结点。 ⚫ CREATE（x，T1，T2，…,Tk) 生成一个结点x, 下带子树T1,T2,…,Tk。 ⚫ DELETE(x,i) 删除结点x的第i个子树。 ⚫ TRAVERSE（T） 遍历树T。按次序依此访问树 中各个结点，且使每个结点只能被访问一次
5树的实现(存储结构) ●数组实现方法(双亲表示法) ●链表实现方式(孩子表示法) ●二叉链表实现方式(孩子兄弟表 示法) 停止放映 第15页
下一页 上一页 停止放映 第 15 页 5.树的实现(存储结构) ⚫ 数组实现方法（双亲表示法） ⚫ 链表实现方式（孩子表示法） ⚫ 二叉链表实现方式（孩子兄弟表 示法）