数据结构叉树

1、6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二叉二叉树树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 6.4 树和森林树和森林6.6 6.6 哈夫曼树及其应用哈夫曼树及其应用第六章第六章 树和二叉树树和二叉树6.2 二叉树二叉树6.2.1 二叉树的定义二叉树的定义（1）定义）定义 二叉树（二叉树（binary tree）：是另一种树型结构。：是另一种树型结构。 特点：特点：每个结点至多只有两棵子树（即二叉树中不存在度大于每个结点至多只有两棵子树（即二叉树中不存在度大于2 的结点）。的结点）。 子树有左右之分，其次序不能任意颠倒。子树有左右之分，其次

2、序不能任意颠倒。（2）图形表示）图形表示 (a) (b) (c) (d) (e)图图6.3二叉树的二叉树的5种基本形态种基本形态(a) 空二叉树空二叉树(b) 仅有根结点的二叉树仅有根结点的二叉树(c) 右子树为空的二叉树右子树为空的二叉树(d) 左、右子树均非空的二叉树左、右子树均非空的二叉树(e) 左子树为空的二叉树左子树为空的二叉树&定义：是由定义：是由n（n=0)个结点的有限集合，个结点的有限集合，它或为空树（它或为空树（n=0），或由一个根结点和至多），或由一个根结点和至多两棵称为根的左子树和右子树的互不相交的两棵称为根的左子树和右子树的互不相交的二叉树组成。二叉树组成。&a

3、mp;注：二叉树中不存在度大于注：二叉树中不存在度大于2的结点，并且的结点，并且二叉树的子树有左子树和右子树之分。二叉树的子树有左子树和右子树之分。二叉树的定义二叉树的定义： 二叉树或为空树空树；或是由一个根结根结点点加上两棵两棵分别称为左子树左子树和右子树的、互不交的互不交的二叉树二叉树组成。abcdefghk根结点左子树右子树ef二叉树的五种基本形态：二叉树的五种基本形态：n空树空树只含根结点只含根结点nnnlrr右子树为空树右子树为空树l左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树（3）二叉树的抽象数据类型定义）二叉树的抽象数据类型定义 h，且存在，且存在dl上的关系上的

4、关系hr h；h = , , hl, hr； （4）(dl, hl)是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的左子树，(dr, hr) 是一棵符合本定义的二叉树，称为根的右子树。是一棵符合本定义的二叉树，称为根的右子树。基本操作：基本操作： adt binarytree数据对象数据对象d：d是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系r： 若若d = ，则，则r =，称称binarytree为空二叉树；为空二叉树； 若若d，则，则r=h,h是如下二元关系：是如下二元关系： （1）在）在d中存在唯一的称为根的数据元素中存在唯一

5、的称为根的数据元素root，它在关系，它在关系h下无前驱；下无前驱； （2）若）若droot，则存在，则存在droot = dl, dr，dl且且dm =； （3）若）若dl，则，则dl中存在唯一的元素中存在唯一的元素x1，有有h，且存在，且存在dl 上的关系上的关系hl h;若若 dr,则则dr中存在唯一的元素中存在唯一的元素xr, ,有有 initbitree (&t);操作结果：构造空二叉树操作结果：构造空二叉树t。 destroybitree (&t);初始条件：二叉树初始条件：二叉树t存在。存在。操作结果：销毁二叉树操作结果：销毁二叉树t。 createbitree

6、(&t, definition);初始条件：初始条件：definition给出二叉树给出二叉树t的定义。的定义。操作结果：按操作结果：按definition构造二叉树构造二叉树t。 clearbitree (&t);初始条件：二叉树初始条件：二叉树t存在。存在。操作结果：将二叉树操作结果：将二叉树t清为空树。清为空树。 bitreeempty(t);初始条件：二叉树初始条件：二叉树t存在。存在。操作结果：若操作结果：若t为空二叉树，则返回为空二叉树，则返回true，否则返回，否则返回false。 bitreedepth(t);初始条件：二叉树初始条件：二叉树t存在。存在。操作结

7、果：返回操作结果：返回t的深度。的深度。 root(t);初始条件：二叉树初始条件：二叉树t存在。存在。操作结果：返回操作结果：返回t的根。的根。 value(t, e);初始条件：二叉树初始条件：二叉树t存在，存在， e是是t中某个结点。中某个结点。操作结果：返回操作结果：返回e的值。的值。 assign(t, &e, value);初始条件：二叉树初始条件：二叉树t存在，存在， e是是t中某个结点。中某个结点。操作结果：结点操作结果：结点e赋值为赋值为value。 parent(t, e);初始条件：二叉树初始条件：二叉树t存在，存在， e是是t中某个结点。中某个结点。操作结果：若

8、操作结果：若e是是t的非根结点，则返回它的双亲，否则函数值为的非根结点，则返回它的双亲，否则函数值为“空空”。 leftchild(t, e);初始条件：二叉树初始条件：二叉树t存在，存在， e是是t中某个结点。中某个结点。操作结果：返回操作结果：返回e的左孩子。若的左孩子。若e无左孩子，则返回无左孩子，则返回“空空”。 rightchild (t, e);初始条件：二叉树初始条件：二叉树t存在，存在， e是是t中某个结点。中某个结点。操作结果：返回操作结果：返回e的右孩子。若的右孩子。若e无右孩子，则返回无右孩子，则返回“空空”。 leftsibling(t, e);初始条件：二叉树初始条件

9、：二叉树t存在，存在， e是是t中某个结点。中某个结点。操作结果：返回操作结果：返回e的左兄弟。若的左兄弟。若e是是t的左孩子或无左兄弟，则返回的左孩子或无左兄弟，则返回“空空”。 rightsibling (t, e);初始条件：二叉树初始条件：二叉树t存在，存在， e是是t中某个结点。中某个结点。操作结果：返回操作结果：返回e的右兄弟。若的右兄弟。若e是是t的右孩子或无右兄弟，则返回的右孩子或无右兄弟，则返回“空空”。 insertchild(t, p, lr, c);初始条件：二叉树初始条件：二叉树t存在，存在，p指向指向t中某个结点，中某个结点，lr为为0或或1，非空二叉，非空二叉 树

10、树c与与t不相交且右子树为空。不相交且右子树为空。操作结果：根据操作结果：根据lr为为0或或1，插入，插入c为为t中中p指结点的左或右子树。指结点的左或右子树。p所指所指 结点的原有左或右子树则成为结点的原有左或右子树则成为c的右子树。的右子树。 deletechild(t, p, lr);初始条件：二叉树初始条件：二叉树t存在，存在，p指向指向t中某个结点，中某个结点，lr为为0或或1。操作结果：根据操作结果：根据lr为为0或或1，删除，删除t中中p所指结点的左或右子树。所指结点的左或右子树。 preordertraverse (t, visit();初始条件：二叉树初始条件：二叉树t存在，

11、存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：先序遍历操作结果：先序遍历t，对每个结点调用函数，对每个结点调用函数visit()一次且仅一次。一次且仅一次。 一旦一旦visit()失败，则操作失败。失败，则操作失败。 inordertraverse (t, visit();初始条件：二叉树初始条件：二叉树t存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：中序遍历操作结果：中序遍历t，对每个结点调用函数，对每个结点调用函数visit()一次且仅一次。一次且仅一次。 一旦一旦visit()失败，则操作失败。失败，则操作失败。 postor

12、dertraverse (t, visit();初始条件：二叉树初始条件：二叉树t存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：后序遍历操作结果：后序遍历t，对每个结点调用函数，对每个结点调用函数visit()一次且仅一次。一次且仅一次。 一旦一旦visit()失败，则操作失败。失败，则操作失败。 levelordertraverse (t, visit();初始条件：二叉树初始条件：二叉树t存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：层序遍历操作结果：层序遍历t，对每个结点调用函数，对每个结点调用函数visit()一次且仅

13、一次。一次且仅一次。 一旦一旦visit()失败，则操作失败。失败，则操作失败。adt binarytree（4）特殊形态的二叉树）特殊形态的二叉树满二叉树满二叉树：一棵深度为：一棵深度为k且有且有2k1个结点的二叉树称为满二叉树。个结点的二叉树称为满二叉树。 特点：每一层上的结点数都是最大结点数。特点：每一层上的结点数都是最大结点数。 完全二叉树完全二叉树：深度为：深度为k的，有的，有n个结点的二叉树，当且仅当其每一个结点的二叉树，当且仅当其每一个结点都与深度为个结点都与深度为k的满二叉树中编号从的满二叉树中编号从1至至n的结点一一对应时，称的结点一一对应时，称之为完全二叉树。之为完全二叉树

14、。特点：特点：叶子结点只可能在层次最大的两层上出现；叶子结点只可能在层次最大的两层上出现； 对任一结点，若其右分支下的子孙的最大层次为对任一结点，若其右分支下的子孙的最大层次为l， 则其左分支下的子孙的最大层次必为则其左分支下的子孙的最大层次必为l或或l1。8 9 10 11 12 13 14 15 12 34 5 6 7(a) 满二叉树满二叉树(b) 完全二叉树完全二叉树8 9 10 11 12 12 34 5 6 7图图6.4特殊形态的二叉树特殊形态的二叉树6 7 1 12 3 2 34 5 4 5 6(c) 非完全二叉树非完全二叉树 (d) 非完全二叉树非完全二叉树6.2.2 二叉树的性

15、质二叉树的性质用归纳法用归纳法证明证明： 归纳基归纳基： 归纳假设：归纳假设： 归纳证明：归纳证明：i = 1 层时，只有一个根结点， 2i-1 = 20 = 1；假设对所有的 j，1 j i，命题成立;二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 。 性质性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1)证明：证明： 基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 性质性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）证明：证明：设设 二叉树上结点总数 n = n0 +

16、 n1 + n2又又 二叉树上分支总数 b = n1 + 2n2而 b = n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1性质性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1除根结点外，其余结点都有一个分支进入，除根结点外，其余结点都有一个分支进入，设设b为分支总数，则为分支总数，则n=b+1。两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。123456789 10 11 12 13 14 15这种树的特点是每一层上的结点数都是最大结点数。两

17、类两类特殊特殊的二叉树：的二叉树：完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号编号为为 1 至至 n 的结点的结点一一对应。abcdefghij可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左至右。由此可引出完全二叉树。完全二叉树的特点完全二叉树的特点（1）叶子结点只可能在层次最大的两层出现；（2）对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次为l或l+1。abcdefghij 性质性质 4 ： 具有 n 个结点的完全二叉树的深度深度为 log2n +1证明：证明：设设 完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2

18、k 即 k-1 log2 n n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子右孩子结点。性质性质 5 ：6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构二、二叉树的链式存储表示二、二叉树的链式存储表示一、一、 二叉树的顺序存储表示二叉树的顺序存储表示#define max_tree_size 100 / 二叉树的最大结点数typedef telemtype sqbitreemax_tree_size; / 0号单元存储根结点sqbitree bt;一、一、 二叉树的顺序存储表

19、示二叉树的顺序存储表示 用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标的结点元素存储在如上定义的一维数组中下标为为i1的分量中。的分量中。 例如例如: a b d c e f 0 1 2 3 4 5 6 7 8 9 10 11 12 13abcdef14013268 9 10 11 12 12 34 5 6 7图图6.5二叉树的顺序存储结构二叉树的顺序存储结构1 2 3 4 5 6 7 8 9 10 11 121 2 3 4 5 0 0 0 0 6 7(a)完全二叉树完全二叉树(b)一般二叉树一般二叉树图中以图中以“0”表示表示不存在此不存在此结点结点6 7 12 34 5adebcf rootlchild data rchild结点结构结点结构:二、二叉树的链式存储表示二、二叉树的链式存储表示图形表示图形表示 a ab bc cd dc