72n1树的定义 树tree的递归定义: 口树(tree是n个数据元素的有限集(记为T),对任意 棵树T有: 1.存在唯一一个称为根(root)的数据元素; 2.当n>1时,其它数据元素可分为m(血m>0)个互不相交的有 限集T1,T2,∴,Tm,其中每个集合T(i=1,2,…,m)本身又 是一棵树,并称树T;是根的子树( subtree A (空树) A B C D E G (a) (b) Data structure Lri
Data Structure LXJ 7.2.1 树的定义 树tree的递归定义： ❑ 树(tree)是n个数据元素的有限集(记为T)，对任意 一棵树T有： 1. 存在唯一一个称为根(root) 的数据元素； 2. 当n＞1时，其它数据元素可分为m(m＞0) 个互不相交的有 限集T1,T2,•…,Tm，其中每个集合Ti(i=1,2,…,m)本身又 是一棵树，并称树 Ti是根的子树(subtree). A B C D E F G (空树) A （a） （b） （c）
树的结点(Node) 层次0 根结点 父结点 层次1……(B… 子结点 层次2 (E.G.H 层次3… 叶结点 根结点、叶结点、分支结点、孩子结点、双亲结点、兄弟结点、 祖先结点、子孙结点 Data structure Lrg
Data Structure LXJ 树的结点（Node） 根结点、叶结点、分支结点、孩子结点、双亲结点、兄弟结点、 祖先结点、子孙结点
结点的度、树的度 A 3度 根 B F)G H 0度 叶 K 2个3度点A,D 树的度:树中所有结点 的度的最大值。 2个2度点BE 上图:树的度为3 2个1度点CH 7个叶FG,K,L,M Data structure Lri
Data Structure LXJ 结点的度、树的度 A B C D E F G H I J K L M ································· ·······根 3度 ············· 叶 0度 2个3度点 A,D 2个2度点 B,E 2个1度点 C,H 7个叶 F,G,I,J,K,L,M 树的度：树中所有结点 的度的最大值。 上图：树的度为3
结点的层次、树的深度 A 第一层 B C 第二层 )GH ①① 第三 层 K 第四层 树的深度为4 Data structure Lri
Data Structure LXJ 结点的层次、树的深度 树的深度为4 A B C D E F G H I J K L M ··········································· ··第一层 ······························ 第二层 ···············第三 层 ···································· 第四层
序树、森林 口无序树:树中任意一个结点的各个子树之间的次序 构成无关紧要,交换树中任意一个结点的各个子树 的次序均和原树相同的树构成无序树 有序树:树中任意一个结点的任意子树都是有次序 的树。 口森林:m颗树的集合称为森林。 A A A B B C E F G 森林 Data structure Lri
Data Structure LXJ 序树、森林 ❑ 无序树：树中任意一个结点的各个子树之间的次序 构成无关紧要，交换树中任意一个结点的各个子树 的次序均和原树相同的树构成无序树。 ❑ 有序树：树中任意一个结点的任意子树都是有次序 的树。 ❑ 森林：m颗树的集合称为森林。 A B C D E F G A 森林 A B C