[工学]数据结构第6章树和二叉树.doc

2000年1月25日 北京理工大学 / 6.1 树的定义与基本术语 树是n个结点的有限集合，在任一棵非空树中： （1）有且仅有一个称为根的结点。 （2）其余结点可分为若干个互不相交的集合，且这些集合中的每一集合本身又是一棵树，称为根的子树。 6.1 树的定义与基本术语 数据对象D D是具有相同特性的数据元素的集合。 数据关系 R 若D为空集，则称为空树。 否则： (1) D中存在唯一的称为根的数据元素root； (2) 当n1时，其余结点可分为m(m0)个互不相交的有限集T1, T2, …, Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。 6.1 树的定义与基本术语 例：右面的图是一棵树 T。 6.1 树的定义与基本术语 逻辑结构： 1）树是一种分支结构：（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。 2）除根外的其它结点，都存在唯一一条从根到该结点的路径； 6.1 树的定义与基本术语 6.1 树的定义与基本术语 树的应用 常用的数据组织形式——计算机的文件系统。 不论是DOS文件系统还是window文件系统，所有的文件都是用树的形式进行组织。 6.1 树的定义与基本术语 树的表示 1）图示表示 2）广义表表示: (A(B(E, F), C(G), D(H, I, J))) 3）集合嵌套表示法 4）凹入表示法（类似书的目录） 6.1 树的定义与基本术语 6.1 树的定义与基本术语 6.1 树的定义与基本术语 6.1 树的定义与基本术语 树的基本操作 1) InitTree ( T ); //构造空树 T。 2) DestroyTree ( T ); //销毁树 T。 3) CreateTree ( T, definition ); //按 definition 构造树 T。 4) ClearTree ( T ); //将树 T 清空。 5) TreeEmpty ( T ); 若树 T 为空，返回 TURE，否则返回 FALSE。 6) TreeDepth ( T ); //返回树 T 的深度。 6.1 树的定义与基本术语 树的基本操作 7) Root ( T ); //返回 T 的根结点。 8) Value ( T, cur_e ); //返回 T 树中 cur_e 结点的值。 9) Assign ( T, cur_e, value ); //将 T 树中结点 cur_e 的值赋值为 value。 10) Parent ( T, cur_e ); //返回 T 树 cur_e 结点的双亲。 11) LeftChild ( T, cur_e ); //返回 T 树 cur_e 结点的最左孩子。 12) RightSibling ( T, cur_e ); //返回 T 树 cur_e 结点的右兄弟。 6.1 树的定义与基本术语 树的基本操作 13) InsertChild ( T, p, i, c ); 将 c 插入到树 T 中 p 所指向的第 i 棵子树中。 14) DeleteChild ( T,p, i ); 删除树 T 中 p 所指向的第 i 棵子树。 15) TraverseTree ( T, Visit( ) ); 按某种次序对 T 树的每个结点调用函数 Visit( )一次且至多一次。也称为按照某种次序对树进行遍历。 6.2 二叉树 数据对象D D是具有相同特性的数据元素的集合。 数据关系 R 若 D＝Φ，则R＝Φ，称为空二叉树。 若 D≠Φ，则R={H}，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若 D-{root}≠Φ，则存在 D-{root} = {Dl, Dr}，且Dl∩Dr=Φ； 6.2 二叉树 定义 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 6.2 二叉树 二叉树的五种基本形态 6.2 二叉树 二叉树 6.2 二叉树 性质1： 在二叉树的第 i 层上至多有2i-1 个结点(i≥1)。 6.2 二叉树 性质2： 深度为k的二叉树上至多含2k-1个结点(k≥1)。 6.2 二叉树 性质3： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1 6.2 二叉树 两类特殊的二叉树 6.2 二叉树 完全二叉树的特点： 1）叶子节点只可能