第7章 吕钢 西南科技大学计算机学院 信息教研室 Data structure Lri
Data Structure LXJ 第 7 章 树 和 二叉树 西南科技大学 计算机学院 信息教研室
内容提纲 71仿真指针 72树 73二叉树 74链式存储结构的二叉树设计 75二叉树遍历游标类 7.6线索二叉树 77堆 78哈夫曼树 Data structure Lri
Data Structure LXJ 内容提纲 7.1 仿真指针 7.2 树 7.3 二叉树 7.4 链式存储结构的二叉树设计 7.5 二叉树遍历游标类 7.6 线索二叉树 7.7 堆 7.8 哈夫曼树
第一部分 仿真指 Data structure Lri
Data Structure LXJ 第一部分 仿真指针
7。仿真指针 head-a0+ ar+a2+ a A)常规链表:链式存储实现,使用指针 data neⅹt ao B) a 1 静态链表:顺序存 储实现(数组),使用 2 a 4 仿真指针 3 a2 a 2 3 Data structure Lri
Data Structure LXJ 7.1仿真指针 A）常规链表：链式存储实现，使用指针 head a0 a1 a2 a3 a4 ^ a 2 3 a 4 2 a －1 4 a 3 1 a 1 0 0 2 3 1 4 data next B） 静态链表：顺序存 储实现(数组),使用 仿真指针
第二部分 Data structure Lri
Data Structure LXJ 第二部分 树
72n1树的定义 树tree的递归定义: 口树(tree是n个数据元素的有限集(记为T),对任意 棵树T有: 1.存在唯一一个称为根(root)的数据元素; 2.当n>1时,其它数据元素可分为m(血m>0)个互不相交的有 限集T1,T2,∴,Tm,其中每个集合T(i=1,2,…,m)本身又 是一棵树,并称树T;是根的子树( subtree A (空树) A B C D E G (a) (b) Data structure Lri
Data Structure LXJ 7.2.1 树的定义 树tree的递归定义： ❑ 树(tree)是n个数据元素的有限集(记为T)，对任意 一棵树T有： 1. 存在唯一一个称为根(root) 的数据元素； 2. 当n＞1时，其它数据元素可分为m(m＞0) 个互不相交的有 限集T1,T2,•…,Tm，其中每个集合Ti(i=1,2,…,m)本身又 是一棵树，并称树 Ti是根的子树(subtree). A B C D E F G (空树) A （a） （b） （c）
树的结点(Node) 层次0 根结点 父结点 层次1……(B… 子结点 层次2 (E.G.H 层次3… 叶结点 根结点、叶结点、分支结点、孩子结点、双亲结点、兄弟结点、 祖先结点、子孙结点 Data structure Lrg
Data Structure LXJ 树的结点（Node） 根结点、叶结点、分支结点、孩子结点、双亲结点、兄弟结点、 祖先结点、子孙结点
结点的度、树的度 A 3度 根 B F)G H 0度 叶 K 2个3度点A,D 树的度:树中所有结点 的度的最大值。 2个2度点BE 上图:树的度为3 2个1度点CH 7个叶FG,K,L,M Data structure Lri
Data Structure LXJ 结点的度、树的度 A B C D E F G H I J K L M ································· ·······根 3度 ············· 叶 0度 2个3度点 A,D 2个2度点 B,E 2个1度点 C,H 7个叶 F,G,I,J,K,L,M 树的度：树中所有结点 的度的最大值。 上图：树的度为3
结点的层次、树的深度 A 第一层 B C 第二层 )GH ①① 第三 层 K 第四层 树的深度为4 Data structure Lri
Data Structure LXJ 结点的层次、树的深度 树的深度为4 A B C D E F G H I J K L M ··········································· ··第一层 ······························ 第二层 ···············第三 层 ···································· 第四层
序树、森林 口无序树:树中任意一个结点的各个子树之间的次序 构成无关紧要,交换树中任意一个结点的各个子树 的次序均和原树相同的树构成无序树 有序树:树中任意一个结点的任意子树都是有次序 的树。 口森林:m颗树的集合称为森林。 A A A B B C E F G 森林 Data structure Lri
Data Structure LXJ 序树、森林 ❑ 无序树：树中任意一个结点的各个子树之间的次序 构成无关紧要，交换树中任意一个结点的各个子树 的次序均和原树相同的树构成无序树。 ❑ 有序树：树中任意一个结点的任意子树都是有次序 的树。 ❑ 森林：m颗树的集合称为森林。 A B C D E F G A 森林 A B C