第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
凹入表示法：