c#与数据构.docxVIP

HYPERLINK /abatei/archive/2008/05/23/1205707.html C#与数据结构--二叉树的遍历 ? 6.2.2 二叉树的存储结构 二叉树的存储可分为两种：顺序存储结构和链式存储结构。 1.????? 顺序存储结构 把一个满二叉树自上而下、从左到右顺序编号，依次存放在数组内，可得到图6.8(a)所示的结果。设满二叉树结点在数组中的索引号为i，那么有如下性质。 （1） 如果i = 0，此结点为根结点，无双亲。 （2） 如果i 0，则其双亲结点为(i -1) / 2 。（注意，这里的除法是整除，结果中的小数部分会被舍弃。） （3） 结点i的左孩子为2i + 1，右孩子为2i + 2。 （4） 如果i 0，当i为奇数时，它是双亲结点的左孩子，它的兄弟为i + 1；当i为偶数时，它是双新结点的右孩子，它的兄弟结点为i – 1。 （5） 深度为k的满二叉树需要长度为2 k-1的数组进行存储。 通过以上性质可知，使用数组存放满二叉树的各结点非常方便，可以根据一个结点的索引号很容易地推算出它的双亲、孩子、兄弟等结点的编号，从而对这些结点进行访问，这是一种存储二叉满二叉树或完全二叉树的最简单、最省空间的做法。 为了用结点在数组中的位置反映出结点之间的逻辑关系，存储一般二叉树时，只需要将数组中空结点所对应的位置设为空即可，其效果如图6.8(b)所示。这会造成一定的空间浪费，但如果空结点的数量不是很多，这些浪费可以忽略。 一个深度为k的二叉树需要2 k-1个存储空间，当k值很大并且二叉树的空结点很多时，最坏的情况是每层只有一个结点，再使用顺序存储结构来存储显然会造成极大地浪费，这时就应该使用链式存储结构来存储二叉树中的数据。  ? 1.????? 链式存储结构 二叉树的链式存储结构可分为二叉链表和三叉链表。二叉链表中，每个结点除了存储本身的数据外，还应该设置两个指针域left和right，它们分别指向左孩子和右孩子（如图6.9(a)所示）。 当需要在二叉树中经常寻找某结点的双亲，每个结点还可以加一个指向双亲的指针域parent，如图6.9(b)所示，这就是三叉链表。 ? 图6.10所示的是二叉链表和三叉链表的存储结构，其中虚线箭头表示parent指针所指方向。 ? 二叉树还有一种叫双亲链表的存储结构，它只存储结点的双亲信息而不存储孩子信息，由于二叉树是一种有序树，一个结点的两个孩子有左右之分，因此结点中除了存放双新信息外，还必须指明这个结点是左孩子还是右孩子。由于结点不存放孩子信息，无法通过头指针出发遍历所有结点，因此需要借助数组来存放结点信息。图6.10(a)所示的二叉树使用双亲链表进行存储将得到图6.11所示的结果。由于根节点没有双新，所以它的parent指针的值设为-1。 ? 双亲链表中元素存放的顺序是根据结点的添加顺序来决定的，也就是说把各个元素的存放位置进行调换不会影响结点的逻辑结构。由图6.11可知，双亲链表在物理上是一种顺序存储结构。 二叉树存在多种存储结构，选用何种方法进行存储主要依赖于对二叉树进行什么操作来确定。而二叉链表是二叉树最常用的存储结构，下面几节给出的有关二叉树的算法大多基于二叉链表存储结构。 6.3 二叉树的遍历 二叉树遍历（Traversal）就是按某种顺序对树中每个结点访问且只能访问一次的过程。访问的含义很广，如查询、计算、修改、输出结点的值。树遍历本质上是将非线性结构线性化，它是二叉树各种运算和操作的实现基础，需要高度重视。 6.3.1 二叉树的深度优先遍历 图6.12二叉树的递归定义 D L R 我们是用递归的方法来定义二叉树的。每棵二叉树由结点、左子树、右子树这三个基本部分组成，如果遍历了这三部分，也就遍历了整个二叉树。如图6.12所示，D为二叉树中某一结点，L、R分别为结点D的左、右子树，则其遍历方式有6种：? ??????? 先左后右 先右后左 先序 DLR DRL 中序 LDR RDL 后序 LRD RLD 这里只讨论先左后右的三种遍历算法。? 如图6.13所示，在沿着箭头方向所指的路径对二叉树进行遍历时，每个节点会在这条有哪些信誉好的足球投注网站路径上会出现三次，而访问操作只能进行一次，这时就需要决定在有哪些信誉好的足球投注网站路径上第几次出现的结点进行访问操作，由此就引出了三种不同的遍历算法。 ? 1.????? 先序遍历 若二叉树为非空，则过程为： （1） 访问根节点。 （2） 先序遍历左子树。 （3） 先序遍历右子树。 图6.13中，先序遍历就是把标号为(1)的结点按有哪些信誉好的足球投注网站路径访问的先后次序连接起来，得出结果为：ABDECF。 2.????? 中序遍历 若二叉树为非空，则过程