数据结构(C语言版) 第6章 树[精品].doc

第6章 树 1树的逻辑结构 核心关系：层次关系。 1.1 通俗定义 树形表示法 广义表表示法 A(B(E,F,G),C(H),D(I,J)) 树是n(n0)个结点的有限集，在任意一棵树中： 1 有且只有一个特定的根(root)结点； 2 当n1时，其余结点可分为m(m0)个互不相交的有限子集T1,T2...Tm，每个子集是一棵树，称为子树。 1.2 形式定义 D={ai | ai∈ElemSet，i=1,…,n} 二元关系S的定义： 当n=1时，S=φ； 当n1时： 1 根的特殊地位 唯一无前驱的元素：根结点(root)； 2 结点的划分 可将D-{root}划分成m(m0)个互不相交的子集D1,D2,…Dm，对任意子集Di，唯一存在xi∈Di，有root,xi∈S； 3 关系的划分 对应D-{root}的划分,可将 S-{root,x1,…,root,xm}唯一划分成互不相交的子集S1,S2,...,Sm，对于任意i, Si是Di上的二元关系。(Di,Si)是一棵树，称为根root的子树。 示例： D={A,B,C,D,E,F,G,H,I,J,K} S={A,B,A,C,A,D, B,E,B,F,B,G, C,H, D,I,D,J } root: A D-{A}可分为： D1={B,E,F,G} D2={C,H} D3={D,I,J} S-{A,B,A,C,A,D}可分为： S1: {B,E,B,F,B,G} S2: {C,H} S3: {D,I,D,J} 1.3 概念 1.3.1 若干角色 双亲、孩子 一个序偶中的直接前驱、直接后继。 祖先、子孙 一个序偶集合中的前驱、后继。 兄弟 具有相同直接前驱的数据元素。 堂兄弟 1.3.2 与“度”相关的概念 结点的度 结点拥有的子树数。 叶子结点 度为0的结点。 分支结点 度不为0的结点。 树的度 树内所有结点的度的最大值。 1.3.3 与“深度”相关的概念 结点深度 根结点的深度为1 若结点深度为i, 则子结点深度为i 森林 m棵互不相交的树的集合。 m=0：空集； m=1：树 1.4 基本操作 构造、析构、遍历、查找、插入、删除、 2 二叉树的逻辑结构 2.1 定义 结构简化、概念强化：左子树、右子树。 树形表示法 广义表表示法 A(B(D),C(F(,E),G)) 2.2 二叉树的形态 具有n个结点的不同形态的二叉树有多少颗？ 二叉树相似：二者都为空；或它们的左右子树相似。 例：n个结点的相似树的个数 template class T int BinTreeT::GetTreeCount(int n) { int left,count=0; if(n==0 || n==1) return(1); for(left=n-1; left=0; left--) count += GetTreeCount(left) * GetTreeCount(n-1-left); return(count); } 2.3 性质 2.3.1 性质1 若某二叉树的叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。 试题例：若一棵m叉树中度为i的结点有Ni个，则该树的叶结点有 (N1+2N2+…+mNm+1)-(N1+N2+…+Nm) 个。 2.3.2 性质2 二叉树的第i层上的结点数最多为2i-1。 2.3.3 性质3 深度为k的二叉树中结点总数最多为2k-1。 满二叉树 完全二叉树 深度为k，共有2k-1个结点。 深度为k，前k-1层是满二叉树，第k层的结点从左至右依次排列。 2.3.4 性质4 具有n个结点的完全二叉树的深度为int(log2n)+1。 2.3.5 性质5 有n个结点的完全二叉树，结点从0顺序标号，则： 1、若i0，i的双亲结点是(i-1)/2。 2、若2i+1n，i的左孩子是2i+1；否则，i无左孩子。 3、若2i+2n，i的右孩子是2i+2；否则，i无右孩子。 3 二叉树的存储结构 3.1 顺序结构 3.1.1 存储规则 依照满二叉树的结点顺序，存放各个结点。 存储位置暗藏树的关系。 试题例：将68个结点的完全二叉树，按顺序存储结构存于数组A[0…100]中，叶子结点的最小编号是 。 A、32 B、33 C、34 D、35 试题例：具有101个结点的完全二叉树，度为1的结点有 个。 3.1.2 性能分析 满/完全二叉树：存储效率最高，插入、删除方便。 非完全二叉树的处理方法： 非完全二叉树 修补结构 不存在的结点，用特殊符号标识。 退化的二叉树及其存储效果：