2014/47 Ch.6树 数据结构 ■树形结构： ◆二叉树，树，森林等 Ch.6树 ◆结点间有分支，具有层次关系 ■特征： ·每个结点最多只有一个直接前驱，但可有多个直间后 计算机学院 继。 肖明军 。开始结点一根 ◆终端结点一叶 Email:xiaomj@ustc.edu.cn ◆其余结点一内部结点 http://staff.ustc.edu.cn/~xiaomj 应用：家谱、行政架构等，计算机系统中的文件 目录等 s6.1树的概念 S6.1树的概念 递归定义：刻画了树的固有特性：非空树由若干 ■Def:制是n(n>=O)个结点的有限集T,T为空时称为空树， 棵子树构成，子树由较小子树构成。 否测则它满足： 表示 ◆有且仅有一个特定的称为损的结点： 种解.TT 第一层 分支结点 8 子 (。树形表示法 ()数套集合表云选 (口入表表示法 (A(B(E.F(I.J)).C.D(G.HJ)) (D广义表表示法 86.1树的概念 S6.1树的概念 术语： ■术语： ①结点的度：结点拥有的子树数目（树的度） ⑧路径：道路（自上而下） ②叶子：终端结点，度为O的结点 若存在一结点序列k,k2,k,使得k是k的双亲 ③分支结点：非终端结点，度>O (1<=K=小1)，则称该序列是从k,到k的一条路径或 道路，路径长度为边数-1. ③内部结点：根之外的分支结点 ②粗先和子孙：若k到k有一路径，则k是k的粗先，k ⑤根：开始结点 是k的子孙， ⑥孩子、双亲：某结点的子树的根称为该 轴点A的祖先是从根到A的路径上所经过的所有结点 结点的孩子，该结点为孩子的双亲 结点A的于孙是以A为根的子树中的所有结点. 直接前驱（双亲）直接后继（孩子） 真祖先和真子孙不包含自身 ⑦兄弟：同一双亲的孩子互为兄弟 鲁层数从根起算（为1或0），其余结点的层数是其双 亲的层敷+12014/4/7 1 数据结构 Ch.6 树 1 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj Ch.6 树  树形结构：  二叉树，树，森林等  结点间有分支，具有层次关系  特征：  每个结点最多只有一个直接前驱，但可有多个直间后 2 继．  开始结点 —— 根  终端结点 —— 叶  其余结点 —— 内部结点  应用：家谱、行政架构等，计算机系统中的文件 目录等 §６.１树的概念  Def: 树是n (n>=0) 个结点的有限集Ｔ，Ｔ为空时称为空树， 否则它满足：  有且仅有一个特定的称为根的结点；  其余结点可分为m (m>=0) 个互不相交的子集Ｔ1 ，Ｔ2，…Ｔm， 其中每个子集本身又是一棵树，并称之为根的子树． 3 §６.１树的概念  递归定义：刻画了树的固有特性：非空树由若干 棵子树构成，子树由较小子树构成．  表示： 4 §６.１树的概念  术语： ① 结点的度：结点拥有的子树数目（树的度） ② 叶子：终端结点，度为０的结点 ③ 分支结点：非终端结点，度＞０ ④ 内部结点：根之外的分支结点 5 ⑤ 根：开始结点 ⑥ 孩子、双亲：某结点的子树的根称为该 结点的孩子，该结点为孩子的双亲 直接前驱（双亲） 直接后继（孩子） ⑦ 兄弟：同一双亲的孩子互为兄弟 §６.１树的概念  术语： ⑧ 路径：道路（自上而下） 若存在一结点序列k1,k2,…，kj ，使得ki 是ki+1的双亲 （１<=i<=j-1），则称该序列是从k1到kj 的一条路径或 道路，路径长度为边数j-1. 6 ⑨ 祖先和子孙：若k到ks有一路径，则k是ks的祖先，ks 是k的子孙．  结点Ａ的祖先是从根到Ａ的路径上所经过的所有结点．  结点Ａ的子孙是以Ａ为根的子树中的所有结点．  真祖先和真子孙不包含自身 ⑩ 层数从根起算（为１或０），其余结点的层数是其双 亲的层数＋１