(数据结构)树和二叉树-严军勇.pptVIP

● 5.4　树、森林和二叉树的关系 A B C F G K D E H I J ^ A B ^ C D ^ E ^ F ^ H ^ ^ I ^ ^ G J ^ ^ K ^ root FirstChild RightSibling 树的孩子兄弟表示法 ● 5.4.1 树的存储结构 A B D E C A B E D C 　　从结点结构看出，当树用二叉链表表示时，树的结构已经转换成一棵二叉树，即给定一棵树，可以找到惟一的一棵二叉树与之对应。 结论 　　当一棵树用二叉链表表示时，可以用惟一对应的一棵二叉树表示，研究树的问题转化成了研究二叉树的问题，同时也为二叉树与树和森林的相互转换提供了依据。 A B A B C ●5.4.2　树、森林与二叉树的转换 　　二叉树与树、森林能够相互转换，是因为它们都可以用孩子兄弟表示法或称二叉链表表示法作为存储结构，从物理结构看，其二叉链表是相同的，只是解释不同而已。 ⒈ 树转换为二叉树 　　对于一棵无序树，树中结点的各孩子的次序无关，但二叉树中的结点的左、右孩子结点是有序的，故约定树中每个结点的孩子结点从左到右有序。 将一棵树转换为二叉树的方法： ⑴ 树中所有相邻兄弟加一条连线。 ⑵ 对树中的每个结点，只保留与第一个孩子结点间的连线，删去与其他孩子结点间的连线。 ⑶ 以树的根结点为轴心，将整棵树顺时针旋转，使之结构层次分明。 　　在二叉链表中虽然没有指向双亲结点的指针，但可以通过指向孩子结点的指针找到“双亲”，因此二叉链表中的信息是完备的。这和只有指向后继指针的单链表中隐含着“前驱”的信息是类似的。整个二叉树可以一个指向根结点的指针表示，如下列左图所示二叉树的二叉链表如下列右图所示。 D E F A B C A B ^ ^ C ^ D ^ E ^ ^ F ^ 头指针bt ● 5.2.3　二叉树的存储结构 　　基于二叉链表存储结构，建立二叉树 算法分析 　　 　　输入时，按完全二叉树形式，若是非完全二叉树，必须给定一些假想结点，使之符合完全二叉树形式，存在的结点输入对应字符，不存在的结点输入逗号，以“#”为输入结束符。 　　建成的二叉链表由根指针root惟一确定。 ● 5.2.3　二叉树的存储结构 D A B C D A B C 增加虚结点假想为完全二叉树 非完全二叉树 从键盘输入数据为：AB,,C,,,,D# ● 5.2.3　二叉树的存储结构 ^ A B ^ ^ Ｃ ^ Ｄ ^ 头指针root 建立的二叉链表 ● 5.2.3　二叉树的存储结构 　　在以前各章的类型定义中都有“遍历”的基本操作，但从来没有专门提出来讨论过。而从另一方面看，很多操作是在遍历过程中进行的，如，在线性表中查询某个特定的数据元素，求链表的长度等等。这是因为线性结构是一个“序列”，每个数据元素只有一个后继，因此它的遍历只有一条有哪些信誉好的足球投注网站路径，即从第一个数据元素起，顺着“后继”直到最后一个数据元素止。　　而非线性结构中每个数据元素可以有多个后继，为保证遍历成功就需要确定合适的有哪些信誉好的足球投注网站路径 ● 5.2.4　二叉树的遍历 　　从数据类型的定义得知，“遍历”的含义是对结构中的每个数据元素都访问一次且仅仅访问一次。因此进行遍历应该确定一条有哪些信誉好的足球投注网站路径，使得结构中的每个数据元素都出现在这条有哪些信誉好的足球投注网站路径上，才能确保每个数据元素都被访问到。　　由于二叉树中每个结点都有两个后继，则可以有三条有哪些信誉好的足球投注网站路径：　　⑴ 先左(子树)后右(子树)；　　⑵ 先右(子树)后左(子树)；　　⑶ 按层次从上到下。 　　按层次从上到下的遍历比较简单，先访问第一层的结点(即根结点)，再访问第二层，第三层，…，直到最后一层，对每一层的结点则从左到右，即“先被访问的父结点的孩子结点”先于“后被访问的父结点的孩子结点”进行访问。 ● 5.2.4　二叉树的遍历 　　从二叉树的结构定义得知，二叉树是由“根结点”、“左子树”和“右子树”三部分构成，则遍历二叉树的操作可分解为“访问根结点”、“遍历左子树”和“遍历右子树”三个子操作，并且由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历二叉树一样“递归”进行。因此整个遍历的操作只要在一条有哪些信誉好的足球投注网站路径上一次完成这三个子操作即可。 　　第一次走到根结点即“访问”为“先序遍历”，从左子树回来再“访问”为“中序遍历”，从右子树回来再 “访问”为“后序遍历”。 ● 5.2.4　二叉树的遍历 　　对二叉树进行遍历的先左后右的有哪些信誉好的足球投注网站路径,可得到两个结论： 　⑴ 由于左右子树互不相交，因此对左子树的遍历一定不会访问到右子树上的结点，反之对右子树的遍历也一定不会访问到左子树，因此沿这条有哪些信誉好的足球投注网站路径必可实现对二叉树中每个结点都访问到且只访问一次； 　⑵也正由于左右子树不相交，因此在遍历了左子树之后必须回到根结点才能继续遍历右子树。由此可见，在这条有哪些信誉好的足球投注网站路径上从进入二