c--数据结构课件(吴伟民-严蔚敏编著)

《c--数据结构课件(吴伟民-严蔚敏编著)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.完成第6章自测卷有关内容，算法设计题一定要写出思路。2.预习实验二：3个方案表示三种级别作业1第6章树和二叉树（Tree&BinaryTree）6.1树的基本概念6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5赫夫曼树及其应用2上堂课例题讨论问:设一棵完全二叉树具有1000个结点，则它有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。法1：先求全部叶子数。n0＝489(末层)＋11(k-1层)=500个；法2：先求2度结点数。n2=255(k-2层)＋2

2、44(k-1层)=499个；这两种方法的缺点：都要先计算树的深度k=log2n＋1=10;法3：无需求树深k，便可快捷求出完全二叉树的叶子数：n0=n/2//取大于n/2的最小整数值可由二叉树性质5轻松证明！(编号为i的结点，其孩子编号必为2i和2i+1)①②④⑧⑤⑨③?⑦……nn已知最后一个结点编号为n，则其双亲（n/2或(n-1)/2)肯定是最后一个非叶子结点。其编号之后的全部结点都是叶子了！故，n0=n-n/2或n-(n-1)/2=n/23问：用二叉链表法（l_child,r_ch

3、ild）存储包含n个结点的二叉树，结点的指针区域中必有个空指针。思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？所以，空指针个数＝2n－(n-1)=n+1个。n+1分析：①n个结点必有2n个链域；（见二叉链表数据类型说明）②除根结点外，二叉树中每一个结点有且仅有一个双亲（直接前驱），所以只会有n－1个结点的链域存放指针，指向非空子女结点（即直接后继）。4二、线索二叉树（ThreadedBinaryTree）普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在

4、遍历过程中获得。若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树了。两种解决方法：增加两个域：fwd和bwd；存放前驱指针存放后继指针如何预存这类信息？例如中序遍历结果：BDCEAFHG，实际上已将二叉树转为线性排列，显然具有唯一前驱和唯一后继。1.定义2.生成3.遍历利用空链域（n+1个空链域）5规定：1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱(即线索)；2）若结点有右子树，则rchild指向其右孩子；否则，rchil

5、d指向其直接后继(即线索)。为区别两种不同情况，特增加两个标志域（各1bit)lchilddatarchild约定:当Tag域为0时,表示正常情况;当Tag域为1时,表示线索情况.右孩子或后继左孩子或前驱LTagRTag6附：有关线索二叉树的几个术语：线索链表：用含Tag的结点样式所构成的二叉链表线索：指向结点前驱和后继的指针线索二叉树：加上线索的二叉树线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程讨论：增加了前驱和后继等线索有什么好处？——能方便找出当前结点的前驱和后继，不用堆栈也能遍历整

6、个树。7dataAGEIDJHCFBltag0011110101rtag0001010111AGEIDJHCFB例：某先序遍历结果如下表所示，请画出对应的二叉树。（多带了两个标志！）82.线索二叉树的生成线索化过程就是在遍历过程中修改空指针的过程：将空的lchild改为结点的直接前驱；将空的rchild改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为“正常情况”）9ABCGEIDHFroot悬空？悬空？解：该二叉树中序遍历结果为:H,D,I,B,E,A,F,C,G所以添加线索应当按如下路径进行

7、：为避免悬空态，应增设一个头结点例1：画出以下二叉树对应的中序线索二叉树。1000A00C00B11E11F11G00D11I11H注：此图中序遍历结果为:H,D,I,B,E,A,F,C,G0--root0对应的中序线索二叉树存储结构如图所示：11例2：【2000年计算机系考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。2825405560330854解:因为中序遍历序列是：5540256028083354对应线索树应当按此规律连线，即在原二叉树中添加虚线。NILNIL12线索二叉树的

8、生成算法（算法6.6,见教材P134）目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后继。注解：为方便添加结点的前驱或后继，需要设置两个指针：p指针→当前结点之指针；pre指针→前驱结点之指针。技巧：当结点p的左/右域为空时，只改写它的左域（装入前驱pre），而其右域（后继）留给下一结点来填写。或者说，当前结点的指针p应当送到前驱结点的空右域中。若p->lchild＝NULL,则{p->Ltag=1;p->lchild＝pre;}//p的前驱结点指针pre存入左