C实现前序遍历二叉树

article/2025/9/17 16:50:55

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. 运行结果