数据结构学位考2.ppt

数据结构学习考复习课 2 主要内容 第三部分 树 二叉树 森林 第六章树和二叉树 考核内容及要求 熟练掌握树的基本概念 熟练掌握二叉树的概念 性质熟练掌握二叉树的遍历方法 各种线索树 树与二叉树的转换 最优二叉树及HUFFUMAN编码 掌握各种树操作特性 性质 实现方法 1树的基本概念 性质 树 n个结点的有限集 在非空树中 有且仅有一个根结点 Root 当n 1时 其余结点可以分为m个 m 0 互不相交的有限集T1 T2 Tm 其中Ti为根的子树 树结构中的基本术语结点 一个数据元素及指向其子树的分支结点的度 结点拥有的子树数叶子结点 度为0的结点分支结点 度不为0的结点树的度 树内各结点的度的最大值孩子 结点的子树的根父亲 双亲 兄弟 同一父亲的孩子祖先 从根到该结点所经分支上的所有结点子孙 以某结点为根的子树中的任一结点层次 根为第一层 根的孩子为第二层 堂兄弟 双亲在同一层的结点互为堂兄弟深度 树中结点的最大层次有序树 将树的结点的各个子树都看成是有序的 则无序树森林 二叉树的定义每个结点至多有两棵子树 即度 2 子树有左右之分 二叉树的五种基本形态 2二叉树的概念 性质 二叉树的性质性质1在二叉树的第i层上至多有2i 1个结点 i 1 证明 归纳法i 1时 命题显然成立 2i 1 20 1假设所有的1 j i都成立 那么证明当j i时命题也成立 由假设知 第i 1层上的结点个数为2i 2 而在二叉树中第i层上结点的个数最多是上一层结点数的2倍 即为2 2i 2 2i 1 性质2深度为k的二叉树至多有2k 1个结点 k 1 证明 利用性质1的结论 性质3对任何一棵二叉树T 如果其终端结点数为n0 度为2的结点数为n2 则n0 n2 1 证明 设n1 度为1的结点数 n为结点总数 则n n0 n1 n2分析二叉树种的分叉数B n B 1B n1 2n2所以有n n1 2n2 1故 n0 n2 1 满二叉树 一棵深度为k且有2k 1个结点的二叉树完全二叉树 深度为k有n个结点的二叉树 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时 成为完全二叉树 性质4具有n个结点的完全二叉树的深度为 满二叉树 完全二叉树 非完全二叉树 性质5如果对一棵有n个结点的完全二叉树 其深度为层 每层从左到右 则对任一结点i 1 i n 有 1 如果i 1 则结点i是二叉树的根 无双亲 若i 1 则其双亲parent i 是结点 2 如果2i n 则结点i无左孩子 结点i为叶子结点 否则其左孩子LCHILD i 是结点2i 3 如果2i 1 n 则结点i无右孩子 否则其右孩子RCHILD i 是结点2i 1 顺序存储结构 defineMAX TREE SIZE100 TypedefTElemTypeSqBiTree MAX TREE SIZE SqBiTreebt 将完全二叉树上编号为i的结点元素存储在一维数组的下标为i 1的分量中 3二叉树的存储结构 链式存储结构 二叉链表 在含有n个结点的二叉链表中有n 1个空链域 二叉链表的定义 TypedefstructBiTNode TElemTypedata structBiTNode lchild rchild BiTNode BiTree 二叉树的基本操作 CreatBiTree BiTree 按先序顺序构造一棵二叉树PreOrderTraverse BiTreeT 先序遍历二叉树InOrderTraverse BiTreeT 中序遍历二叉树PostOrderTraverse BiTreeT 后序遍历二叉树LevelOrderTraverse BiTreeT 层次遍历二叉树 4遍历二叉树和线索二叉树 遍历二叉树 例 表达式 a b c d e f 的二叉树 先序遍历二叉树 a b cd ef 中序遍历二叉树 a b c d e f 后序遍历二叉树 abcd ef a a b b b a 遍历二叉树的过程 线索二叉树非线性结构的线性化操作增加两个指针 分别指向结点的前驱和后继利用二叉链表的n 1个空链域 bt 中序线索链表 在中序线索二叉树中找结点的后继叶子结点的后继 右链域指示非终端结点 其右子树的第一个结点中序线索二叉树中找结点的前驱 左标志域为1 左链域指示左标志域为0 左子树的最后一个结点 NIL NIL 中序线索二叉树 线索链表的存储结构typedefenumPointerTag Link Thread Link 0 指针 Thread 1 线索typedefstructBiThrNode TElemTypedata structBiThrNOde lchild rchild 左右孩子指针PointerTagLTag RTag 左右标志 BiThrNode BiThrTree 双向线索链表 添加头结点 lchild域指向二叉树的根结点 rchild域指向中序遍历时访问的最后结点 5树和森林 树的存储结构 双亲表示法 除根结点外的每个结点都只有唯一的双亲 树的双亲表存储表示 defineMAX TREE SIZE100 TypedefstructPTNode TElemTypedata intpatent PTNode Typedefstruct PTNodenodes MAX TREE SIZE intr n PTree 优点 parent T x Root x 操作容易实现确定 求结点的孩子时需要遍历整个结构 孩子表示法 D为树的度 结点同构 空间浪费 结点不同构 空间不浪费 操作不方便 适用于涉及孩子的操作 树的孩子链表存储表示TypedefstructCTNode 孩子结点intchild structCTNode next childptr Typedefstruct TElemTypedata childptrfirstchild 孩子链表头指针 CTBox Typedefstruct CTBoxnodes MAX TREE SIZE intn r 结点数和根的位置 CTree 带双亲的孩子链表 孩子表示法和双亲表示法结合起来 即带双亲的孩子链表 孩子兄弟表示法 以二叉链表表示两个链域 firstchild和nextsibling 第一个孩子结点和下一个兄弟结点 TypedefstructCSNode ElemTypedata StructCSNode firstchild nextsibling CSNode CSTree 森林与二叉树的转换 任何一棵与树对应的二叉树 其右子树都为空 森林与二叉树的对应关系 树与二叉树对应 森林与二叉树 树和森林的遍历树的遍历 先根遍历后根遍历森林的遍历 先序遍历森林中序遍历森林 1 中序遍历森林中的第一颗树的根结点的子树森林 2 访问第一颗树的根结点 3 中序遍历剩余的树构成的森林 6哈夫曼树及其应用 哈夫曼树 最优树 带权路径长度最短的树 最优二叉树 哈夫曼树 路径 从树中一个结点到另一个结点之间的分支构成两个结点之间的路径 路径长度 路径上的分支数目 树的路径长度 从树根到每一个结点的路径长度之和树的带权路径长度 其中 wk为k个结点的权值最优二叉树 哈夫曼树 带权路径长度WPL最小的二叉树 构造哈夫曼树的过程 哈夫曼算法 1 根据给定的n个权值 w1 w2 wn 构成n棵二叉树的集合F T1 T2 Tn 其中每棵二叉树Ti中只有一个带权为wi的根结点 其左右子树均空 2 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树 且置新的二叉树的根结点的权值为其左 右子树上根结点的权值之和 3 在F中删除这两棵树 同时将新得到的二叉树加入F中 4 重复 2 3 直到F只含一棵树为止 这颗树就是哈夫曼树 哈夫曼编码 编码A 0 B 10 C 110 D 111 哈夫曼树的特点 没有度为1的结点 称为严格的二叉树 哈夫曼树与哈夫曼编码的存储表示Typedefstruct unsignedintweight unsignedintparent lchild rchild HTNode HuffmanTree 动态分配数组存储哈夫曼树Typedefchar HuffmannCode 动态分配哈夫曼编码表 1234567 例如 构造哈夫曼树 求哈夫曼编码的算法voidHuffmanCoding HuffmanTree 从叶子到根逆向求每个字符的哈夫曼编码HC HuffmanCode malloc n 1 sizeof char cd char malloc n sizeof char cd n 1 0 for i 1 i n i start n 1 for c i f HT i parent f 0 c f f HT f parent if HT f lchild c cd start 0 elsecd start 1 Hc i chat malloc n start sizeof char atrcpy HC i HuffmanCoding 1234567 从根结点遍历哈夫曼树 求哈夫曼编码 1234567 算法 HC HuffmanCode malloc n 1 sizeof char P m cdlen 0 For i 1 i m i HT i weight 0 While p if HT p weight 0 HT p weight 1 if HT p lchild 0 p HT p lchild cd cdlen 0 elseif HT p rchild 0 HC p char malloc cdlen 1 sizeof char cd cdlen 0 atrcpy HC p cd elseif HT p weight 1 HT p weight 2 if HT p rchild 0 p HT p rchild cd cdlen 1 else HT p weight 0 p HT p parent cdlen while 6 2一个度为2的树与一棵二叉树有何区别 答 二叉树的度小于等于2 二叉树的子树有左右之分 而度为2的树的子树不一定是有序的 6 7一棵含有n个结点的k叉树 可能达到的最大深度和最小深度各是多少 答 最大n 最小 logkn 1 典型例题 证明 在含有n个结点的二叉链表中有n 1个空链域证明 除根结点均有分支引出 故有n 1个分支 占用n 1个子域 n个结点共有2n个子域 故空域共2n n 1 n 1个 6 10对于那些所有非叶子结点均有非空左右子树的二叉树 有n个叶子结点的树中共有多少个结点 性质3对任何一棵二叉树T 如果其终端结点数为n0 度为2的结点数为n2 则n0 n2 1 6 14找出满足下列条件的二叉树1 先序和中序遍历 得到的结点访问顺序一样 2 后序和中序遍历 得到的结点访问顺序一样 3 先序和后序遍历 得到的结点访问顺序一样 答 1 无左子树2 无右子树3 仅一个结点 6 17阅读下列算法 若有错 则改正 BiTreeInSucc BiTreeq 已知q是指向中序线索二叉树上某个结点的指针 本函数返回指向 q的后继结点指针r q rchild if r rtag while r rtag r r rchild returnr InSucc 6 19分别画出和下列树对应的各个二叉树6 22对于下列树分别求出以下遍历序列 1 先根序列 2 后根序列 A 6 21画出和下列二叉树对应的森林 a 原则 森林的先序 中序遍历 即对应二叉树的先序 中序遍历先做二叉树 cbefdg 6 24画出和下列已知序列对应的森林F 森林的先序次序访问序列为 ABCDEFGHIJKL森林的中序次序访问序列为 CBEFDGAJIKLH jiklh a jikl b efdg c h b h c d i a ef g j kl b h c d i a g j e f k l 二叉树 先ABCDEFGHIJKL中CBEFDGAJIKLH b h c d i g j e f k l a 森林 6 23画出和下列已知序列对应的树T树的先根次序访问序列为 GFKDAIEBCHJ树的后根次序访问序列为 DIAEKFCJHBG思路 树的先根为二叉树的先序树的后根为二叉树的中序求出二叉树然后化为树 6 42编写递归算法 计算二叉树中叶子结点的数目 StatusPreOrderTraverse BiTreeT ints s为叶子数目 初值为0if T if T lchild PreOrderTraverse 6 47编写按层次顺序 同一层自左至右 遍历二叉树的算法StatusLevelTraverse BiTreeT status visit TElemTypee InitQueue Q if T EnQueue Q T while QueueEmpty Q DeQueue Q e if visit e data returnERROR if e lchild EnQueue Q e lchild if e rchild EnQueue Q e rchild returnOK LevelTraverse 习题6 39假设在二叉链表中增设两个域 双亲域指示双亲结点 标志域 mark取值0 2 以区分在遍历过程中到达该结点时应该向左 向右或访问该结点 试以此存储结构编写不用栈的后序遍历算法 分析 每一个结点的mark初始化为0 Statusexercise 6 39 BiTreeT 后序遍历二叉树 二叉树的结点有五个域 data parent lchild rchild mark mark初始值为0P T while P swich p mark case0 p mark 1 if p lchild p p lchild break case1 p mark 2 if p rchild p p rchild break case2 p mark 0 visit P p p parent break default 6 62对一个以孩子兄弟链表表示的树 计算它的深度 队列中数据元素的类型定义TypedefstructQNode QElemtypedata intlay structQNode next Qnode QueuePtr 链队列的存储Typedefstruct QueuePtrfront QueuePtrrear LinkQueue TypedefstructCSNode ElemTypedata StructCSNode firstchild ne