《NOIP普与讲座5-树的基础知识》由会员分享，可在线阅读，更多相关《NOIP普与讲座5-树的基础知识（45页珍藏版）》请在金锄头文库上搜索。
1、树的基础知识 江苏省华罗庚中学杨志军 树的基本概念 01 二叉树的基本知识 02 二叉树的应用 03 特殊二叉树 04 TableofContents 内容大纲 树的基本概念 1 树的定义树是n n 0 个结点的有穷集合 满足 有且仅有一个称为根的结点 其余结点分为m m 0 个互不相交的非空集合T1 T2 Tm 这些集合中的每一个都是一棵树 称为根的子树 树的基本概念 2 树的表示方法 图示表示 广义表表示 T 1 T1 T2 T3 1 2 T11 T12 3 4 T31 1 2 5 6 3 4 7 T311 T312 1 2 5 6 3 4 7 8 9 树的基本概念 3 树的基本术语 结点
2、的度和树的度结点的度 每个结点具有的子树的个数或者说其后继结点的个数被定义为该结点的度 树的度 所有结点的度的最大值定义为该树的度 树的基本概念 3 树的基本术语 分支结点和叶子结点度大于0的结点称为分支结点或非终端结点 度为0的结点称为叶子结点 树的基本概念 3 树的基本术语 孩子结点 双亲结点和兄弟结点每个结点的后继结点被称为该结点的孩子结点 相应的该结点被称为双亲结点或父亲结点 具有同一双亲结点的孩子结点互称为兄弟结点 树的基本概念 3 树的基本术语 树的深度和宽度树中的结点的最大层数称为树的深度或高度 整棵树中某一层中最多的结点数称为树的宽度 二叉树的基本知识 1 二叉树的基本概念二叉
3、树是一种特殊的树型结构 它是度数最多为2的树 即二叉树的每个结点最多有两个子结点 二叉树的基本知识 2 二叉树的性质 性质1 在二叉树的第i层上至多有2i 1个结点 i 1 性质2 深度为h的二叉树至多有2h 1个结点 h 1 一棵深度为k且有2k 1个结点的二叉树称为满二叉树 二叉树的基本知识 2 二叉树的性质 性质3 对任何一棵二叉树 如果其叶结点数n0 度为2的结点数为n2 则一定满足 n0 n2 1 性质4 具有n个结点的完全二叉树的深度为trunc log2n 1 完全二叉树的定义 深度为k 有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时
4、称为完全二叉树 二叉树的基本知识 2 二叉树的性质 性质5 对于一棵n个结点的完全二叉树 对任一个结点 编号为i 如果i 1 则结点i为根 无父结点 如果i 1 则其父结点编号为trunc i 2 如果2i n 则结点i无左孩子 即结点i为叶结点 否则左孩子编号为2i 如果2i 1 n 则结点i无右孩子 否则右孩子编号为2i 1 二叉树的基本知识 3 二叉树的存储结构 顺序存储对一个完全二叉树的所有结点按层编号 将编号为i的结点存入一维数组的第i个单元 二叉树的基本知识 3 二叉树的存储结构 顺序存储对一个完全二叉树的所有结点按层编号 将编号为i的结点存入一维数组的第i个单元 二叉树的基本知识
5、 3 二叉树的存储结构 链式存储typenode recorddata char left right longint end vara array 1 n ofnode 二叉树的基本知识 3 二叉树的存储结构 链式存储structnode chardata intleft right nodea 1001 二叉树的基本知识 3 二叉树的存储结构 二叉树的基本知识 4 二叉树的建立 顺序存储 s string s LDPCFM EH N 二叉树的基本知识 4 二叉树的建立 顺序存储 strings s LDPCFM EH N 二叉树的基本知识 4 二叉树的建立 链式存储 L23D45P60C0
6、0F78M09E00H00N00 二叉树的基本知识 5 二叉树的基本运算1 二叉树的输出运算 采用广义表 设标记flag 0 如果当前结点不为空 则输出该结点 如果当前结点的左子树不为空 则输出 flag 1 递归其左子树 如果当前结点的右子树不为空 若flag 0 则输出 flag 1 否则输出 递归其右子树 如果flag 1 则输出 二叉树的基本知识 5 二叉树的基本运算2 二叉树的遍历运算 先序 中序 后序 先序遍历的操作定义如下 若二叉树为空 则空操作 否则 访问根结点 先序遍历左子树 先序遍历右子树A B C D E F G H 二叉树的基本知识 5 二叉树的基本运算2 二叉树的遍历
7、运算 先序 中序 后序 中序遍历的操作定义如下 若二叉树为空 则空操作 否则 中序遍历左子树 访问根结点 中序遍历右子树C B A F E G D H 二叉树的基本知识 5 二叉树的基本运算2 二叉树的遍历运算 先序 中序 后序 后序遍历的操作定义如下 若二叉树为空 则空操作 否则 后序遍历左子树 后序遍历右子树 访问根结点C B F G E H D A 二叉树的基本知识 5 二叉树的基本运算3 求二叉树的深度若二叉树为空 则深度为0否则 深度 左子树与右子树中最大深度 1 二叉树的应用 例1 已知一棵二叉树的先序遍历和中序遍历的结果 请你编程输出这棵二叉树的后序遍历结果 样例输入 ABDEG
8、KHCFIDBKGEHAFIC 样例输出 DKGHEBIFCA 二叉树的应用 分析 先序 ABDEGKHCFI中序 DBKGEHAFIC因为二叉树的先序遍历是先访问根结点A 再遍历左子树 最后遍历右子树 而中序遍历是先遍历左子树 再访问根结点A 最后遍历右子树 所以结点A把中序遍历的字符串分成了两个部分 A之前的是左子树上的结点 A之后的是右子树上的结点 依此类推 便可得到整个二叉树 二叉树的应用 分析 先序 ABDEGKHCFI中序 DBKGEHAFIC A BDEGKH CFI 二叉树的应用 分析 先序 ABDEGKHCFI中序 DBKGEHAFIC A BDEGKH CFI B D EG
9、KH 先序 ABDEGKHCFI中序 DBKGEHAFICproceduretry l1 r1 l2 r2 longint varm longint beginm pos s1 l1 s2 ifm l2thentry l1 1 l1 m l2 l2 m 1 ifm r2thentry l1 m l2 1 r1 m 1 r2 write s1 l1 end 先序 ABDEGKHCFI中序 DBKGEHAFICvoidp intl1 intr1 intl2 intr2 intm m s2 find s1 l1 if m l2 p l1 1 l1 m l2 l2 m 1 if m r2 p l1 m
10、 l2 1 r1 m 1 r2 cout s1 l1 二叉树的应用 例2 具有n个结点的不同形态的二叉树有多少棵 样例输入 3 样例输出 5 二叉树的应用 分析 一般情况 一棵具有n n 0 个结点的二叉树可以看成是由一个根结点 一棵具有i个结点的左子树 和一棵具有n 1 i个结点的右子树组成 其中0 i n 1 i 0表示无左子树 i n 1表示无右子树 根据乘法原理可以得出具有n个结点的不同形态的二叉树有Fn棵 二叉树的应用 分析 F0 1F1 1F2 F0 F1 F1 F0 1 1 1 1 2F3 F0 F2 F1 F1 F2 F0 1 2 1 1 2 1 5 Fn F0 Fn 1 F1
11、 Fn 2 Fn 2 F1 Fn 1 F0 特殊二叉树 1 二叉排序树1 定义二叉排序树具有这样的性质 任何结点的值都大于它左子树上结点的值 小于右子树上结点的值 然后采用中序遍历就可以生成一个有序序列 特殊二叉树 1 二叉排序树2 建立二叉排序树先生成一个结点 加入到树中 如果不是根结点 再根据大小决定这个结点是插在某个节点的左子树上还是右子树上 如此重复 例 312465 3 1 4 2 6 5 特殊二叉树 1 二叉排序树3 二叉排序树的查找从根结点开始 如果要查找的数与该结点不相等 则根据与该结点的值比较 选择查找左子树 还是右子树 直到没有结点 例 查找2例 查找7 特殊二叉树 2 哈
12、夫曼树1 定义树的带权路径长度为树中所有叶子结点的带权路径长度之和 也称WPL 哈夫曼树又称为最优二叉树 它是n个带权叶子结点构成的二叉树中WPL最小的二叉树 WPL 5 2 4 2 2 3 9 3 51 WPL 9 1 5 2 2 3 4 3 37 WPL 2 2 4 2 5 2 9 2 40 特殊二叉树 2 哈夫曼树2 构造哈夫曼树 根据给定的n个权值 w1 w2 wn 构造n棵二叉树的集合F T1 T2 Tn 其中每棵二叉树中均只含一个带权值为wi的根结点 其左 右子树为空树 在F中选取其根结点的权值为最小的两棵二叉树 分别作为左 右子树构造一棵新的二叉树 并置这棵新的二叉树根结点的权值
13、为其左 右子树根结点的权值之和 从F中删去这两棵树 同时加入刚生成的新树 重复 和 两步 直到F中只含一棵树为止 特殊二叉树 2 哈夫曼树例 对权值分别是3 1 4 5 1 3的结点构造哈夫曼树 3 1 4 5 1 3 初赛试题 noip2014普及组选择题第16题 1 一棵具有5层的满二叉树中结点数为 A 31B 32C 33D 16 noip2015提高组问题求解第2题 2 结点数为5的不同形态的二叉树一共有种 结点数为2的二叉树一共有2种 一种是根结点和左儿子 另一种是根结点和右儿子 初赛试题 noip2016普及组选择题第11题 3 一棵二叉树如右图所示 若采用顺序存储结构 即用一维数
14、组元素存储该二叉树中的结点 根结点的下标为1 若某结点的下标为i 则其左孩子位于下标2i处 右孩子位于下标 2i 1 处 则图中所有结点的最大下标为 A 6B 10C 12D 15 初赛试题 noip2015普及组选择题第17题 提高组选择题第8题 4 如果根的高度为1 具有61个结点的完全二叉树的高度为 A 5B 6C 7D 8 noip2016普及组问题求解第2题 5 约定二叉树的根节点高度为1 一棵结点数为2016的二叉树最少有个叶子结点 一棵结点数为2016的二叉树最小的高度值是 初赛试题 noip2016提高组选择题第7题 6 一棵二叉树如右图所示 若采用二叉树链表存储该二叉树 各个结点包括结点的数据 左孩子指针 右孩子指针 如果没有左孩子或者右孩子 则对应的为空指针 那么该链表中空指针的数目为 A 6B 7C 12D 14 知识回顾KnowledgeReview 祝您成功
