数据结构学习分享试卷.ppt

人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * * 二叉树的存储（二） * * 二叉树链式存储结构 存储方式 一般从根结点开始存储，用二叉链表来表示。（相应地，访问树中结点时也只能从根开始） 二叉树结点的特点 二叉树是非线性结构，适合用链式存储结构 lchild data rchild 结点结构 data rchild lchild data parent lchild rchild 二叉树结点数据类型定义： typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; } BiTNode,*BiTree; 二叉树遍历 * * 若规定先左后右，则只有前三种情况： DLR —— 前（根）序遍历， LDR —— 中（根）序遍历， LRD —— 后（根）序遍历 根据遍历顺序确定一棵二叉树 已知二叉树的前序序列和中序序列，可以唯一确定一棵二叉树。 已知二叉树的后序序列和中序序列，可以唯一确定一棵二叉树。 已知二叉树的前序序列和后序序列，不能唯一确定一棵二叉树。 例题解析 * * 设二叉树bt的一种存储结构如下： 0 0 2 3 7 5 8 0 10 1 j h f d b a c e g i 0 0 0 9 4 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 lchild data rchild 其中bt为树根结点指针,lchild、rchild分别为结点的左、右孩子指针域,在这里使用结点编号作为指针域值,0表示指针域为空;data为结点的数据域。请完成下列各题： (1)画出二叉树的树形表示； (2)写出按先序、中序和后序遍历二叉树bt所得到的结点序列； 例题解析（续） * * 0 0 2 3 7 5 8 0 10 1 j h f d b a c e g i 0 0 0 9 4 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 lchild data rchild (1)画出二叉树的树形表示；因为第6号结点不是任何结点的孩子结点，该结点必定是根结点，再根据和结点左、右指针域的值很容易得到该二叉树的树形表示为 a b g f d c e h i j 例题解析（续） * * 0 0 2 3 7 5 8 0 10 1 j h f d b a c e g i 0 0 0 9 4 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 lchild data rchild a b g f d c e h i j (2)写出按先序、中序和后序遍历二叉树bt所得到的结点序列； a.先序序列 a b c e d f h g i j 例题解析（续） * * 0 0 2 3 7 5 8 0 10 1 j h f d b a c e g i 0 0 0 9 4 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 lchild data rchild a b g f d c e h i j (2)写出按先序、中序和后序遍历二叉树bt所得到的结点序列； a.先序序列 a b c e d f h g i j b.中序序列 e c b h f d j i g a 例题解析（续） * * 0 0 2 3 7 5 8 0 10 1 j h f d b a c e g i 0 0 0 9 4 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 lchild data rchild a b g f d c e h i j (2)写出按先序、中序和后序遍历二叉树bt所得到的结点序列； a.先序序列 a b c e d f h g i j b.中序序列 e c b h f d j i g a b.后序序列 e c h f j i g d b a 树与森林 【例题】从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。 答： 树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树惟一表示，并可使用二叉树的一些算法去解决树和森林中的问题。