实验七、数据结构之二叉树用递归方法建立二叉树 C语言版

刺骨的言语ヽ痛彻心扉 2023-06-10 04:27 12阅读 0赞

###### 1. 看了大佬C++版本的递归法建立二叉树：在此有兴趣用C语言实现一下 ######

C++版本链接：[https://blog.csdn.net/stpeace/article/details/8138303][https_blog.csdn.net_stpeace_article_details_8138303]

###### 2. 实现效果： ######

![在这里插入图片描述][2019102817101270.png]

###### 3. 源代码（已验证） ######

假设二叉树为：
    
                                       a
    
                              b                 c
    
                                   d                 e
    
       
    
       因为程序中要知道叶子结点（终点），所以要将上面的二叉树变成扩展二叉树 (把叶子结点的孩子补成#, 用作标记),  扩展后就变成了：         
    
                                       a
    
                            b                    c
    
                       #        d          #       e
    
                              #    #             #    #

那么，**按先序序列输入二叉树的时候**，需要输入: ab\#d\#\#c\#e\#\# (注意，输入后，按enter键即可) ，完整程序如下：（先序创建二叉树）

1 #include <stdio.h>
      2 #include <stdlib.h>
      3 
      4 typedef struct Binnode
      5 {
        
      6     char data;
      7     struct Binnode *lchild;
      8     struct Binnode *rchild;
      9 } Binnode, *Bintree;
     10 
     11 void Create_Bintree(Bintree *root)
     12 {
        
     13     char ch;
     14 
     15     if ((ch = getchar()) == '#') {
        
     16         *root = NULL;
     17     } else {
        
     18         *root = (Binnode *)malloc(sizeof(Binnode));
     19         (*root)->data = ch;
     20         Create_Bintree(&(*root)->lchild);
     21         Create_Bintree(&(*root)->rchild);
     22     }
     23 }
     24 
     25 void Preorder(Bintree *t)
     26 {
        
     27     if (*t != NULL){
        
     28         printf("%c", ((*t)->data));
     29         Preorder(&(*t)->lchild);
     30         Preorder(&(*t)->rchild);
     31     }
     32 }
     33 
     34 void Inorder(Bintree *t)
     35 {
        
     36     if (*t != NULL){
        
     37         Inorder(&(*t)->lchild);
     38         printf("%c", (*t)->data);
     39         Inorder(&(*t)->rchild);
     40     }
     41 }
     42 
     43 void Posorder(Bintree *t)
     44 {
        
     45     if (*t != NULL){
        
     46         Posorder(&(*t)->lchild);
     47         Posorder(&(*t)->rchild);
     48         printf("%c", (*t)->data);
     49     }
     50 }
     51 int main()
     52 {
        
     53     Bintree T;
     54     printf("Tree Create Start!\n");
     55     Create_Bintree(&T);
     56     printf("Tree Create OK!\n");
     57     printf("先序遍历:\n");
     58     Preorder(&T);
     59     printf("\n中序遍历:\n");
     60     Inorder(&T);
     61     printf("\n后序遍历:\n");
     62     Posorder(&T);
     63     printf("\n");
     64     return 0;
     65 }

[https_blog.csdn.net_stpeace_article_details_8138303]: https://blog.csdn.net/stpeace/article/details/8138303
[2019102817101270.png]: /images/20230531/2da76317786244889a780d21bfc89d5c.png