数据结构讲义树和叉树.pptVIP

第六章 树和二叉树 树是一种重要的非线性数据结构。 树的特点： 每个结点至多有一个前驱，可有多个后继。 树的应用： 在现实中的应用： 如族谱、各种社会组织机构等。 在计算机领域： 编译程序中的语法树、数据库系统中的索引等。 6.1 树的定义和基本术语 1、树的定义 树是由 n (n≥ 0) 个结点组成的有限集合。 如果n= 0，称为空树； 否则，在一棵非空树中，满足如下两个条件： （1）有一个特定的称之为根(root) 的结点，它只有直 接后继，但没有直接前驱； （2）除根以外的其它结点划分为 m (m ≥ 0) 个互不相 交的有限集合 T0,T1, …, Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。 6.1 树的定义和基本术语 2、树的表示 （1）树型表示（直观表示法） 6.1 树的定义和基本术语 2、树的表示 （1）树型表示（直观表示法） （2）二元组表示 T=(D,R) D={A,B,C,D,E,F,G,H,I,J,K,L,M} R={A,B, A,C, A,D, B,E, B,F, C,G, D,H, D,I, D,J, E,K, E,L, H,M} 6.1 树的定义和基本术语 2、树的表示 （1）树型表示（直观表示法） （2）二元组表示 （3）凹入法 6.1 树的定义和基本术语 2、树的表示 （1）树型表示（直观表示法） （2）二元组表示 （3）凹入法 （4）嵌套集合表示 6.1 树的定义和基本术语 2、树的表示 （1）树型表示（直观表示法） （2）二元组表示 （3）凹入法 （4）嵌套集合表示 （5）广义表表示（嵌套括号表示 ） 6.1 树的定义和基本术语 3、基本术语 结点（node）：包含一个数据元素及若干指向其它结点的分支信息。 结点的度(degree)：结点的子树个数 叶结点(leaf)：度为0的结点，也称为终端结点。 分支结点(branch)：度不为0的结点，也称为非终端结点。 孩子结点(child)：一个结点的直接后继或某结点子树的根结点 。 双亲结点(parent)：一个结点的直接前驱或某个结点是其子树之根的 双亲 。 6.1 树的定义和基本术语 3、基本术语 兄弟(sibling)结点: 具有同一双亲的所有结点 祖先(ancestor)结点: 若树中结点k到ks存在一条路径，则称 k是ks的祖先 子孙(descendant)结点: 若树中结点k到ks存在一条路径，则称ks是k的子孙 结点所处层次(level) :根结点的层数为1，其余结点的层 ，其余结点的层 数为双亲结点的层数加 1 树的高度(depth):树中结点的最大层数 树的度(degree):树中结点的最大度数 6.1 树的定义和基本术语 3、基本术语 有序树 子树的次序不能互换 无序树 子树的次序可以互换 森林（Forest） 互不相交的树的集合 4、树的基本操作 初始化 求指定结点所在树的根结点 求指定结点的双亲结点 求指定结点的某一孩子结点 求指定结点的最右边兄弟结点 将一棵树插入到另一树的指定结点下作为它的子树 删除指定结点的某一子树 树的遍历 6.2 二叉树 (Binary Tree) 6.2.1 二叉树的定义 1、二叉树（Binary Tree）或为空树，或由根及两棵不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。 6.2 二叉树 (Binary Tree) 6.2.1 二叉树的定义 2、二叉树的五种不同形态 6.2 二叉树 (Binary Tree) 6.2.1 二叉树的定义 3、二叉树和树的区别： 二叉树不是树的特殊情形，它们是两个概念。 树和二叉树之间最主要的差别是：二叉树中结点的子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。 6.2 二叉树 (Binary Tree) 6.2.2 二叉树的性质 性质1：在二叉树的第i层上至多有2i-1个结点(i≥1) 性质2：深度为k的二叉树最多有2k-1个结点。(k≥1) 性质3：对任何一棵二叉树, 如果其叶结点个数为n0,度为2的非叶结点个数为n2, 则有n0＝n2＋1。 6.2 二叉树 (Binary Tree) 6.2.2 二叉树的性质 两种特殊的二叉树： 满二叉树：深度为k且有2k-1个结点的二叉树。 在满二叉树中，每层结点都是满的，即每层结点都具 有最大结点数。 6.2 二叉树 (Binary Tree) 6.2.2 二叉树的性质 两种特殊的二叉树： 完全二叉树：若设二叉树的高度为h，除第 h层外，其它各层的结点