第6章__树与二叉树.ppt

第6章 树与二叉树 本章要点 树和二叉树的逻辑结构和基本概念 二叉树的性质和二叉树的存储形式 二叉树的遍历与线索操作 树的存储形式及树与二叉树的转换 哈夫曼树与哈夫曼编码 第6章 树与二叉树 线性结构特点是结点间具有唯一前驱和唯一后继；而非线性结构的特征是：表示结点间关系的前驱、后继不具有唯一性。 树是非线性结构，结构中结点间关系是前驱唯一而后继不唯一，结点之间的数据关系是一对多的关系。 直观地看，树结构是指具有分支关系的结构。树形结构特别是二叉树应用非常广泛，在文件系统、编译系统、目录组织等方面更加突出。在计算机科学和软件工程中研究它的有着现实意义。 第6章 树与二叉树 6.1 树的逻辑结构和基本操作现实生活中树的例子很多，如家庭成员关系、单位人员组织机构等都是树结构。 例如：某家庭成员关系如下：李奶奶(为描述方便用A表示)有三个儿子分别用B、C、D表示；大儿子B有两个孩子，分别用E、F表示；二儿子C有一个孩子用G表示；三儿子D有三个孩子，分别用H、I、J表示；李奶奶的孙子E有两个孩子，分别用K、L表示；另一个孙子H也有一个孩子M。李奶奶的家庭关系就是树结构，如图6.1所示描述这棵树结构。 第6章 树与二叉树 李奶奶A有三个儿子分别用B、C、D表示；大儿子B有两个孩子，分别用E、F表示；二儿子C有一个孩子用G表示；三儿子D有三个孩子，分别用H、I、J表示；李奶奶的孙子E有两个孩子，分别用K、L表示；另一个孙子H也有一个孩子M。李奶奶的家庭关系就是树结构，如图6.1所示描述这棵树结构。 第6章 树与二叉树 树(tree)T是n(n≥0)个结点的有限集合。如果n=0是空树；否则满足如下两个条件： 第一有且只有一个称为根(root)的结点，根结点无前驱； 第二除根之外其余n-1个结点可以划分成m(m＞0)个互不相交的有限集T1，T2，T3，…，Tm ，其中Ti（i=1‥m）又是一棵树，称为根的子树。 显然，这是递归定义。 第6章 树与二叉树 描述图6.1所示的家庭关系树的数据结构：Tree=(D,R)，其中： 数据元素D={Va Vb Vc Vd Ve Vf Vg Vh Vi Vj Vk Vl Vm } 数据关系R={Va Vb, Va Vc , Va Vd , Vb Ve , Vb Vf ,Vc Vg ,Vd Vh ,Vd Vi,Vd Vj ,Ve Vk , Ve Vl ,Vh Vm }。 树的根为A，根结点无前驱。{D-{A}}存在三个不相交的划分： D1={ Vb Ve Vf Vk Vl } D2={ Vc Vg } D3={ Vd Vh Vi Vj Vm } 第6章 树与二叉树 与数据结点相应关系{R-{Va VbVa Vc Va Vd }}存在三个不相交的划分： R1={Vb Ve Vb Vf Ve Vk Ve Vl } R2={Vc Vg} R3={Vd Vh Vd Vi Vd Vj Vh Vm } 且(D1 R1)﹑(D2 R2)﹑(D3 R3)分别组成三棵树，是根的子树。 显然在这个描述中根是李奶奶，三棵子树 (D1 R1)﹑(D2 R2)﹑(D3 R3)所描述的是李奶奶的三个儿子的家庭关系。递归定义。 图6.2(a)是只有一个根节点的树，图6.2(b)、(c)、(d)是不同的树。 第6章 树与二叉树 第6章 树与二叉树 树的有关术语： 结点：包含一个数据元素及描述与其他结点关系的信息（如前驱、后继指针）。 结点的度：一个结点直接后继的个数称为该结点的度。图6.2（b）中A结点的度为3。 树的度：树所有结点的度的最大值。图6.2(b)中各结点的最大度为3，树的度为3。 叶结点：度为0的结点，是无后继的结点，也称为终端结点。图6.2(b)中{E，F，C，G}四个结点都是叶结点。 孩子：一个结点的直接后继称为该结点的孩子。 第6章 树与二叉树 双亲：一个结点的直接前驱称为该结点的双亲。 结点的层次：从根结点开始层次为l，根节点的后继结点的层次为2，依此类推。图6.2(b)结点A层次号为1；B、C、D层次号为2；E、F、G的层次号为3。 兄弟：同一双亲的孩子结点之间互称兄弟。 堂兄弟：同一层上不同双亲的结点称为堂兄弟。图6.2(b)中F、G互为堂兄弟。 子孙：一个结点的直接后继和间接后继称为该结点的子孙。在图6.1中结点D的子孙是H、I、J、M。 第6章 树与二叉树 祖先：是从该结点开始追溯前驱直到根结点，所经历的所有结点。图6.2（b）中结点F的祖先是A、B。 树的高度(深度)：树中所有结