二叉树中的三种遍历方式

╰半橙微兮° 2022-08-08 12:57 148阅读 0赞

对于二叉树:

[![20130507202022904][]][20130507202022904]

的几种遍历方式

1、先序遍历：先序遍历是先输出根节点，再输出左子树，最后输出右子树。上图的先序遍历结果就是：ABCDEF

2、中序遍历：中序遍历是先输出左子树，再输出根节点，最后输出右子树。上图的中序遍历结果就是：CBDAEF

3、后序遍历：后序遍历是先输出左子树，再输出右子树，最后输出根节点。上图的后序遍历结果就是：CDBFEA

<table style=""> 
 <tbody style=""> 
  <tr style=""> 
   <td style=""> 
    <div style="">
      1 
    </div> 
    <div style="">
      2 
    </div> 
    <div style="">
      3 
    </div> 
    <div style="">
      4 
    </div> 
    <div style="">
      5 
    </div> 
    <div style="">
      6 
    </div> 
    <div style="">
      7 
    </div> 
    <div style="">
      8 
    </div> 
    <div style="">
      9 
    </div> 
    <div style="">
      10 
    </div> 
    <div style="">
      11 
    </div> 
    <div style="">
      12 
    </div> 
    <div style="">
      13 
    </div> 
    <div style="">
      14 
    </div> 
    <div style="">
      15 
    </div> 
    <div style="">
      16 
    </div> 
    <div style="">
      17 
    </div> 
    <div style="">
      18 
    </div> 
    <div style="">
      19 
    </div> 
    <div style="">
      20 
    </div> 
    <div style="">
      21 
    </div> 
    <div style="">
      22 
    </div> 
    <div style="">
      23 
    </div> 
    <div style="">
      24 
    </div> 
    <div style="">
      25 
    </div> 
    <div style="">
      26 
    </div> 
    <div style="">
      27 
    </div> 
    <div style="">
      28 
    </div> 
    <div style="">
      29 
    </div> 
    <div style="">
      30 
    </div> 
    <div style="">
      31 
    </div> 
    <div style="">
      32 
    </div> 
    <div style="">
      33 
    </div> 
    <div style="">
      34 
    </div> 
    <div style="">
      35 
    </div> 
    <div style="">
      36 
    </div> 
    <div style="">
      37 
    </div> 
    <div style="">
      38 
    </div> 
    <div style="">
      39 
    </div> 
    <div style="">
      40 
    </div> 
    <div style="">
      41 
    </div> 
    <div style="">
      42 
    </div> 
    <div style="">
      43 
    </div> 
    <div style="">
      44 
    </div> 
    <div style="">
      45 
    </div> 
    <div style="">
      46 
    </div> 
    <div style="">
      47 
    </div> 
    <div style="">
      48 
    </div> 
    <div style="">
      49 
    </div> 
    <div style="">
      50 
    </div> 
    <div style="">
      51 
    </div> 
    <div style="">
      52 
    </div> 
    <div style="">
      53 
    </div> 
    <div style="">
      54 
    </div> 
    <div style="">
      55 
    </div> 
    <div style="">
      56 
    </div> 
    <div style="">
      57 
    </div> 
    <div style="">
      58 
    </div> 
    <div style="">
      59 
    </div> 
    <div style="">
      60 
    </div> 
    <div style="">
      61 
    </div> 
    <div style="">
      62 
    </div> 
    <div style="">
      63 
    </div> 
    <div style="">
      64 
    </div> 
    <div style="">
      65 
    </div> 
    <div style="">
      66 
    </div> 
    <div style="">
      67 
    </div> 
    <div style="">
      68 
    </div> 
    <div style="">
      69 
    </div> 
    <div style="">
      70 
    </div> 
    <div style="">
      71 
    </div> 
    <div style="">
      72 
    </div> 
    <div style="">
      73 
    </div> 
    <div style="">
      74 
    </div> 
    <div style="">
      75 
    </div> 
    <div style="">
      76 
    </div> 
    <div style="">
      77 
    </div> 
    <div style="">
      78 
    </div> 
    <div style="">
      79 
    </div> 
    <div style="">
      80 
    </div> 
    <div style="">
      81 
    </div> 
    <div style="">
      82 
    </div> 
    <div style="">
      83 
    </div> 
    <div style="">
      84 
    </div> 
    <div style="">
      85 
    </div> 
    <div style="">
      86 
    </div> 
    <div style="">
      87 
    </div> 
    <div style="">
      88 
    </div> 
    <div style="">
      89 
    </div> 
    <div style="">
      90 
    </div> 
    <div style="">
      91 
    </div> </td> 
   <td style=""> 
    <div style=""> 
     <div style=""> 
      <code style="">#include &lt;stdio.h&gt;</code> 
     </div> 
     <div style=""> 
      <code style="">#include &lt;stdlib.h&gt;</code> 
     </div> 
     <div style=""> 
      <code style="">typedef</code> 
      <code style="">char</code> 
      <code style=""> TelemType;</code> 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style=""> 
      <code style="">typedef</code> 
      <code style="">struct</code> 
      <code style=""> TNode{ </code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">TelemType data;</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">struct</code> 
      <code style="">TNode *lchild,*rchild;</code> 
     </div> 
     <div style=""> 
      <code style="">} BitNode;</code> 
     </div> 
     <div style=""> 
      <code style="">//声明</code> 
     </div> 
     <div style=""> 
      <code style="">BitNode* createTree(</code> 
      <code style="">void</code> 
      <code style="">);</code> 
     </div> 
     <div style=""> 
      <code style="">void</code> 
      <code style="">preOrderTraverse(BitNode *);</code> 
     </div> 
     <div style=""> 
      <code style="">void</code> 
      <code style="">inOrderTraverse(BitNode *);</code> 
     </div> 
     <div style=""> 
      <code style="">void</code> 
      <code style="">lastOrderTraverse(BitNode *);</code> 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style=""> 
      <code style="">int</code> 
      <code style="">main(</code> 
      <code style="">int</code> 
      <code style="">agrc,</code> 
      <code style="">char</code> 
      <code style="">*argv[]){ </code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">BitNode *root=NULL;</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">root=createTree();&nbsp;</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">printf</code> 
      <code style="">(</code> 
      <code style="">"\n先序遍历二叉树:"</code> 
      <code style="">);</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">preOrderTraverse(root);</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">printf</code> 
      <code style="">(</code> 
      <code style="">"\n中序遍历二叉树:"</code> 
      <code style="">);</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">inOrderTraverse(root);</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">printf</code> 
      <code style="">(</code> 
      <code style="">"\n后序遍历二叉树:"</code> 
      <code style="">);</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">lastOrderTraverse(root);</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">return</code> 
      <code style="">0;</code> 
     </div> 
     <div style=""> 
      <code style="">}</code> 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style=""> 
      <code style="">//创建二叉树</code> 
     </div> 
     <div style=""> 
      <code style="">BitNode* createTree(</code> 
      <code style="">void</code> 
      <code style="">){ </code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">BitNode *b;</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">TelemType ch;</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">scanf</code> 
      <code style="">(</code> 
      <code style="">"%c"</code> 
      <code style="">,&amp;ch);</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">if</code> 
      <code style="">(ch==</code> 
      <code style="">'#'</code> 
      <code style="">){ </code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">b=NULL;</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">}</code> 
      <code style="">else</code> 
      <code style="">{ </code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">b=(BitNode *)</code> 
      <code style="">malloc</code> 
      <code style="">(</code> 
      <code style="">sizeof</code> 
      <code style="">(BitNode));</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">b-&gt;data=ch;</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">b-&gt;lchild=createTree();</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">b-&gt;rchild=createTree();</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">}</code> 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">return</code> 
      <code style="">b;</code> 
     </div> 
     <div style=""> 
      <code style="">}</code> 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style=""> 
      <code style="">//先序遍历</code> 
     </div> 
     <div style=""> 
      <code style="">void</code> 
      <code style="">preOrderTraverse(BitNode *root){ </code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">if</code> 
      <code style="">(root){ </code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">printf</code> 
      <code style="">(</code> 
      <code style="">"%c"</code> 
      <code style="">,root-&gt;data);</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">preOrderTraverse(root-&gt;lchild);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">preOrderTraverse(root-&gt;rchild);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">}</code> 
     </div> 
     <div style=""> 
      <code style="">}</code> 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style=""> 
      <code style="">//中序遍历</code> 
     </div> 
     <div style=""> 
      <code style="">void</code> 
      <code style="">inOrderTraverse(BitNode *root){ </code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">if</code> 
      <code style="">(root){ </code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp;</code> 
      <code style="">inOrderTraverse(root-&gt;lchild);</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">printf</code> 
      <code style="">(</code> 
      <code style="">"%c"</code> 
      <code style="">,root-&gt;data);</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp;</code> 
      <code style="">inOrderTraverse(root-&gt;rchild);</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">}</code> 
     </div> 
     <div style=""> 
      <code style="">}</code> 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style="">
       &nbsp; 
     </div> 
     <div style=""> 
      <code style="">//后序遍历</code> 
     </div> 
     <div style=""> 
      <code style="">void</code> 
      <code style="">lastOrderTraverse(BitNode *root){ </code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">if</code> 
      <code style="">(root){ </code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp;</code> 
      <code style="">lastOrderTraverse(root-&gt;lchild);</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp;</code> 
      <code style="">lastOrderTraverse(root-&gt;rchild);</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp;</code> 
      <code style="">printf</code> 
      <code style="">(</code> 
      <code style="">"%c"</code> 
      <code style="">,root-&gt;data);</code> 
     </div> 
     <div style=""> 
      <code style="">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="">}</code> 
     </div> 
     <div style=""> 
      <code style="">}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

结果:  
[![QQ截图20131013173637][QQ_20131013173637]][QQ_20131013173637]

[20130507202022904]: http://silenceper.qiniudn.com/wp-content/uploads/2013/10/20130507202022904.jpg
[QQ_20131013173637]: http://silenceper.qiniudn.com/wp-content/uploads/2013/10/QQ%E6%88%AA%E5%9B%BE20131013173637.png