C语言数据结构和算法实验二：二叉树的遍历

浅浅的花香味﹌ 2022-04-23 23:12 151阅读 0赞

### C语言数据结构和算法实验二：二叉树的遍历 ###

*   *  前言
     *  问题描述
     *  问题基本判断
     *  参考代码(IDE:VisualStudio)
     *  输出结果

## 前言 ##

题目来源：燕山大学经济管理学院数据结构与算法实验。

## 问题描述 ##

任意给定一棵二叉树。试设计一个程序，在计算机中构造该二叉树，并对它进行遍历。  
一棵二叉树的结点若无子树，则可将其子树看作 “.”，输入时，按照前序序列的顺序输入该结点的内容。对 下图，其输入序列为ABD…EH…CF.I…G…。  
![在这里插入图片描述][20190409221312342.png]  
\[输出\]  
若为空二叉树，则输出：THIS IS A EMPTY BINARY TREE。若二叉树不空，按后序序列输出，对上例，输出结果为：DHEBIFGCA。

## 问题基本判断 ##

\[存储结构\]  
采用二叉链表存储。  
\[算法的基本思想\]  
采用递归方法建立和遍历二叉树。首先建立二叉树的根结点，然后建立其左右子树，直到空子树为止。后序遍历二叉树时，先遍历左子树，后遍历右子树，最后访问根结点。

## 参考代码(IDE:VisualStudio) ##

#include"pch.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node {
        
    	char data;
    	struct node *lchild, *rchild;
    }node, *tree;//定义树节点的结构体
    void CreateTree(tree *p)//建立二叉树
    {
        
    	char name;
    	scanf_s("%c", &name);
    	getchar();//此时%c读取的是单个字符，所以用那个getchar来接收一下
    	if (name == '#')
    		*p = NULL;
    	else
    	{
        
    		*p = (tree)malloc(sizeof(node));
    		(*p)->data = name;
    		printf("请输入%c的左子树\n", name);
    		CreateTree(&(*p)->lchild);
    		printf("请输入%c的右子树\n", name);
    		CreateTree(&(*p)->rchild);
    	}
    
    }
    
    
    void CheckTree(tree p)//后续遍历
    {
        
    	if (p == NULL)
    		return;
    	CheckTree(p->lchild);
    	CheckTree(p->rchild);
    	printf("%c ", p->data);
    }
    int main()
    {
        
    	tree p;
    	printf("输入根节点，#为空树。\n");
    	CreateTree(&p);
    	CheckTree(p);
    }

## 输出结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4OTQ0OA_size_16_color_FFFFFF_t_70]

[20190409221312342.png]: /images/20220222/26606537871b4483bdb6e536c52273cc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4OTQ0OA_size_16_color_FFFFFF_t_70]: /images/20220222/fe2a9c35dce649c1a6737ff46eee6e8d.png