结点(Node) ●结点包括一个数据元素及若干个指向其它子 树的分支;例如,A,B,C,D等。 ●结点度结点拥有的子树数;例如,A的度为3 ●根结点无前趋结点为根;例如,A结点。 ●支结点度不为0的结点为支结点;如B,C,D 等 ●叶结点无后继结点为叶;如K,L,M。 树的度树中结点的最大度数;上述树的度为3 □上一页 「停止放映 第16页
下一页 上一页 停止放映 第 16 页 结点（Node） ⚫ 结点 包括一个数据元素及若干个指向其它子 树的分支；例如，A，B，C，D等。 ⚫ 结点度 结点拥有的子树数；例如，A的度为3。 ⚫ 根结点 无前趋结点为根；例如，A结点。 ⚫ 支结点 度不为0的结点为支结点；如B，C，D 等。 ⚫ 叶结点 无后继结点为叶；如K，L，M。 ⚫ 树的度 树中结点的最大度数；上述树的度为3
基本术语(二) ●子结点某结点子树的根为该结点的子结点; 例如,结点A的子结点为B,C,D。 父结点相对于某结点子树的根,称该结点为 子树根的父结点;例如子结点C,B,D的父结 点为A。 兄弟结点同一父亲的孩子之间互为兄弟结点 ( Sibling);H,I,J互为兄弟。 路径结点的序列n1,n2,,nk(K1)是一条 路径. □上一页 ●长度长度等于路径中结点数-1 「停止放映 第17页
下一页 上一页 停止放映 第 17 页 基本术语（二） ⚫ 子结点 某结点子树的根为该结点的子结点； 例如，结点A的子结点为B，C，D。 ⚫ 父结点 相对于某结点子树的根，称该结点为 子树根的父结点；例如子结点C，B，D的父结 点为A。 ⚫ 兄弟结点 同一父亲的孩子之间互为兄弟结点 （Sibling）；H，I，J互为兄弟。 ⚫ 路径 结点的序列n1，n2，…,nk(K1)是一条 路径. ⚫ 长度 长度等于路径中结点数-1
基本术语(三) ●高度从一结点到叶结点的最长路径为该结 点的高度;例如,结点A到M的高度为4。 ●探度从根结点到某结点的路径为该结点的 深度;M的深度为4。 森林0棵或多棵互不相交的树的集合。对 树中每个结点而言,其子树的集合即为森林 有序字如果将树中结点的各子树看成从左至 右是有顺序的(即不能互换),则称该树为 □上一页 有序树。否则,称为无序树。 「停止放映 第18页
下一页 上一页 停止放映 第 18 页 基本术语（三） ⚫ 高度 从一结点到叶结点的最长路径为该结 点的高度；例如，结点A到M的高度为4。 ⚫ 深度 从根结点到某结点的路径为该结点的 深度；M的深度为4。 ⚫ 森林 0棵或多棵互不相交的树的集合。对 树中每个结点而言，其子树的集合即为森林。 ⚫ 有序 如果将树中结点的各子树看成从左至 右是有顺序的（即不能互换），则称该树为 有序树。否则，称为无序树
树的操作 ● PARENT(n,T)得到树中n的父亲结点; ●RO0T(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。按次序依此访问树 □上一页 中各个结点,且使每个结点只能被访问一次。 「停止放映 第19页
下一页 上一页 停止放映 第 19 页 树的操作 ⚫ 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。按次序依此访问树 中各个结点，且使每个结点只能被访问一次
树的实现(存储结构) ●数组实现方法(双亲表示法) ●链表实现方式(孩子表示法) ●二叉链表实现方式(孩子兄弟表 示法) □上一页 「停止放映 第20页
下一页 上一页 停止放映 第 20 页 树的实现(存储结构) ⚫ 数组实现方法（双亲表示法） ⚫ 链表实现方式（孩子表示法） ⚫ 二叉链表实现方式（孩子兄弟表 示法）