人民邮电出版社：高职高专现代信息技术系列教材《数据结构》课程电子教案（PPT课件讲稿）第五章 树和二叉树

第5章和二又州 本章中主要介绍下列内容: 树的逻辑定义和存储结构 二叉树的逻辑定义、存储结构 二叉树的基本操作算法 树和二叉树的转换 哈夫曼树及其应用 请单赤鼠标左键换页! 退出

第5章 树和二叉树 本章中主要介绍下列内容： ⚫ 树的逻辑定义和存储结构 ⚫ 二叉树的逻辑定义、存储结构 ⚫ 二叉树的基本操作算法 ⚫ 树和二叉树的转换 ⚫ 哈夫曼树及其应用 退出

5.2二叉树 5.3哈未最越及其应 请单赤鼠标左键换页!

5.1 树 5.2 二叉树 5.3 哈夫曼树及其应用

51树 5.1.1树的定义和基本运算 1.定义 树是一种常用的非线性结构。我们可以这样定义: 树是n(n≥0)个结点的有限集合。若n=0,则称为空 树;否则,有且仅有一个特定的结点被称为根,当n>1 时,其余结点被分成m(m>0)个互不相交的子集T1, T2,…,Tm,每个子集又是一棵树。由此可以看出, 树的定义是递归。 请单赤鼠标左键换页!

5.1 树 5.1.1 树的定义和基本运算 1. 定义 树是一种常用的非线性结构。我们可以这样定义： 树是n（n≥0）个结点的有限集合。若n=0，则称为空 树；否则，有且仅有一个特定的结点被称为根，当n>1 时，其余结点被分成m（m>0）个互不相交的子集T1， T2，...，Tm，每个子集又是一棵树。由此可以看出， 树的定义是递归

B 图5-1 请单赤鼠标左键换页!

图 5-1 K L M E F G H I J B C D A A  (a) (b) (c)

结点数据元素的内容及其指向其子树根的分支统 称为结点。 结点的度结点的分支数。 终端结点(叶子)度为0的结点。 非终端结点度不为0的结点。 结点的层次树中根结点的层次为1,根结点子树 的根为第2层,以此类推。 树的度树中所有结点度的最大值。 树的深度树中所有结点层次的最大值。 有序树、无序树如果树中每棵子树从左向右的排 列拥有一定的顺序,不得互换,则称为有序树,否则 称为无序树。 请单鼠标左键换页!

结点 数据元素的内容及其指向其子树根的分支统 称为结点。 结点的度 结点的分支数。 终端结点（叶子） 度为0的结点。 非终端结点 度不为0的结点。 结点的层次 树中根结点的层次为1，根结点子树 的根为第2层，以此类推。 树的度 树中所有结点度的最大值。 树的深度 树中所有结点层次的最大值。 有序树、无序树 如果树中每棵子树从左向右的排 列拥有一定的顺序，不得互换，则称为有序树，否则 称为无序树

森林是m(m≥0)棵互不相交的树的集合。 在树结构中,结点之间的关系又可以用家族关系 描述,定义如下: 孩子、双亲结点子树的根称为这个结点的孩子, 而这个结点又被称为孩子的双亲。 子孙以某结点为根的子树中的所有结点都被称 为是该结点的子孙。 祖先从根结点到该结点路径上的所有结点。 兄弟同一个双亲的孩子之间互为兄弟。 堂兄弟双亲在同一层的结点互为堂兄弟。 请单赤鼠标左键换页!

森林 是m（m≥0）棵互不相交的树的集合。 在树结构中，结点之间的关系又可以用家族关系 描述，定义如下： 孩子、双亲 结点子树的根称为这个结点的孩子， 而这个结点又被称为孩子的双亲。 子孙 以某结点为根的子树中的所有结点都被称 为是该结点的子孙。 祖先 从根结点到该结点路径上的所有结点。 兄弟 同一个双亲的孩子之间互为兄弟。 堂兄弟 双亲在同一层的结点互为堂兄弟

2.树的基本运算 常用操作: (1)构造一个树 CreateTree(① (2)清空以T为根的树 ClearTree( (3)判断树是否为空 TreeEmpty(T (4)获取给定结点的第论个孩子 Child(T, node i) (5)获取给定结点的双亲 Parent(T,node) (6)遍历树 Traverse(T 对树遍历的主要目的是将非线性结构通过遍历过程 线性化,即获得一个线性序列。树的遍历顺序有两种, 种是先序遍历,即先访问根结点,然后再依次用同 样的方法访问每棵子树;另一种是后序遍历,即先依 请单赤鼠标左键换页!

2. 树的基本运算 常用操作： （1） 构造一个树 CreateTree (T) （2）清空以T为根的树 ClearTree(T) （3）判断树是否为空 TreeEmpty(T) （4）获取给定结点的第i个孩子 Child(T,node,i) （5）获取给定结点的双亲 Parent(T,node) （6）遍历树Traverse(T) 对树遍历的主要目的是将非线性结构通过遍历过程 线性化，即获得一个线性序列。树的遍历顺序有两种， 一种是先序遍历，即先访问根结点，然后再依次用同 样的方法访问每棵子树；另一种是后序遍历，即先依

5.1.2树的存储结构 1.双亲表示法 树的双亲表示法主要描述的是结点的双亲关系。 请单鼠标左键换页!

5.1.2 树的存储结构 1. 双亲表示法 树的双亲表示法主要描述的是结点的双亲关系

下标 info paren 0123456789 ABCDEFGH 000 3666 图5-3 请单鼠标左键换页!

图 5-3 下标 info paren t 0 A -1 1 B 0 2 C 0 3 D 0 4 E 1 5 F 1 6 G 3 7 H 6 8 I 6 9 J 6 H I J E F G B C D A A B C D E F G H I J

类型定义: #define max tree node size 1oo typedef struct i TEntryType info; int parent; 3 ParentNode typedef struct ParentNode item MAX TREE NODE SIZE; intn;∥树中当前的结点数目 iParentTree 请单鼠标左键换页!

类型定义： #define MAX_TREE_NODE_SIZE 100 typedef struct { TEntryType info; int parent; } ParentNode; typedef struct { ParentNode item[MAX_TREE_NODE_SIZE]; int n; //树中当前的结点数目 }ParentTree;