二叉树的创建与三种遍历（先序，中序，后序）

淡淡的烟草味﹌ 2022-06-12 07:26 52阅读 0赞

\[问题描述\] 建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。  
\[基本要求\] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来 建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。  
\[测试数据\] 1 2 3 0 0 4 5 0 7 0 0 6 0 0 0

则输出结果为 先序：1 2 3 4 5 7 6 中序：3 2 5 7 4 6 1 后序：3 7 5 6 4 2 1

二叉树节点的建立：

C++ Code

建立二叉树：

C++ Code

先序遍历：

C++ Code

中序遍历：

C++ Code

后序遍历：

C++ Code

总代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 62 
 63 
 64 
 65 
 66 
 67 
 68 
 69 
 70 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="width:100%; vertical-align:text-top; background-color:rgb(239,239,239)"> 
 <div style="margin:7px"> 
 #include&lt;bits/stdc++.h&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 
 typedef&nbsp; 
 struct&nbsp;BiTNode 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;data; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 struct&nbsp;BiTNode&nbsp;*lchild,&nbsp;*rchild; 
 }BiTNode&nbsp;,*BiTree; 
 BiTree&nbsp;creatbitree() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp;BiTree&nbsp;T; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;p; 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&amp;p); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(p== 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;T= 
 NULL; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;T=(BiTNode&nbsp;*&nbsp;)malloc( 
 sizeof(BiTNode)); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;T-&gt;data=p; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;T-&gt;lchild=creatbitree(); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;T-&gt;rchild=creatbitree(); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;T; 
 } 
 
 void&nbsp;preOrder(BiTree&nbsp;T) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(T!= 
 NULL) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d&nbsp;",T-&gt;data); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;preOrder(T-&gt;lchild); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;preOrder(T-&gt;rchild); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 void&nbsp;inOrder(BiTree&nbsp;T) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(T!= 
 NULL) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;inOrder(T-&gt;lchild); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d&nbsp;",T-&gt;data); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;inOrder(T-&gt;rchild); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 void&nbsp;postOrder(BiTree&nbsp;T) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(T!= 
 NULL) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;postOrder(T-&gt;lchild); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;postOrder(T-&gt;rchild); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d&nbsp;",T-&gt;data); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp;BiTree&nbsp;ta; 
 &nbsp;&nbsp;&nbsp;&nbsp;ta=creatbitree(); 
 &nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "xian&nbsp;xu&nbsp;bian&nbsp;li\n"); 
 &nbsp;&nbsp;&nbsp;&nbsp;preOrder(ta); 
 &nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "\n"); 
 &nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "zhong&nbsp;xu&nbsp;bian&nbsp;li\n"); 
 &nbsp;&nbsp;&nbsp;&nbsp;inOrder(ta); 
 &nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "\n"); 
 &nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "hou&nbsp;xu&nbsp;bian&nbsp;li&nbsp;\n"); 
 &nbsp;&nbsp;&nbsp;&nbsp;postOrder(ta); 
 
 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

![Image 1][]

[Image 1]: