C语言——二叉树的基本操作（二叉树遍历）

深碍√TFBOYSˉ_ 2023-06-21 07:27 17阅读 0赞

## 程序需求 ##

1.内容包括二叉链表的结构描述。  
2.二叉树的建立。  
3.二叉树的先序、中序与后序遍历算法。  
先序遍历：先访问根节点,再先序遍历左子树,最后先序遍历右子树  
中序遍历：先中序遍历左子树,再访问根节点,最后中序遍历右子树  
后序遍历：先后序遍历左子树,再后序遍历右子树,最后访问根节点  
4.建立二叉树,并通过调用函数。  
5.输出先序遍历、中序遍历与后序遍历的结果。

**算法的基本思想**  
根据题目要求，采用二叉链表来存储二叉树结构，二叉树是非线性数据集结构，通过遍历可以把二叉树中的结点访问一次且一次，从而得到顺序序列。  
先序遍历：  
1.先访问根节点  
2.再先序遍历左子树  
3.最后先序遍历右子树  
中序遍历：  
1.先中序遍历左子树  
2.再访问根节点  
3.最后中序遍历右子树  
后序遍历：  
1.先后序遍历左子树  
2.再后序遍历右子树  
3.最后访问根节点

**程序的流程**  
程序由三个模块组成：  
1.输入模块：输入二叉树的扩展，就要先进行二叉树的扩展，也就是将二叉树每个结点的空指针引出一个虚结点，其值为一个特定值，比如“*”。用“*”来表示空子树，处理后的二叉树称为原二叉树的扩展二叉树。  
2.计算模块：设计先序PreOrder，中序InOrder，后序PostOrder遍历函数，进行函数调用二叉树结点排序。  
3.输出模块：输出三种遍历结果。

## 二叉树遍历 ##

#include<stdio.h>
    #include<stdlib.h>
    
    typedef struct Node//定义二叉树链表结点结构
    {
        
    	char data;
    	struct Node * LChild;
        struct Node * RChild;
    }BiTNode,* BiTree;
    
    
    BiTree creat(BiTree root)//创建二叉树
    {
        
    char x;
    x = getchar();
    if(x == '*')
    root = NULL;
    else
    {
        
    root = (BiTNode*)malloc(sizeof(BiTNode));
    root->data = x;
    root->LChild = creat(root->LChild);
    root->RChild = creat(root->RChild);
    }
    return root;
    }
    
    
    
    void PreOrder (BiTree root)//先序遍历二叉树
    {
        if(root!=NULL)
    {
        
    	   printf(" %c ",root->data); 
    		PreOrder (root->LChild);
    		PreOrder (root->RChild);
    }
    }
    
    
    void InOrder (BiTree root)//中序遍历二叉树
    {
        
    	if(root!=NULL)
    	{
        
    		InOrder(root->LChild);
    		printf(" %c ",root->data);
    		InOrder(root->RChild);
    
    	}
    }
    
    
    void PostOrder(BiTree root)//后序遍历二叉树
    {
        
    	if(root!=NULL)
    	{
        
    		PostOrder(root->LChild);
            PostOrder(root->RChild);
    		printf(" %c ",root->data);
    	}
    
    }
    
    
    void main()
    {
        
    BiTree t=NULL;
    printf("请输入二叉树的数据(输入格式为扩展二叉树序列,空子树输入*):\n");
    t = creat(t);
    printf("先序遍历:\n");
    PreOrder(t);
    printf("\n");
    printf("中序遍历:\n");
    InOrder(t);
    printf("\n");
    printf("后序遍历:\n");
    PostOrder(t);
    printf("\n");
    }

**输入和输出的格式**  
输入：输入的遍历序列是一种“扩展的遍历序列”，在扩展的遍历序列中，必须用特定的元素来表示空子树。输入扩展二叉树序列，空子树用“\*”表示  
输入如下二叉树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]  
输出：分别输出先序，中序，后序遍历的排序结果  
先序遍历：A B D F G C E H  
中序遍历：B F D G A C E H  
后序遍历：F G D B H E C A  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019121118421531.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191211184353346.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70