二叉树的建立与基本操作

￡神魔★判官ぃ 2022-06-02 07:22 130阅读 0赞

编写程序实现二叉树的如下操作：  
1) 建立二叉链表  
2) 二叉树的先序、中序、后序遍历  
3) 求解二叉树的叶子结点个  
4) 将二叉树中所有结点的左、右子树相互交换

**输入：**  
　　扩展二叉树先序序列：ab\#d\#\#ce\#\#\#。其中\#代表空指针。

**输出：**  
 二叉树的凹入表示  
　　二叉树的先序序列、中序序列、后序序列  
　　二叉树叶子结点个数  
　　左、右子树相互交换后的二叉树的凹入表示  
　　左、右子树相互交换后的二叉树的先序序列、中序序列、后序序列。

**说明：**  
　　在输出凹入表示的二叉树时，先输出根结点，然后依次输出左右子树，上下层结点之间相隔 3 个空格。

<table style="width:1615px; margin-bottom:20px; color:rgb(68,68,68); font-family:open_sansregular,Arial,Helvetica,sans-serif; font-size:13px; line-height:25px"> 
 <tbody> 
 <tr> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 测试用例 1</td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64766&amp;test=82480&amp;type=in&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
 <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
 <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> ab#d##ce###↵</li> 
 </ol> 
 </div> </td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64766&amp;test=82480&amp;type=out&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
 <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
 <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> BiTree↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> a↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;b↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;c↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> pre_sequence&nbsp;&nbsp;:&nbsp;abdce↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> in_sequence&nbsp;&nbsp;&nbsp;:&nbsp;bdaec↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> post_sequence&nbsp;:&nbsp;dbeca↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;leaf:&nbsp;2↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> BiTree&nbsp;swapped↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> a↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;c↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;b↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> pre_sequence&nbsp;&nbsp;:&nbsp;acebd↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> in_sequence&nbsp;&nbsp;&nbsp;:&nbsp;ceadb↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> post_sequence&nbsp;:&nbsp;ecdba↵</li> 
 </ol> 
 </div> </td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 1秒</td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 64M</td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 0</td> 
 </tr> 
 <tr> 
 <td style="padding:4px; line-height:20px; vertical-align:middle"> 测试用例 2</td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64766&amp;test=82481&amp;type=in&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
 <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
 <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> abd##e##cf##g##↵</li> 
 </ol> 
 </div> </td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64766&amp;test=82481&amp;type=out&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
 <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
 <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> BiTree↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> a↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;b↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;c↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;g↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> pre_sequence&nbsp;&nbsp;:&nbsp;abdecfg↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> in_sequence&nbsp;&nbsp;&nbsp;:&nbsp;dbeafcg↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> post_sequence&nbsp;:&nbsp;debfgca↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;leaf:&nbsp;4↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> BiTree&nbsp;swapped↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> a↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;c↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;g↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;b↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> pre_sequence&nbsp;&nbsp;:&nbsp;acgfbed↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> in_sequence&nbsp;&nbsp;&nbsp;:&nbsp;gcfaebd↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> post_sequence&nbsp;:&nbsp;gfcedba↵</li> 
 </ol> 
 </div> </td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle"> 1秒</td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle"> 64M</td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle"> 0</td> 
 </tr> 
 </tbody> 
</table>

#include<stdio.h> 
 #include<stdlib.h> 
 
 struct Btreenode 
 { 
 char element; 
 struct Btreenode *left; 
 struct Btreenode *right; 
 }; 
 typedef struct Btreenode *PtrNode; 
 int numlef; 
 void Creat_Btree(PtrNode*proot) //用二级指针创建二叉树 
 { 
 char c; 
 c = getchar(); 
 if (c == '#') 
 *proot = NULL; 
 else 
 { 
 (*proot) = (PtrNode)malloc(sizeof (struct Btreenode)); 
 (*proot)->element = c; 
 Creat_Btree(&(*proot)->left); 
 Creat_Btree(&(*proot)->right); 
 if (!(*proot)->left&&!(*proot)->right) 
 numlef++; 
 } 
 } 
 
 PtrNode creat_BTree(PtrNode proot) //用返回值创建二叉树（没用二级指针） 
 { 
 
 char c; 
 c = getchar(); 
 if (proot == NULL&&c!='#') 
 { 
 proot = (PtrNode)malloc(sizeof (struct Btreenode)); 
 proot->element = c; proot->left = proot->right = NULL; 
 proot->left = creat_BTree(proot->left); 
 proot->right = creat_BTree(proot->right); 
 if (!(proot)->left&&!(proot)->right) 
 numlef++; 
 } 
 return proot; 
 } 
 
 void inorder(PtrNode rt) 
 { 
 if (rt) 
 { 
 inorder(rt->left); 
 printf("%c", rt->element); 
 inorder(rt->right); 
 } 
 } 
 
 void preorder(PtrNode rt) 
 { 
 if (rt) 
 { 
 printf("%c", rt->element); 
 preorder(rt->left); 
 preorder(rt->right); 
 } 
 } 
 
 void postorder(PtrNode rt) 
 { 
 if (rt) 
 { 
 
 postorder(rt->left); 
 postorder(rt->right); 
 printf("%c", rt->element); 
 } 
 } 
 
 void Printline(char c, int num) 
 { 
 for (int i = 0; i < 4*num; i++) 
 { 
 printf(" "); 
 } 
 printf("%c\n", c); 
 } 
 
 void listtree(PtrNode rt, int depth) 
 { 
 if (rt) 
 { 
 Printline(rt->element, depth); 
 listtree(rt->left, depth + 1); 
 listtree(rt->right, depth + 1); 
 } 
 } 
 
 void Swap(PtrNode rt) 
 { 
 if (rt) 
 { 
 
 if (rt->left||rt->right) 
 { 
 PtrNode tmp = rt->left; 
 rt->left = rt->right; 
 rt->right = tmp; 
 if (rt->left) 
 Swap(rt->left); 
 if (rt->right) 
 Swap(rt->right); 
 } 
 } 
 } 
 int main() 
 { 
 //freopen("1.txt","r", stdin); 
 PtrNode root=NULL; 
 printf("BiTree\n"); 
 //Creat_Btree(&root); 
 root=creat_BTree(root); 
 listtree(root, 0); 
 
 
 printf("pre_sequence : "); 
 preorder(root); printf("\n"); 
 printf("in_sequence : "); 
 inorder(root); printf("\n"); 
 printf("post_sequence : "); 
 postorder(root); printf("\n"); 
 
 
 printf("Number of leaf: %d\n", numlef); 
 printf("BiTree swapped\n"); 
 Swap(root); 
 listtree(root, 0); 
 
 printf("pre_sequence : "); 
 preorder(root); printf("\n"); 
 printf("in_sequence : "); 
 inorder(root); printf("\n"); 
 printf("post_sequence : "); 
 postorder(root); printf("\n"); 
 
 
 return 0; 
 }