[工学]数据结构_树和二叉树.ppt

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）除根外，其余结点都有且仅一个前趋； 3）树的结点，可以有零个或多个后继； 4）除根外的其它结点，都存在唯一条从根到该结点的路径； 5）树是一种分支结构（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。 6.1 树的定义与基本术语 树的应用 常用的数据组织形式——计算机的文件系统。 不论是DOS文件系统还是window文件系统，所有的文件都是用树的形式进行组织。 6.1 树的定义与基本术语 树的表示 1）图示表示 2）二元组表示 3）文氏图表示 4）凹入表示法（类似书的目录） 5）广义表表示 6.1 树的定义与基本术语 树的基本术语 树的结点：包含一个数据元素的内容及若干指向子树的分支。 孩子结点：结点的子树的根称为该结点的孩子；如E是B的孩子。 双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；如B是E的双亲。 兄弟结点：同一双亲的孩子结点；如H、I、J互为兄弟。 堂兄结点：同一层上结点；如G与E、F、H、I、J互为堂兄。 6.1 树的定义与基本术语 祖先结点：某一结点的祖先是从根到该结点所经分支上的所有结点；如H的祖先为A、D。 子孙结点：以某结点为根的子树中的任一结点称为该结点的子孙；如A的子孙为B、C、D、E、F、G、H、I、J。 结点的度：结点子树的个数；如D的度为3。 叶子结点：也叫终端结点，是度为0的结点；如E、F、G、H、I、J。 分枝结点：度不为0的结点；如A、B、C、D。 6.1 树的定义与基本术语 结点层次：根结点的层定义为1，根的孩子为第2层结点，依此类推。 树的高度（深度）：树中结点的最大层次；如图所示树的高度为3。 树的度：树中各结点的度的最大值；如图所示树的度为3。 有序树：子树之间存在明确的次序关系的树。 无序树：不考虑子树的顺序。 森林：m（m=0）棵互不相交的树的集合。 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( ) ); 按某种次