C实现前序遍历二叉树

一时失言乱红尘 2021-11-11 13:36 288阅读 0赞

**1. 实验目的**

（1）掌握二叉树的逻辑结构；

（2）掌握二叉树的二叉链表存储结构；

（3）验证二叉树的二叉链表存储及遍历操作。

**2. 实验目的**

（1）建立一棵含有*n*个结点的二叉树，采用二叉链表存储；

（2）输出前序遍历该二叉树的遍历结果。

**3. 实验提示**

定义二叉树的数据类型——二叉树结点结构体BiNode，在BiNode基础上实现题目要求的建立二叉链表、前序遍历等基本操作。建立二叉链表可以采用扩展二叉树的一个遍历序列，例如前序序列，将扩展二叉树的前序序列由键盘输入，建立该二叉树的二叉链表存储。

简单起见，本实验假定二叉树的数据元素为char型，要求学生：

（1）将实验程序调试通过后，用模板类改写；

（2）加入层序遍历二叉树等基本操作。

4. 程序代码

#include<stdlib.h>
    #include<stdio.h>
    
    typedef char ElemType;
    
    //二叉树的二叉链表结构，也就是二叉树的存储结构，1个数据域，2个指针域（分别指向左右孩子）
    
    typedef  struct BiTNode
    {
    	ElemType data;
    	struct BiTNode *lchild, *rchild;
    }BiTNode, *BiTree;
    
    //二叉树的建立，按前序遍历的方式建立二叉树，当然也可以以中序或后序的方式建立二叉树
    void CreateBiTree(BiTree *T)
    {
    	ElemType ch;
    	scanf_s("%c",&ch);
    	if (ch == '#')
    		*T = NULL;  //保证是叶结点
    	else
    	{
    		*T = (BiTree)malloc(sizeof(BiTNode));
    		//if (!*T)
    		//exit(OVERFLOW); //内存分配失败则退出。
    		(*T)->data = ch;//生成结点
    		CreateBiTree(&(*T)->lchild);//构造左子树
    		CreateBiTree(&(*T)->rchild);//构造右子树    
    	}
    }
    //表示对遍历到的结点数据进行的处理操作,此处操作是将树结点前序遍历输出
    void operation1(ElemType ch)
    {
    	printf("%c\n",ch);
    }
    //此处在输出的基础上，并输出层数
    void operation2(ElemType ch, int level)
    {
    	printf("%c在第%d层\n",ch,level);
    }
    //递归方式前序遍历二叉树
    void PreOrderTraverse(BiTree T, int level)
    {
    	if (T == NULL)
    		return;
    	/*此处表示对遍历的树结点进行的操作，根据你自己的要求进行操作，这里只是输出了结点的数据*/
    	//operation1(T->data);
    	operation2(T->data, level); //输出了层数
    
    	PreOrderTraverse(T->lchild, level + 1);
    	PreOrderTraverse(T->rchild, level + 1);
    }
    
    //递归方式中序遍历二叉树
    
    void InOrderTraverse(BiTree T, int level)
    {
    	if (T == NULL)
    		return;
    	InOrderTraverse(T->lchild, level + 1);
    
    	//operation1(T->data);
    	operation2(T->data, level); //输出了层数
    
    	InOrderTraverse(T->rchild, level + 1);
    }
    
    //递归方式后序遍历二叉树
    
    void PostOrderTraverse(BiTree T, int level)
    {
    	if (T == NULL)
    		return;
    	PostOrderTraverse(T->lchild, level + 1);
    	PostOrderTraverse(T->rchild, level + 1);
    
    	//operation1(T->data);
    	operation2(T->data, level); //输出了层数
    }
    
    
    int main()
    {
    	int level = 1; //表示层数
    	BiTree T = NULL;
    	printf("请以前序遍历的方式输入扩展二叉树："); //类似输入AB#D##C##
    	CreateBiTree(&T);// 建立二叉树，没有树，怎么遍历
    
    	printf("递归前序遍历输出为：\n");
    	PreOrderTraverse(T, level);//进行前序遍历，其中operation1()和operation2()函数表示对遍历的结点数据进行的处理操作
    	printf("\n");
    
    	printf("递归中序遍历输出为：\n");
    	InOrderTraverse(T, level);
    	printf("\n");
    
    	printf("递归后序遍历输出为：\n");
    	PostOrderTraverse(T, level);
    	printf("\n");
    	system("pause");
    	return 0;
    }

**5. 运行结果**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTg3NjEy_size_16_color_FFFFFF_t_70][]

![20190805231934272.png][]

**6. 实验心得**

通过这次实验，我对前序、中序、后续遍历二叉树有了更深的理解,我充分掌握了了递归算法的运行过程与实现，掌握了常用递归算法的算法思想与使用，更全面的认识了计算机中程序运行的过程。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTg3NjEy_size_16_color_FFFFFF_t_70]: /images/20211109/9d5627db90854780a9fa81a7d6f4d42f.png
[20190805231934272.png]: /images/20211109/a591b9f3df904c48b93233b4150287be.png