c#

C#与数据结构--二叉树的遍历 ,来源网上收集

</SPAN></SPAN></SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">结点</SPAN><SPAN 
lang=EN-US>i</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">的左孩子为</SPAN><SPAN 
lang=EN-US>2i + 1</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，右孩子为</SPAN><SPAN 
lang=EN-US>2i + 2</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">。</SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 54pt; TEXT-INDENT: -27pt; mso-list: l0 level2 lfo1; tab-stops: list 54.0pt"><SPAN 
lang=EN-US style="mso-bidi-font-family: 宋体"><SPAN 
style="mso-list: Ignore">（4）<SPAN style="FONT: 7pt 'Times New Roman'"> 
</SPAN></SPAN></SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">如果</SPAN><SPAN 
lang=EN-US>i &gt; 0</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，当</SPAN><SPAN 
lang=EN-US>i</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">为奇数时，它是双亲结点的左孩子，它的兄弟为</SPAN><SPAN 
lang=EN-US>i + 1</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">；当</SPAN><SPAN 
lang=EN-US>i</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">为偶数时，它是双新结点的右孩子，它的兄弟结点为</SPAN><SPAN 
lang=EN-US>i – 1</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">。</SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 54pt; TEXT-INDENT: -27pt; mso-list: l0 level2 lfo1; tab-stops: list 54.0pt"><SPAN 
lang=EN-US style="mso-bidi-font-family: 宋体"><SPAN 
style="mso-list: Ignore">（5）<SPAN style="FONT: 7pt 'Times New Roman'"> 
</SPAN></SPAN></SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">深度为</SPAN><SPAN 
lang=EN-US>k</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">的满二叉树需要长度为</SPAN><SPAN 
lang=EN-US>2</SPAN><SUP><SPAN lang=EN-US style="mso-bidi-font-size: 10.5pt"> 
k-1</SPAN></SUP><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt">的数组进行存储。</SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; mso-char-indent-count: 2.0"><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">通过以上性质可知，使用数组存放满二叉树的各结点非常方便，可以根据一个结点的索引号很容易地推算出它的双亲、孩子、兄弟等结点的编号，从而对这些结点进行访问，这是一种存储二叉满二叉树或完全二叉树的最简单、最省空间的做法。</SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; mso-char-indent-count: 2.0"><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">为了用结点在数组中的位置反映出结点之间的逻辑关系，存储一般二叉树时，只需要将数组中空结点所对应的位置设为空即可，其效果如图</SPAN><SPAN 
lang=EN-US>6.8(b)</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">所示。这会造成一定的空间浪费，但如果空结点的数量不是很多，这些浪费可以忽略。</SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; mso-char-indent-count: 2.0"><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">一个深度为</SPAN><SPAN 
lang=EN-US>k</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">的二叉树需要</SPAN><SPAN 
lang=EN-US>2</SPAN><SUP><SPAN lang=EN-US style="mso-bidi-font-size: 10.5pt"> 
k-1</SPAN></SUP><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt">个存储空间，当</SPAN><SPAN 
lang=EN-US style="mso-bidi-font-size: 10.5pt">k</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt">值很大并且二叉树的空结点很多时，最坏的情况是每层只有一个结点，再使用顺序存储结构来存储显然会造成极大地浪费，这时就应该使用链式存储结构来存储二叉树中的数据。</SPAN></P>
<P><BR><BR><IMG alt="" src="C#与数据结构--二叉树的遍历 - abatei - 博客园.files/6-8.jpg" 
border=0></P>
<P> </P>
<P class=MsoNormal 
style="MARGIN-LEFT: 42pt; TEXT-INDENT: -21pt; mso-list: l0 level1 lfo1; tab-stops: list 42.0pt"><STRONG 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-FAMILY: 楷体_GB2312; mso-hansi-font-family: 华文楷体; mso-bidi-font-family: 楷体_GB2312"><SPAN 
style="mso-list: Ignore">1.<SPAN 
style="FONT: 7pt 'Times New Roman'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
</SPAN></SPAN></SPAN></STRONG><STRONG style="mso-bidi-font-weight: normal"><SPAN 
style="FONT-FAMILY: 楷体_GB2312; mso-hansi-font-family: 华文楷体">链式存储结构<SPAN 
lang=EN-US><O:P></O:P></SPAN></SPAN></STRONG></P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; mso-char-indent-count: 2.0"><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">二叉树的链式存储结构可分为二叉链表和三叉链表。二叉链表中，每个结点除了存储本身的数据外，还应该设置两个指针域</SPAN><SPAN 
lang=EN-US>left</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">和</SPAN><SPAN 
lang=EN-US>right</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，它们分别指向左孩子和右孩子（如图</SPAN><SPAN 
lang=EN-US>6.9(a)</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">所示）。</SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; mso-char-indent-count: 2.0"><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">当需要在二叉树中经常寻找某结点的双亲，每个结点还可以加一个指向双亲的指针域</SPAN><SPAN 
lang=EN-US>parent</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，如图</SPAN><SPAN 
lang=EN-US>6.9(b)</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">所示，这就是三叉链表。</SPAN></P><BR><IMG 
alt="" src="C#与数据结构--二叉树的遍历 - abatei - 博客园.files/6-9.jpg" border=0><BR>&nbsp; 
<P class=MsoNormal style="TEXT-INDENT: 21pt; mso-char-indent-count: 2.0"><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">图</SPAN><SPAN 
lang=EN-US>6.10</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">所示的是二叉链表和三叉链表的存储结构，其中虚线箭头表示</SPAN><SPAN 
lang=EN-US>parent</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">指针所指方向。</SPAN></P><BR><IMG 
alt="" src="C#与数据结构--二叉树的遍历 - abatei - 博客园.files/6-10.jpg" border=0><BR>&nbsp; 
<P class=MsoNormal style="TEXT-INDENT: 21pt; mso-char-indent-count: 2.0"><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">二叉树还有一种叫双亲链表的存储结构，它只存储结点的双亲信息而不存储孩子信息，由于二叉树是一种有序树，一个结点的两个孩子有左右之分，因此结点中除了存放双新信息外，还必须指明这个结点是左孩子还是右孩子。由于结点不存放孩子信息，无法通过头指针出发遍历所有结点，因此需要借助数组来存放结点信息。图</SPAN><SPAN 
lang=EN-US>6.10(a)</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">所示的二叉树使用双亲链表进行存储将得到图</SPAN><SPAN 
lang=EN-US>6.11</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">所示的结果。由于根节点没有双新，所以它的</SPAN><SPAN 
lang=EN-US>parent</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">指针的值设为</SPAN><SPAN 
lang=EN-US>-1</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">。</SPAN></P><BR><IMG 
alt="" src="C#与数据结构--二叉树的遍历 - abatei - 博客园.files/6-11.jpg" border=0><BR>&nbsp; 
<P class=MsoNormal style="TEXT-INDENT: 21pt; mso-char-indent-count: 2.0"><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">双亲链表中元素存放的顺序是根据结点的添加顺序来决定的，也就是说把各个元素的存放位置进行调换不会影响结点的逻辑结构。由图</SPAN><SPAN 
lang=EN-US>6.11</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">可知，双亲链表在物理上是一种顺序存储结构。</SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; mso-char-indent-count: 2.0"><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">二叉树存在多种存储结构，选用何种方法进行存储主要依赖于对二叉树进行什么操作来确定。而二叉链表是二叉树最常用的存储结构，下面几节给出的有关二叉树的算法大多基于二叉链表存储结构。</SPAN></P>
<H2><SPAN lang=EN-US>6.3 </SPAN><SPAN 
style="FONT-FAMILY: 黑体; mso-ascii-font-family: Arial">二叉树的遍历</SPAN></H2>
<P class=MsoNormal style="TEXT-INDENT: 21pt; mso-char-indent-count: 2.0"><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">二叉树遍历（</SPAN><SPAN 
lang=EN-US>Traversal</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">）就是按某种顺序对树中每个结点访问且只能访问一次的过程。访问的含义很广，如查询、计算、修改、输出结点的值。树遍历本质上是将非线性结构线性化，它是二叉树各种运算和操作的实现基础，需要高度重视。</SPAN></P>
<H3><SPAN lang=EN-US>6.3.1<SPAN style="mso-spacerun: yes">&nbsp; 
</SPAN></SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">二叉树的深度优先遍历</SPAN></H3>
<P class=MsoNormal 
style="TEXT-INDENT: 21pt; mso-char-indent-count: 2.0"><V:GROUP id=_x0000_s1026 
style="MARGIN-TOP: 20.8pt; Z-INDEX: -1; LEFT: 0px; MARGIN-LEFT: 351pt; WIDTH: 129pt; POSITION: absolute; HEIGHT: 93.6pt; TEXT-ALIGN: left" 
coordsize="2580,1872" coordorigin="4374,6976" editas="canvas"><O:LOCK 
aspectratio="t" v:ext="edit"></O:LOCK><V:SHAPETYPE id=_x0000_t75 
coordsize="21600,21600" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" 
o:preferrelative="t" o:spt="75"><V:STROKE 
joinstyle="miter"></V:STROKE><V:FORMULAS><V:F 
eqn="if lineDrawn pixelLineWidth 0"></V:F><V:F eqn="sum @0 1 0"></V:F><V:F 
eqn="sum 0 0 @1"></V:F><V:F eqn="prod @2 1 2"></V:F><V:F 
eqn="prod @3 21600 pixelWidth"></V:F><V:F 
eqn="prod @3 21600 pixelHeight"></V:F><V:F eqn="sum @0 0 1"></V:F><V:F 
eqn="prod @6 1 2"></V:F><V:F eqn="prod @7 21600 pixelWidth"></V:F><V:F 
eqn="sum @8 21600 0"></V:F><V:F eqn="prod @7 21600 pixelHeight"></V:F><V:F 
eqn="sum @10 21600 0"></V:F></V:FORMULAS><V:PATH o:connecttype="rect" 
gradientshapeok="t" o:extrusionok="f"></V:PATH><O:LOCK aspectratio="t" 
v:ext="edit"></O:LOCK></V:SHAPETYPE><V:SHAPE id=_x0000_s1027 
style="LEFT: 4374px; WIDTH: 2580px; POSITION: absolute; TOP: 6976px; HEIGHT: 1872px" 
o:preferrelative="f" type="#_x0000_t75"><V:FILL 
o:detectmouseclick="t"></V:FILL><V:PATH o:connecttype="none" 
o:extrusionok="t"></V:PATH><O:LOCK v:ext="edit" 
text="t"></O:LOCK></V:SHAPE><V:SHAPETYPE id=_x0000_t202 coordsize="21600,21600" 
path="m,l,21600r21600,l21600,xe" o:spt="202"><V:STROKE 
joinstyle="miter"></V:STROKE><V:PATH o:connecttype="rect" 
gradientshapeok="t"></V:PATH></V:SHAPETYPE><V:SHAPE id=_x0000_s1028 
style="LEFT: 4554px; WIDTH: 2220px; POSITION: absolute; TOP: 8380px; HEIGHT: 312px" 
stroked="f" type="#_x0000_t202"><V:TEXTBOX 
style="mso-next-textbox: #_x0000_s1028" inset="0,0,0,0">
<TABLE cellSpacing=0 cellPadding=0 width="100%">
  <TBODY>
  <TR>
    <TD>
      <DIV>
      <P class=MsoNormal style="TEXT-ALIGN: center" align=center><SPAN 
      style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">图</SPAN><SPAN 
      lang=EN-US style="FONT-SIZE: 9pt">6.12</SPAN><SPAN 
      style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">二叉树的递归定义</SPAN><SPAN 
      lang=EN-US 
  style="FONT-SIZE: 9pt"><O:P></O:P></SPAN></P></DIV></TD></TR></TBODY></TABLE></V:TEXTBOX></V:SHAPE><V:GROUP 
id=_x0000_s1029 
style="LEFT: 5139px; WIDTH: 1038px; POSITION: absolute; TOP: 7132px; HEIGHT: 1032px" 
coordsize="1038,1032" coordorigin="2214,7600"><V:OVAL id=_x0000_s1030 
style="LEFT: 2529px; WIDTH: 408px; POSITION: absolute; TOP: 7600px; HEIGHT: 408px"><V:TEXTBOX 
style="mso-next-textbox: #_x0000_s1030" inset="1.8mm,0,0,0">
<TABLE cellSpacing=0 cellPadding=0 width="100%">
  <TBODY>
  <TR>
    <TD>
      <DIV>
      <P class=MsoNormal><SPAN lang=EN-US 
      style="FONT-SIZE: 9pt">D<O:P></O:P></SPAN></P></DIV></TD></TR></TBODY></TABLE></V:TEXTBOX></V:OVAL><V:OVAL 
id=_x0000_s1031 
style="LEFT: 2214px; WIDTH: 408px; POSITION: absolute; TOP: 8224px; HEIGHT: 408px"><V:TEXTBOX 
style="mso-next-textbox: #_x0000_s1031" inset="1.8mm,0,0,0">
<TABLE cellSpacing=0 cellPadding=0 width="100%">
  <TBODY>
  <TR>
    <TD>
      <DIV>
      <P class=MsoNormal><SPAN lang=EN-US 
      style="FONT-SIZE: 9pt">L<O:P></O:P></SPAN></P></DIV></TD></TR></TBODY></TABLE></V:TEXTBOX></V:OVAL><V:OVAL 
id=_x0000_s1032 
style="LEFT: 2844px; WIDTH: 408px; POSITION: absolute; TOP: 8224px; HEIGHT: 408px"><V:TEXTBOX 
style="mso-next-textbox: #_x0000_s1032" inset="1.8mm,0,0,0">
<TABLE cellSpacing=0 cellPadding=0 width="100%">
  <TBODY>
  <TR>
    <TD>
      <DIV>
      <P class=MsoNormal><SPAN lang=EN-US 
      style="FONT-SIZE: 9pt">R<O:P></O:P></SPAN></P></DIV></TD></TR></TBODY></TABLE></V:TEXTBOX></V:OVAL><V:LINE 
id=_x0000_s1033 style="POSITION: absolute; flip: x" to="2685,8247" 
from="2505,8009"></V:LINE><V:LINE id=_x0000_s1034 style="POSITION: absolute" 
to="2953,8240" from="2773,8002"></V:LINE></V:GROUP><W:WRAP 
type="square"></W:WRAP></V:GROUP><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">我们是用递归的方法来定义二叉树的。每棵二叉树由结点、左子树、右子树这三个基本部分组成，如果遍历了这三部分，也就遍历了整个二叉树。如图</SPAN><SPAN 
lang=EN-US>6.12</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">所示，</SPAN><SPAN 
lang=EN-US>D</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">为二叉树中某一结点，</SPAN><SPAN 
lang=EN-US>L</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">、</SPAN><SPAN 
lang=EN-US>R</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">分别为结点</SPAN><SPAN 
lang=EN-US>D</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">的左、右子树，则其遍历方式有</SPAN><SPAN