数据结构课件C版第五章.ppt

2020 3 31 mayan 第五章树 树二叉树线索二叉树树与森林堆Huffman树 2020 3 31 mayan 树 树的定义和术语 两种树 自由树与有根有序树 自由树 一棵自由树Tf可定义为一个二元组Tf V E 其中V v1 vn 是由n n 0 个元素组成的有限非空集合 称为顶点 vertex 集合 E vi vj vi vjV 1 i j n 是n 1个序对的集合 称为边集合 E中的元素 vi vj 称为边 edge 或分支 2020 3 31 mayan 树 树的定义和术语 有根树 一棵有根树T 简称为树 它是n n 0 个结点的有限集合 当n 0时 T称为空树 否则 T是非空树 记作其中 r是一个特定的称为根 root 的结点 它没有直接前驱 根以外的其他结点划分为m m 0 个互不相交的有限集合T1 T2 Tm 每个集合又是一棵树 并且称之为根的子树 2020 3 31 mayan 树 树的定义和术语 相关术语子女 若结点的子树非空 结点子树的根即为该结点的子女 双亲 若结点有子女 该结点是子女双亲 兄弟 同一结点的子女互称为兄弟 度 结点的子女个数即为该结点的度 树中各个结点的度的最大值称为树的度 分支结点 度不为0的结点即为分支结点 亦称为非终端结点 2020 3 31 mayan 树 树的定义和术语 叶结点 度为0的结点即为叶结点 亦称为终端结点 祖先 某结点到根结点的路径上的各个结点都是该结点的祖先 子孙 某结点的所有下属结点 都是该结点的子孙 结点的层次 规定根结点在第一层 其子女结点的层次等于它的层次加一 以此类推 深度 结点的深度即为结点的层次 离根最远结点的层次即为树的深度 2020 3 31 mayan 树 树的定义和术语 高度 规定叶结点的高度为1 其双亲结点的高度等于它的高度加一 树的高度 等于根结点的高度 即根结点所有子女高度的最大值加一 有序树 树中结点的各棵子树T0 T1 是有次序的 即为有序树 无序树 树中结点的各棵子树之间的次序是不重要的 可以互相交换位置 森林 森林是m m 0 棵树的集合 2020 3 31 mayan 树 树的抽象数据类型 templateclassTree 在类界面中的position是树中结点的地址 在顺序 存储方式下是下标型 在链表存储方式下是指针型public Tree Tree positionRoot BuildRoot constT 建立树的根结点 2020 3 31 mayan 树 树的抽象数据类型 positionFirstChild positionp 返回p第一个子女地址 无子女返回0positionNextSibling positionp 返回p下一兄弟地址 若无下一兄弟返回0positionParent positionp 返回p双亲结点地址 若p为根返回0TgetData positionp 返回结点p中存放的值boolInsertChild constpositionp constT 在结点p下插入值为value的新子女 若插 入失败 函数返回false 否则返回true 2020 3 31 mayan 树 树的抽象数据类型 boolDeleteChild positionp inti 删除结点p的第i个子女及其全部子孙结 点 若删除失败 则返回false 否则返回truevoidDeleteSubTree positiont 删除以t为根结点的子树boolIsEmpty 判树空否 若空则返回true 否则返回falsevoidTraversal void visit positionp 遍历以p为根的子树 2020 3 31 mayan 二叉树 二叉树的定义 一棵二叉树是结点的一个有限集合 该集合或者为空 或者是由一个根结点加上两棵分别称为左子树和右子树的 互不相交的二叉树组成 2020 3 31 mayan 二叉树 二叉树的性质 性质1若二叉树结点的层次从1开始 则在二叉树的第i i 1 层最多有2i 1个结点 证明用数学归纳法 性质2深度为k k 0 的二叉树最少有k个结点 最多有2k 1个结点 证明 因为每一层最少要有1个结点 因此 最少结点数为k 最多结点个数借助性质1用求等比级数前k项和的公式20 21 22 2k 1 2k 1 2020 3 31 mayan 二叉树 二叉树的性质 性质3对任何一棵二叉树 如果其叶结点有n0个 度为2的非叶结点有n2个 则有n0 n2 1证明 若设度为1的结点有n1个 总结点数为n 总边数为e 则根据二叉树的定义 n n0 n1 n2 e 2n2 n1 n 1因此 有2n2 n1 n0 n1 n2 1则n2 n0 1 n0 n2 1 2020 3 31 mayan 二叉树 二叉树的性质 定义1满二叉树 FullBinaryTree 深度为k的满二叉树是有2k 1个结点的二叉树 定义2完全二叉树 CompleteBinaryTree 若设二叉树的深度为k 则共有k层 除第k层外 其它各层 1 k 1 的结点数都达到最大个数 第k层从右向左连续缺若干结点 这就是完全二叉树 2020 3 31 mayan 二叉树 二叉树的性质 性质4具有n n 0 个结点的完全二叉树的深度为 log2 n 1 证明 设完全二叉树的深度为k 则有2k 1 1 n 2k 1即2k 1 n 1 2k 取对数k 1 log2 n 1 k有k log2 n 1 2020 3 31 mayan 二叉树 二叉树的性质 性质5如将一棵有n个结点的完全二叉树自顶向下 同一层自左向右连续给结点编号1 2 n 则有以下关系 若i 1 则i无双亲 若i 1 则i的双亲为 i 2 若2 i n 则i的左子女为2 i 若2 i 1 n 则i的右子女为2 i 1 若i为奇数 且i 1 则其左兄弟为i 1 若i为偶数 且i n 则其右兄弟为i 1 结点i所在的层次为 log2i 1 2020 3 31 mayan 二叉树 二叉树的抽象数据类型 templateclassBinaryTree public BinaryTree 构造函数BinaryTree BinTreeNode lch BinTreeNode rch Titem 构造函数 以item为根 lch和rch为左 右子树构造一棵二叉树intHeight 求树深度或高度intSize 求树中结点个数 2020 3 31 mayan 二叉树 二叉树的抽象数据类型 boolIsEmpty 判二叉树空否 BinTreeNode Parent BinTreeNode current 求结点current的双亲BinTreeNode LeftChild BinTreeNode current 求结点current的左子女BinTreeNode RightChild BinTreeNode current 求结点current的右子女boolInsert Titem 在树中插入新元素boolRemove Titem 在树中删除元素boolFind constT 判断item是否在树中 2020 3 31 mayan 二叉树 二叉树的抽象数据类型 boolgetData constT 2020 3 31 mayan 二叉树 二叉树的数组存储表示 2020 3 31 mayan 二叉树 二叉树的链表存储表示 二叉链表和三叉链表的概念二叉树结点定义 每个结点有3个域 data域存储结点数据 leftChild和rightChild分别存放指向左子女和右子女的指针 二叉链表如下图所示 2020 3 31 mayan 二叉树 二叉树的链表存储表示 每个结点增加一个指向双亲的指针parent 使得查找双亲也很方便 2020 3 31 mayan 二叉树 二叉树的链表存储表示 整个二叉树的链表有一个表头指针 他指向二叉树的根结点 在含有n个结点的二叉链表中有n 1个空链指针域 三叉链表则有n 2个空链指针域 2n n 1 n 1n 1 1 n 2 2020 3 31 mayan 二叉树 二叉树的链表存储表示 二叉树的链表表示 2020 3 31 mayan 二叉树 二叉链表的类定义 templatestructBinTreeNode 二叉树结点类定义Tdata 数据域BinTreeNode leftChild rightChild 左子女 右子女链域BinTreeNode leftChild NULL rightChild NULL 构造函数BinTreeNode Tx BinTreeNode l NULL BinTreeNode r NULL data x leftChild l rightChild r 2020 3 31 mayan 二叉树 二叉链表的类定义 templateclassBinaryTree 二叉树类定义public BinaryTree root NULL 构造函数BinaryTree Tvalue RefValue value root NULL 构造函数BinaryTree BinaryTree 析构函数 2020 3 31 mayan 二叉树 二叉链表的类定义 boolIsEmpty returnroot NULL 判二叉树空否BinTreeNode Parent BinTreeNode current 返回双亲结点 return root NULL root current NULL Parent root t BinTreeNode LeftChild BinTreeNode current 返回左子女 return current NULL current leftChild NULL 2020 3 31 mayan 二叉树 二叉链表的类定义 BinTreeNode RightChild BinTreeNode current 返回右子女 return current NULL current rightChild NULL intHeight returnHeight root 求树高度intSize returnSize root 求结点数BinTreeNode getRoot const returnroot 取根voidpreOrder void visit BinTreeNode p preOrder root visit 前序遍历 2020 3 31 mayan 二叉树 二叉链表的类定义 voidinOrder void visit BinTreeNode p inOrder root visit 中序遍历voidpostOrder void visit BinTreeNode p postOrder root visit 后序遍历voidlevelOrder void visit BinTreeNode p 层次序遍历intInsert constTitem 插入新元素BinTreeNode Find Titem const 搜索 2020 3 31 mayan 二叉树 二叉链表的类定义 protected BinTreeNode root 二叉树的根指针TRefValue 数据输入停止标志voidCreateBinTree istream 查找 2020 3 31 mayan 二叉树 二叉链表的类定义 BinTreeNode Copy BinTreeNode orignode 复制intHeight BinTreeNode subTree 返回树高度intSize BinTreeNode subTree 返回结点数BinTreeNode Parent BinTreeNode subTree BinTreeNode current 返回父结点BinTreeNode Find BinTreeNode subTree constT 前序遍历输出 2020 3 31 mayan 二叉树 二叉链表的类定义 voidpreOrder BinTreeNode 2020 3 31 mayan 二叉树 二叉链表的函数实现 私有函数 删除根为subTree的子树templatevoidBinaryTree destroy BinTreeNode subTree if subTree NULL destroy subTree leftChild 删除左子树destroy subTree rightChild 删除右子树deletesubTree 删除根结点 2020 3 31 mayan 二叉树 二叉链表的函数实现 从结点subTree开始 搜索结点current的双亲 若找到则返回双亲结点地址 否则返回NULLtemplateBinTreeNode BinaryTree Parent BinTreeNode subTree BinTreeNode current if subTree NULL returnNULL if subTree leftChild current subTree rightChild current returnsubTree 找到 返回父结点地址 2020 3 31 mayan 二叉树 二叉链表的函数实现 BinTreeNode p if p Parent subTree leftChild current NULL 递归在左子树中搜索returnp elsereturnParent subTree rightChild current 递归在右子树中搜索 2020 3 31 mayan 二叉树 二叉链表的函数实现 前序遍历输出templatevoidTraverse BinTreeNode subTree ostream 2020 3 31 mayan 二叉树 二叉链表的函数实现 输入并建立一棵二叉树Tree in是输入流对象 templateistream 2020 3 31 mayan 二叉树 二叉树的遍历 二叉树的遍历 BinaryTreeTraversal 就是按某种次序访问树中的结点 要求每个结点访问一次且仅访问一次 访问 的意思是对结点施行某些操作 令L R V分别代表遍历一个结点的左子树 右子树和访问该结点的操作 则可能有VLR LVR LRV VRL RVL RLV六种遍历二叉树的规则 若规定先左后右则有VLR 前序遍历 LVR 中序遍历 LRV 后序遍历 三种 2020 3 31 mayan 二叉树 二叉树的遍历 三种遍历算法 先序遍历 访问根结点 先序遍历左子树 先序遍历右子树 中序遍历 中序遍历左子树 访问根结点 中序遍历右子树 后序遍历 后序遍历左子树 后序遍历右子树 访问根结点 2020 3 31 mayan 二叉树 二叉树的遍历 二叉树中序遍历的递归算法templatevoidBinaryTree InOrder BinTreeNode subTree void visit BinTreeNode p if subTree NULL InOrder subTree leftChild visit 遍历左子树visit subTree 访问根结点InOrder subTree rightChild visit 遍历右子树 2020 3 31 mayan 二叉树 二叉树的遍历 二叉树前序遍历的递归算法templatevoidBinaryTree PreOrder BinTreeNode subTree void visit BinTreeNode p if subTree NULL visit subTree 访问根结点PreOrder subTree leftChild visit 遍历左子树PreOrder subTree rightChild visit 遍历右子树 2020 3 31 mayan 二叉树 二叉树的遍历 二叉树后序遍历的递归算法templatevoidBinaryTree PostOrder BinTreeNode subTree void visit BinTreeNode p if subTree NULL PostOrder subTree leftChild visit 遍历左子树PostOrder subTree rightChild visit 遍历右子树visit subTree 访问根结点 2020 3 31 mayan 二叉树 二叉树遍历的应用 利用二叉树后序遍历算法计算二叉树的结点个数templateintBinaryTree Size BinTreeNode subTree const if subTree NULL return0 空树elsereturn1 Size subTree leftChild Size subTree rightChild 2020 3 31 mayan 二叉树 二叉树遍历的应用 利用二叉树后序遍历算法计算二叉树的高度或深度templateintBinaryTree Height BinTreeNode subTree const if subTree NULL return0 空树高度为0else inti Height subTree leftChild intj Height subTree rightChild return i j j 1 i 1 2020 3 31 mayan 二叉树 以递归方式建立二叉树 私有函数 以递归方式建立二叉树 templatevoidBinaryTree CreateBinTree ifstream 建立根结点 2020 3 31 mayan 二叉树 以递归方式建立二叉树 if subTree NULL cerrleftChild 递归建立左子树CreateBinTree in subTree rightChild 递归建立右子树 elsesubTree NULL 封闭指向空子树的指针 2020 3 31 mayan 二叉树 二叉树遍历的非递归算法 利用栈的前序遍历非递归算法templatevoidBinaryTree PreOrder void visit BinTreeNode p stack S BinTreeNode p root S Push NULL 2020 3 31 mayan 二叉树 二叉树遍历的非递归算法 while p NULL visit p 访问结点if p rightChild NULL S Push p rightChild 预留右指针在栈中if p leftChild NULL p p leftChild 进左子树elseS Pop p 左子树为空 2020 3 31 mayan 二叉树 二叉树遍历的非递归算法 利用栈的中序遍历非递归算法templatevoidBinaryTree InOrder void visit BinTreeNode p stack S BinTreeNode p root 2020 3 31 mayan 二叉树 二叉树遍历的非递归算法 do while p NULL 遍历指针向左下移动S Push p 该子树沿途结点进栈p p leftChild if S IsEmpty 栈不空时退栈S Pop p visit p 退栈 访问p p rightChild 遍历指针进到右子女 while p NULL S IsEmpty 2020 3 31 mayan 二叉树 二叉树遍历的非递归算法 利用栈的后序遍历非递归算法templatestructstkNode BinTreeNode ptr 树结点指针enumtag L R 退栈标记stkNode BinTreeNode N NULL ptr N tag L 构造函数 tag L 表示从左子树退回还要遍历右子树 tag R 表示从右子树退回要访问根结点 2020 3 31 mayan 二叉树 二叉树遍历的非递归算法 templatevoidBinaryTree PostOrder void visit BinTreeNode p Stack S stkNodew BinTreeNode p root p是遍历指针do while p NULL w ptr p w tag L S Push w p p leftChild intcontinue1 1 继续循环标记 用于R 2020 3 31 mayan 二叉树 二叉树遍历的非递归算法 while continue1 2020 3 31 mayan 二叉树 二叉树遍历的非递归算法 层次序遍历算法templatevoidBinaryTree levelOrder void visit BinTreeNode t if root NULL return Queue Q BinTreeNode p root Q EnQueue p 2020 3 31 mayan 二叉树 二叉树遍历的非递归算法 while Q IsEmpty Q DeQueue p visit p if p leftChild NULL Q EnQueue p leftChild if p rightChild NULL Q EnQueue p rightChild 2020 3 31 mayan 二叉树 例1 给定一棵二叉树的先序序列EBADCFHGIKJ和中序序列ABCDEFGHIJK 画出这颗二叉树 2020 3 31 mayan 二叉树 例2 给定一棵二叉树的中序序列DCBGEAHFIJK和后序序列DCEGBFHKJIA 画出这颗二叉树 2020 3 31 mayan 二叉树 例3 给定一棵二叉树的先序和后序序列不能确定一棵二叉树 2020 3 31 mayan 线索二叉树 线索二叉树的概念 为什么提出线索二叉树 遍历的过程实质上是对一个非线性结构进行线性化的操作 使每个结点 除第一个和最后一个 在这个线性序列中有且仅有一个直接前驱和直接后继 二叉树种只存储了左右孩子的信息 因此 前驱和后继的信息无法直接找到 就提出了线索二叉树的概念 又因为n个结点的二叉链表中有n 1个空链域 从而得到线索二叉树的存储结构如下 2020 3 31 mayan 线索二叉树 线索二叉树的概念 规定 若结点有左子树 则leftChild指示其左孩子 否则令leftChild指示其前驱 若结点有右子树 则其rightChild域指示其右孩子 否则令rightChild指示其后继 为避免混淆 增加两个标志域 ltag为0 1 表示leftChild指向左孩子 前驱 rtag为0 1 表示rightChild指向右孩子 后继 2020 3 31 mayan 线索二叉树 线索二叉树的概念 其中 指向结点前驱和后继的指针叫做线索 加上线索的二叉树称为线索二叉树 对二叉树以某种次序遍历使其变为线索二叉树的过程叫线索化 2020 3 31 mayan 线索二叉树 线索二叉树的概念 2020 3 31 mayan 线索二叉树 中序线索化二叉树的类定义 templatestructThreadNode 线索二叉树的结点类intltag rtag 线索标志ThreadNode leftChild rightChild 线索或子女指针Tdata 结点数据ThreadNode constTitem 构造函数 data item leftChild NULL rightChild NULL ltag 0 rtag 0 2020 3 31 mayan 线索二叉树 中序线索化二叉树的类定义 templateclassThreadTree 线索化二叉树类protected ThreadNode root 树的根指针voidcreateInThread ThreadNode current ThreadNode 寻找结点t的双亲结点 2020 3 31 mayan 线索二叉树 中序线索化二叉树的类定义 public ThreadTree root NULL 构造函数voidcreateInThread 建立中序线索二叉树ThreadNode First ThreadNode current 寻找中序下第一个结点ThreadNode Last ThreadNode current 寻找中序下最后一个结点ThreadNode Next ThreadNode current 寻找结点在中序下的后继结点 2020 3 31 mayan 线索二叉树 中序线索化二叉树的类定义 ThreadNode Prior ThreadNode current 寻找结点在中序下的前驱结点voidInorder void visit ThreadNode p 中序遍历voidpreorder void visit ThreadNode p 前序遍历voidpostorder void visit ThreadNode p 后序遍历 2020 3 31 mayan 线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索 而前驱和后继的信息只有在遍历时才能得到 因此线索化的过程即为在遍历的过程中修改空指针的过程 线索二叉树 通过中序遍历建立中序线索化二叉树 2020 3 31 mayan 线索二叉树 通过中序遍历建立中序线索化二叉树 templatevoidThreadTree createInThread ThreadNode pre NULL 前驱结点指针if root NULL 非空二叉树 线索化createInThread root pre 中序遍历线索化二叉树pre rightChild NULL pre rtag 1 后处理中序最后一个结点 2020 3 31 mayan 线索二叉树 通过中序遍历建立中序线索化二叉树 通过中序遍历 对二叉树进行线索化templatevoidThreadTree createInThread ThreadNode current ThreadNode 2020 3 31 mayan 线索二叉树 通过中序遍历建立中序线索化二叉树 if pre NULL 递归 右子树线索化 2020 3 31 mayan 线索二叉树 寻找当前结点在中序下的后继 寻找当前结点在中序下的后继 2020 3 31 mayan 线索二叉树 寻找当前结点在中序下的后继 函数返回以 current为根的线索化二叉树中的中序序列下的第一个结点templateThreadNode ThreadTree First ThreadNode current ThreadNode p current while p ltag 0 p p leftChild returnp 2020 3 31 mayan 线索二叉树 寻找当前结点在中序下的后继 函数返回在线索化二叉树中结点 current在中序下的后继结点templateThreadNode ThreadTree Next ThreadNode current ThreadNode p current rightChild if current rtag 0 returnFirst p rtag 0 表示有右子女elsereturnp rtag 1 直接返回后继线索 2020 3 31 mayan 线索二叉树 寻找当前结点在中序下的前驱 寻找当前结点在中序下的前驱 2020 3 31 mayan 线索二叉树 中序线索化二叉树的中序遍历 templatevoidThreadTree Inorder void visit BinTreeNode p ThreadNode p for p First root p NULL p Next p visit p 2020 3 31 mayan 树与森林 树的存储表示 双亲表示法 父指针表示法 以一组连续的存储单元来存放树中的结点 每个结点有两个域 一个是data域 用来存放数据元素 一个是parent域 用来存放指示其父结点位置的指针 这种存储表示适合经常需要寻找父结点的应用 2020 3 31 mayan 树与森林 树的存储表示 孩子表示法 子女链表表示法 为树中每个结点设置一个子女链表 并将这些结点的数据和对应子女链表的头指针放在一个向量中 就构成了子女链表表示 这种存储表示适合需要频繁寻找子女的应用 无序树情形链表中各结点顺序任意 有序树必须自左向右链接各个子女结点 2020 3 31 mayan 树与森林 树的存储表示 孩子兄弟表示法 子女 兄弟链表表示法 子女 兄弟链表表示法也称为树的二叉树表示 他的每个结点的度为2 是最节省存储空间的树的存储表示 每个结点由三个域组成 firstChild指向该结点的第一个子女结点 无序树时 可任意指定一个结点为第一个子女 nextSibling指向该结点的下一个兄弟 任一结点在存储时总是有顺序的 2020 3 31 mayan 树与森林 树的存储表示 孩子兄弟表示法 子女 兄弟链表表示法 2020 3 31 mayan 树与森林 树的子女 兄弟表示的类定义 templatestructTreeNode 树的结点类Tdata 结点数据TreeNode firstChild nextSibling 子女及兄弟指针TreeNode Tvalue 0 TreeNode fc NULL TreeNode ns NULL 构造函数 data value firstChild fc nextSibling ns 2020 3 31 mayan 树与森林 树的子女 兄弟表示的类定义 templateclassTree 树类private TreeNode root current 根指针及当前指针intFind TreeNode p Tvalue 在以p为根的树中搜索valuevoidRemovesubTree TreeNode p 删除以p为根的子树boolFindParent TreeNode t TreeNode p public 2020 3 31 mayan 树与森林 树的子女 兄弟表示的类定义 Tree root current NULL 构造函数boolRoot 置根结点为当前结点boolIsEmpty returnroot NULL boolFirstChild 将当前结点的第一个子女置为当前结点boolNextSibling 将当前结点的下一个兄弟置为当前结点boolParent 将当前结点的双亲置为当前结点boolFind Ttarget 搜索含target的结点 使之成为当前结点 树的其他公共操作 2020 3 31 mayan 树与森林 子女 兄弟链表常用操作的实现 让树的根结点成为树的当前结点templateboolTree Root if root NULL current NULL returnfalse else current root returntrue 2020 3 31 mayan 树与森林 子女 兄弟链表常用操作的实现 置当前结点的双亲结点为当前结点templateboolTree Parent TreeNode p current if current NULL current root current NULL returnfalse 空树或根无双亲returnFindParent root p 从根开始找 p的双亲结点 2020 3 31 mayan 树与森林 子女 兄弟链表常用操作的实现 在根为 t的树中找 p的双亲 并置为当前结点templateboolTree FindParent TreeNode t TreeNode p TreeNode q t firstChild q是 t长子boolsucc 2020 3 31 mayan 树与森林 子女 兄弟链表常用操作的实现 while q NULL 未找到 2020 3 31 mayan 树与森林 子女 兄弟链表常用操作的实现 在树中找当前结点的长子 并置为当前结点templateboolTree FirstChild if current 2020 3 31 mayan 树与森林 子女 兄弟链表常用操作的实现 在树中找当前结点的兄弟 并置为当前结点templateboolTree NextSibling if current 2020 3 31 mayan 树与森林 子女 兄弟链表常用操作的实现 templateboolTree Find Ttarget if IsEmpty returnfalse returnFind root target templateboolTree Find TreeNode p Tvalue 2020 3 31 mayan 树与森林 子女 兄弟链表常用操作的实现 boolresult false if p data value result true current p else TreeNode q p firstChild while q NULL 2020 3 31 mayan 树与森林 森林与二叉树的转换 将一般树化为二叉树表示就是用树的子女 兄弟表示来存储树的结构 森林与二叉树表示的转换可以借助树的二叉树表示来实现 2020 3 31 mayan 树与森林 森林与二叉树的转换 森林转化成二叉树的规则若F为空 即n 0 则对应的二叉树B为空树 若F不空 则二叉树B的根是F第一棵树T1的根 其左子树为B T11 T12 T1m 其中 T11 T12 T1m是T1的根的子树 其右子树为B T2 T3 Tn 其中 T2 T3 Tn是除T1外其它树构成的森林 2020 3 31 mayan 树与森林 森林与二叉树的转换 二叉树转换为森林的规则如果B为空 则对应的森林F也为空 如果B非空 则F中第一棵树T1的根为B的根 T1的根的子树森林 T11 T12 T1m 是由B的根的左子树LB转换而来 F中除了T1之外其余的树组成的森林 T2 T3 Tn 是由B的根的右子树RB转换而成的森林 2020 3 31 mayan 树与森林 森林与二叉树的转换 2020 3 31 mayan 树与森林 树的遍历 深度优先遍历先根次序遍历 先访问树的根结点 然后先根遍历根的每棵子树 树的先根遍历结果与其对应二叉树表示的前序遍历结果相同 树的先根遍历可以借助对应二叉树的前序遍历算法实现 后根次序遍历 先依次后根遍历每棵子树 然后访问根结点 树的后根遍历结果与其对应二叉树表示的中序遍历结果相同 树的后根遍历可以借助对应二叉树的中序遍历算法实现 2020 3 31 mayan 树与森林 树的遍历 树的先根次序遍历的递归算法templatevoidTree PreOrder ostream 2020 3 31 mayan 树与森林 树的遍历 树的后根次序遍历的递归算法templatevoidTree PostOrder ostream 2020 3 31 mayan 树与森林 树的遍历 树的广度优先遍历树的广度优先遍历方法是分层进行访问的 templatevoidTree LevelOrder ostream 2020 3 31 mayan 树与森林 树的遍历 if p NULL 树不空Q EnQueue p 根结点进队列while Q IsEmpty Q DeQueue p 退出队列outdata for p p firstChild p NULL p p nextSibling Q EnQueue p 2020 3 31 mayan 树与森林 森林的遍历 森林的遍历也分为深度优先遍历和广度优先遍历 深度优先遍历又可分为先根次序遍历和后根次序遍历 深度优先遍历给定森林F 若F 则遍历结束 否则若F T1 r1 T11 T1k T2 Tm 则可以导出先根遍历 后根遍历两种方法 其中 r1是第一棵树的根结点 T11 T1k 是第一棵树的子树森林 T2 Tm 是除去第一棵树之后剩余的树构成的森林 2020 3 31 mayan 树与森林 森林的遍历 森林的先根次序遍历若森林F 返回 否则访问森林的根 也是第一棵树的根 r1 先根遍历森林第一棵树的根的子树森林 T11 T1k 先根遍历森林中除第一棵树外其他树组成的森林 T2 Tm 森林的后根次序遍历若森林F 返回 否则后根遍历森林F第一棵树的根结点的子树森林 T11 T1k 访问森林的根结点r1 后根遍历森林中除第一棵树外其他树组成的森林 T2 Tm 2020 3 31 mayan 树与森林 森林的遍历 森林的先根次序遍历和后根次序遍历分别对应为二叉树的前序遍历和中序遍历 广度优先遍历若森林F为空 返回 否则依次遍历各棵树的根结点 依次遍历各棵树根结点的所有子女 依次遍历这些子女结点的子女结点 2020 3 31 mayan 堆 最小堆和最大堆 堆的定义n个元素的序列 k1 k2 kn 当且仅当满足下列关系时 称之为堆 ki k2i且ki k2i 1或ki k2i且ki k2i 1其中 i 1 2 若将此序列对应的一维数组看成是一个完全二叉树 则堆的含义表明 完全二叉树中所有非终端结点的值均不大于 或不小于 其左 右孩子结点的值 2020 3 31 mayan 堆 最小堆和最大堆 堆的元素下标计算由于堆存储在下标从0开始计数的一维数组中 因此在堆中给定下标为i的结点时如果i 0 结点i是根结点 无双亲 否则结点i的父结点为结点 如果2i 1 n 1 则结点i无左子女 否则结点i的左子女为结点2i 1 如果2i 2 n 1 则结点i无右子女 否则结点i的右子女为结点2i 2 2020 3 31 mayan 堆 最小堆的类定义 templateclassMinHeap publicMinPQ 最小堆继承了 最小 优先级队列public MinHeap intsz DefaultSize 构造函数 建立空堆MinHeap Earr intn 构造函数 通过一个数组建堆 MinHeap delete heap 析构函数 2020 3 31 mayan 堆 最小堆的类定义 boolInsert constE 置空堆 2020 3 31 mayan 堆 最小堆的类定义 private E heap 最小堆元素存储数组intcurrentSize 最小堆当前元素个数intmaxHeapSize 最小堆最大容量voidsiftDown intstart intm 调整算法voidsiftUp intstart 调整算法 2020 3 31 mayan 堆 最小堆的建立 templateMinHeap MinHeap intsz DefaultSize maxHeapSize DefaultSize sz sz DefaultSize heap newE maxHeapSize 创建堆空间if heap NULL cerr 堆存储分配失败 endl exit 1 currentSize 0 建立当前大小 2020 3 31 mayan 堆 最小堆的建立 templateMinHeap MinHeap Earr intn maxHeapSize DefaultSize n n DefaultSize heap newE maxHeapSize if heap NULL cerr 堆存储分配失败 endl exit 1 for inti 0 i n i heap i arr i 2020 3 31 mayan 堆 最小堆的建立 currentSize n 复制堆数组 建立当前大小intcurrentPos currentSize 2 2 找最初调整位置 最后分支结点while currentPos 0 逐步向上扩大堆siftDown currentPos currentSize 1 局部自上向下下滑调整currentPos 2020 3 31 mayan 堆 最小堆的下滑调整算法 私有函数 从结点start开始到m为止 自上向下比较 如果子女的值小于父结点的值 则关键码小的上浮 继续向下层比较 将一个集合局部调整为最小堆 templatevoidMinHeap siftDown intstart intm inti start j 2 i 1 j是i的左子女位置Etemp heap i 2020 3 31 mayan 堆 最小堆的下滑调整算法 while jheap j 1 j 让j指向两子女中的小者if temp heap j break 小则不做调整else heap i heap j i j j 2 j 1 否则小者上移 i j下降 heap i temp 回放temp中暂存的元素 2020 3 31 mayan 堆 最小堆的下滑调整算法 2020 3 31 mayan 堆 最小堆的下滑调整算法 2020 3 31 mayan 堆 最小堆的下滑调整算法 2020 3 31 mayan 堆 最小堆的插入 每次插入都加在堆的最后 再自下向上执行调整 使之重新形成堆 时间复杂性O log2n 公共函数 将x插入到最小堆中templateboolMinHeap Insert constE 2020 3 31 mayan 堆 最小堆的插入 从结点start开始到结点0为止 自下向上比较 如果子女的值小于父结点的值 则相互交换 这样将集合重新调整为最小堆 关键码比较符voidMinHeap FilterUp intstart intj start i j 1 2 Etemp heap j while j 0 沿父结点路径向上直达根if heap i temp break 父结点值小 不调整else heap j heap i j i i i 1 2 heap j temp 回送 2020 3 31 mayan 堆 最小堆的插入 在堆中插入新元素11 2020 3 31 mayan 堆 最小堆的删除算法 templateboolMinHeap Remove E 返回最小元素 2020 3 31 mayan Huffman树 相关概念 路径长度 PathLength 两个结点之间的路径长度PL是连接两结点的路径上的分支数 树的外部路径长度是各叶结点 外结点 到根结点的路径长度之和EPL 树的内部路径长度是各非叶结点 内结点 到根结点的路径长度之和IPL 树的路径长度PL EPL IPL 2020 3 31 mayan Huffman树 相关概念 n个结点的二叉树的路径长度不小于下述数列前n项的和 即 2020 3 31 mayan Huffman树 相关概念 其路径长度最小者为完全二叉树或理想平衡树满足这个要求 带权路径长度 WeightedPathLength WPL 树的带权路径长度为树中所有叶子结点的带权路径长度之和 2020 3 31 mayan Huffman树 相关概念 2020 3 31 mayan Huffman树 相关概念 Huffman树假设有n个权值 w1 w2 wn 试构造一棵有n个叶子结点的二叉树 每个叶子结点带权为wi 则其中带权路径长度WPL最小的二叉树为最优二叉树 即Huffman树 2020 3 31 mayan Huffman树 Huffman树的构造算法 1 根据给定的n个权值 w1 w2 wn 构造n棵二叉树的集合F T1 T2 Tn 其中每棵二叉树Ti中只有