数据结构与 chap6 .ppt

课前导学 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用 【学习目标】 【重点和难点】 重点：二叉树和树的遍历及其应用 难点：编写实现二叉树和树的各种操作的递归算法 【知识点】　　树、二叉树、二叉树的遍历、线索二叉树、树和森林的存储表示、树和森林的遍历、最优树和哈夫曼编码 【课前思考】 你见过家族谱系图吗？试以图形表示从你的祖父起的家族成员关系。 上列家族谱系图可用如下关系表示：　祖父，伯父，祖父，父亲，祖父，叔父，伯父，堂兄，伯父，堂姐，父亲，你，叔父，堂弟，堂兄，侄儿 6.1 树的定义和基本术语 定义：树(tree)是n(n0)个结点的有限集T，其中： 有且仅有一个特定的结点，称为树的根(root) 当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree) 特点： 树中至少有一个结点——根 树中各子树是互不相交的集合 基本术语 结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支 结点的度(degree)——结点拥有的子树数 叶子(leaf)——度为0的结点 孩子(child)——结点子树的根称为该结点的孩子 双亲(parents)——孩子结点的上层结点叫该结点的~ 兄弟(sibling)——同一双亲的孩子 树的度——一棵树中最大的结点度数 结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层…… 深度(depth)——树中结点的最大层次数 森林(forest)——m(m?0)棵互不相交的树的集合 树的抽象数据类型: ADT Tree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 否则: (1)在D中存在唯一的称为根的数据元素root, (2) 当n1时，其余结点可分为m (m0) 个互不相交的有限集 T1, T2, …, Tm, 其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。 基本操作P： 　InitTree(T);　　　操作结果：构造空树 T。CreateTree(T,definition);　　　初始条件：definition 给出树T的定义。　　　操作结果：按 definition 构造树 T。DestroyTree(T);　　　初始条件：树 T 存在。　　　操作结果：销毁树 T。TreeEmpty(T);　　　初始条件：树 T 存在。　　　操作结果：若 T 为空树，则返回 TRUE，否则返回 FALSE。 TreeDepth(T);　　初始条件：树T存在。　　操作结果：返回T的深度。Root(T);　　初始条件：树 T 存在。　　操作结果：返回 T 的根。Value(T, cur_e);　　初始条件：树 T 存在，cur_e 是 T 中某个结点。　　操作结果：返回 cur_e 的值。Parent(T, cur_e);　　初始条件：树 T 存在，cur_e 是 T 中某个结点。　　操作结果：若 cur_e 是T的非根结点，则返回它的双亲，否则返回空。 LeftChild(T, cur_e);　　　初始条件：树 T 存在，cur_e 是 T 中某个结点。　　　操作结果：若 cur_e 是T的非叶子结点，则返回它的 最左孩子，否则返回“空”。 RightSibling(T, cur_e);　　　初始条件：树 T 存在，cur_e 是 T 中某个结点。　　　操作结果：若 cur_e 有右兄弟，则返回它的右兄弟， 否则返回空。TraverseTree(T, visit());　　初始条件：树T存在，visit 是对结点操作的应用函数。　　操作结果：按某种次序对 T 的每个结点调用函数 visit() 一次且至多一次。一旦 visit() 失败，则操作失败。 Assign(T, cur_e, value);　　初始条件：树T存在，cur_e 是 T 中某个结点。　　操作结果：结点 cur_e 赋值为 value。 ClearTree(T);　　初始条件：树 T 存在。　　操作结果：将树 T 清为空树。　InsertChild(T, p, i, c);