第7章树 树的定义及基本操作 ⊙二叉树 线索二叉树 树、森林和二叉树 哈夫曼树及其应用
第7章 树 树的定义及基本操作 二叉树 线索二叉树 树、森林和二叉树 哈夫曼树及其应用
树的定义 ◆树:包含n(n>0)个节点的有穷集合K,且在K中定义了 个关系N,N满足以下条件: 0有且仅有一个结点K0,它对于关系N来说没有前驱, 称K0为树的根结点。 除K0外,K中的每个结点对于关系N来说有且仅有 个前驱。 0K中各结点对关系N来说可以有m个后继m≥0)。 ◆子树:若n>1,除根结点之外的其余数据元素被分为m (m>0)个互不相交的集合T1,T2,…Tm,其中每一个 集合(1≤i≤m本身又是一棵树;树T1,T2,……,Tm称 作根结点的子树
树的定义 树：包含n（n>0）个节点的有穷集合K，且在K中定义了 一个关系N，N满足以下条件： 有且仅有一个结点K0，它对于关系N来说没有前驱， 称K0为树的根结点。 除K0外，K中的每个结点对于关系N来说有且仅有 一个前驱。 K中各结点对关系N来说可以有m个后继(m≥0)。 子树：若n>1，除根结点之外的其余数据元素被分为m （m>0）个互不相交的集合T1, T2,….. Tm，其中每一个 集合Ti (1≤i≤m)本身又是一棵树；树T1, T2,…..,Tm称 作根结点的子树
◆实例: (a)只有根结点的树 (b)一般的树 图7-1树的示例 ◆树的特点: 树的根结点没有前驱结点,且除了根结点之外 的所有结点有且只有一个前驱结点。 树结点可以有零个或多个后继结点
实例： 树的特点： 树的根结点没有前驱结点，且除了根结点之外 的所有结点有且只有一个前驱结点。 树结点可以有零个或多个后继结点
树的表示形式 ◆树的表示方法: 直观表示法: (b)一般的树 形式化表示法: (A(BE(K, L,FLDCIG,D(HIMNDD)
树的表示形式 树的表示方法： 直观表示法： 形式化表示法： （A(B(E(K,L),F(L)),C(G),D(H,I(M(N))))）
◆凹入表示法: ABEJKFLcGDHIM
凹入表示法：
树的常用术语 ◆树的结点:包含一个数据元素及若千指向其子树的分支。 ◆结点的度:结点所拥有的子树的个数称为该结点的度。 ◆叶子:度为0的结点。 ◆非终端结点:度不为0的结点。 ◆孩子:结点的子树的根称为该结点的孩子。 ◆兄弟:同一个双亲的孩子之间互称兄弟。 ◆结点的祖先:是从根到该结点所经分支上的所有结点。 ◆子孙:以某结点为根的子树中的任意结点都称为该结点 的子孙
树的常用术语 树的结点：包含一个数据元素及若干指向其子树的分支。 结点的度：结点所拥有的子树的个数称为该结点的度。 叶子：度为0的结点。 非终端结点：度不为0的结点。 孩子：结点的子树的根称为该结点的孩子。 兄弟：同一个双亲的孩子之间互称兄弟。 结点的祖先：是从根到该结点所经分支上的所有结点。 子孙：以某结点为根的子树中的任意结点都称为该结点 的子孙
◆层次性:从根开始定义起,根为第一层,根的孩子为第 二层;某结点在第工层,则其子树的根就在第L+1层。 ◆树的深度:树中各结点层次的最大值称作该树的深度。 有序树:将树中结点的各子树看成从左向右是有次序的 则称该树为有序树 ◆森林:是m(m≥0)棵互不相交的树构成的有限集合 即F=1,T2,…Tm},其中,Ti(i=1,2,…m)是树 当m=0时,F是空森林。对树中每个结点而言,其子树 的集合即为森林。反之,若给森林F={T1,T2,…Tm} 中的每棵树的根结点都赋予同一个双亲结点,则就构成 棵树
层次性：从根开始定义起，根为第一层，根的孩子为第 二层；某结点在第L层，则其子树的根就在第L+1层。 树的深度：树中各结点层次的最大值称作该树的深度。 有序树：将树中结点的各子树看成从左向右是有次序的 则称该树为有序树。 森林：是m（m≥0）棵互不相交的树构成的有限集合； 即F={T1，T2，Tm}，其中，Ti（i=1,2, m）是树， 当m=0时，F是空森林。对树中每个结点而言，其子树 的集合即为森林。反之，若给森林F={T1，T2，Tm} 中的每棵树的根结点都赋予同一个双亲结点，则就构成 一棵树
树的基本操作 ◆树的基本操作: o Initiate(t):初始化一棵树t Root(x):求结点x所在树的根结点。 Parent(t,x):求树t中结点x的双亲结点。 Child(t,x,j):求树t中结点x的第i个孩子 结点。 Insert(t1x,i,s):把以s为结点的树插入 到树t中作为结点x的第棵子树。 Delete(t,x,i:在树t中删除结点x的第课 子树。 Tranverse(t):按某种方式访问树t中的每个 结点,且使每个结点只被访问一次
树的基本操作 树的基本操作： Initiate(t)：初始化一棵树t。 Root(x)：求结点x所在树的根结点。 Parent(t，x)：求树t中结点x的双亲结点。 Child(t，x，i)：求树t中结点x的第i个孩子 结点。 Insert(t，x，i，s)：把以s为结点的树插入 到树t中作为结点x的第i棵子树。 Delete(t，x，i)：在树t中删除结点x的第i棵 子树。 Tranverse(t)：按某种方式访问树t中的每个 结点，且使每个结点只被访问一次
二叉树 ◆二叉树:T是n(n≥0)个有限元素的集合,这个集 合或者是空集,或者是由一个根结点和两棵分别称为 左子树和右子树的互不相交的二叉树组成。即当T地 时,T满足以下条件: 存在唯一的数据元素r∈T,且在T中没有直接 前驱,称为根结点。 0若T-{地①,则个-{r存在划分T1,T2: T12=T-t},T1T2=①,且T1,T2均为二 叉树,并命名T1是T的左子树,T2是T的右子 树
二叉树 二叉树：T是n（n≥0） 个有限元素的集合，这个集 合或者是空集，或者是由一个根结点和两棵分别称为 左子树和右子树的互不相交的二叉树组成。即当T 时，T满足以下条件： 存在唯一的数据元素rT，且r在T中没有直接 前驱，称为根结点。 若T-{r}，则T-{r}存在划分T1，T2： T1T2=T-{r}，T1T2=，且T1，T2均为二 叉树，并命名T1是T的左子树，T2是T的右子 树
◆实例: E ◆二叉树的基本形态: (a)空二叉树 b)只有一个根结点 左子树 (c)有根结点和左子树 右子树 左子树(有子树 (d)有根结点和右子树 (e)有根结点和左、有子树
实例： 二叉树的基本形态：