第七章树和二义树 数据结构 ●线性结构(线性表,栈,队列,串等) 非线性结构:至少存在一个数据元素有不 止一个直接前驱或后继(树,图等)
1 第七章 树和二叉树 数据结构 ⚫ 线性结构（线性表，栈，队列，串等） ⚫ 非线性结构：至少存在一个数据元素有不 止一个直接前驱或后继（树，图等）
7.1树的概念 711树的定义形式化定y) 树:T={KR}。K是包含n个结点的有穷集合 (m>0)关系R满足以下条件: (1)有且仅有一个结点k∈K,它对于关系R来说 没有前驱结点结点k称作树的。 (2)除结点k外K中的每个结点对于关系R来说 都有且仅有一个前驱结点。 (3)K中每个结点对于关系R来说可以有多个后 结点
2 7.1.1 树的定义(形式化定义)： 树：T＝{K,R}。K是包含n个结点的有穷集合 (n>0),关系R满足以下条件: (1)有且仅有一个结点k0∈K,它对于关系R来说 没有前驱结点,结点k0称作树的根。 (2)除结点k0外,K中的每个结点对于关系R来说 都有且仅有一个前驱结点。 (3)K中每个结点对于关系R来说可以有多个后 继结点。 7.1 树的概念
7.1树的概念 711树的定义递归定义) 树(Tree是由n(n>=0)个结点组成的有限集 (记为T),对任意一颗树T有 (1)存在唯一一个称为报(Root)的结点; (2)当n>1时,其余的结点可分为m(m>0)个 互不相交的子集T1T2T3Tm,其中每个子集 又是一棵树,并称其为根的子树 Subtree)。 3
3 7.1 树的概念 7.1.1 树的定义(递归定义） 树(Tree)是由n(n>=0)个结点组成的有限集 （记为T），对任意一颗树T有： （1）存在唯一一个称为根(Root)的结点； （2）当n>1时，其余的结点可分为m(m>0)个 互不相交的子集T1,T2,T3…Tm，其中每个子集 又是一棵树，并称其为根的子树(Subtree)
n=1只有根结点的树 N=0,空树 A n>1有子树的树 根 A B D E( FDIGH(I( K M 子树
4 A n=1,只有根结点的树 A B C D E F G H I J K L M n>1有子树的树 根 子树 N=0,空树
72树的逻辑表示方法 2 3 4 6 7 凹入表表示法 3 1(2(4,5(6,7)),3) 文氏图表示法 括号表示法
7.1.2 树的逻辑表示方法 1 2 3 4 5 6 7 1 2 4 5 6 7 3 凹入表表示法 1 2 4 5 3 6 7 文氏图表示法 1（2（4，5（6，7）），3） 括号表示法