第6章 树和二叉树.ppt

**************************不同的定义方法相应有不同的存储结构的建立算法**不同的定义方法相应有不同的存储结构的建立算法****上页算法执行过程举例****************我们先观察一下后序遍历的过程，发现规律：先访问根，先序遍历右子树，先序遍历左子树，即为后序遍历的逆序********************************************遍历是任何类型均有的操作********************观察中序遍历过程*****************************************/**********************树是一类重要的非线性数据结构，是以分支关系定义的层次结构**二维数组中共有m?n个元素，每个元素同时处于行和列的两个关系中，它既在行关系ROW中是(i0)的后继，又在列关系COL中是(j0)的后继。******这个公式可以推广到n维数组**这个公式可以推广到n维数组********二叉树不是树的特例，因为二叉树是有序树，而树不是有序的。即二叉树不是度数为2的树。二叉树的抽象数据类型由学生自己看。**二叉树不是树的特例，因为二叉树是有序树，而树不是有序的。即二叉树不是度数为2的树。二叉树的抽象数据类型由学生自己看。**二叉树不是树的特例，因为二叉树是有序树，而树不是有序的。即二叉树不是度数为2的树。二叉树的抽象数据类型由学生自己看。********由性质5可知结点间关系****除根结点，每个结点只有一个指针指向它，所以n个结点只用了n-1个指针，而n个结点有2n个指针域，所以有2n-(n-1)=n+1个空指针域缺点：找双亲难，引出三叉链表**除根结点，每个结点只有一个指针指向它，所以n个结点只用了n-1个指针，而n个结点有2n个指针域，所以有2n-(n-1)=n+1个空指针域缺点：找双亲难，引出三叉链表*****/树和森林的遍历树的遍历ABCDEFGHIJK层次遍历时顶点的访问次序先根遍历时顶点的访问次序ABEFCDGHIJK后根遍历时顶点的访问次序EFBCIJKHGDAABCDEFGHIJK转换二叉树的先序遍历转换二叉树的中序遍历*/（1）森林中第一棵树的根结点；（2）森林中第一棵树的子树森林；（3）森林中其它树构成的森林。可以分解成三部分森林树和森林的遍历森林的遍历BCDEFGHIJK*/树和森林森林与二叉树的转换森林的遍历先根(次序)遍历若森林不空，则访问森林中第一棵树的根结点先序遍历森林中第一棵树的子树森林;先序遍历森林中(除第一棵树之外)其余树构成的森林。即：依次从左至右对森林中的每一棵树进行先根遍历。*/树和森林森林与二叉树的转换森林的遍历中根(次序)遍历若森林不空，则中序遍历森林中第一棵树的子树森林;访问森林中第一棵树的根结点;中序遍历森林中(除第一棵树之外)其余树构成的森林即：依次从左至右对森林中的每一棵树进行后根遍历。*/树和森林森林与二叉树的转换树的遍历和二叉树遍历的对应关系？