数据结构课程设计-二叉树的基本操作 下载本文

内容发布更新时间 : 2024/12/23 21:29:01星期一 下面是文章的全部内容请认真阅读。

二叉树的基本操作

摘要:

本次课程设计通过对二叉树的一系列操作主要练习了二叉树的建立、四种遍历方式:先序遍历、中序遍历、后序遍历和层序遍历以及节点数和深度的统计等算法。增加了对二叉树这一数据结构的理解,掌握了使用c语言对二叉树进行一些基本的操作。

关键字:递归、二叉树、层序遍历、子树交换

一、程序简介

本程序名为“二叉树基本操作的实现”,其主要为练习二叉树的基本操作而开发,其中包含了建立、遍历、统计叶子结点和深度等一系列操作。其中定义二叉链表来表示二叉树,用一个字符类型的数据来表示每一个节点中存储的数据。由于没有进行图形界面的设计,用户可以通过程序中的遍历二叉树一功能来查看操作的二叉树。

二、功能模块

2.1功能模块图

2.2功能模块详解

2.2.1建立二叉树

输入要建立的二叉树的扩展二叉树的先序遍历序列,来建立二叉树,建立成功会给出提示。 2.2.2遍历二叉树

执行操作之后会有四个选项可供选择:先序遍历、中序遍历、后序遍历、层序遍历。输入对应的序号即可调动相关函数输出相应的遍历序列。 2.2.3统计叶子节点树

执行之后输出叶子结点的个数。 2.2.4求二叉树深度

执行之后输出二叉树的深度。 2.2.5子树交换

交换成功则会给出提示,用户可通过遍历二叉树来观察子树交换之后的二叉树。

三、数据结构和算法设计

3.1二叉链表的设计

1. typedef struct BiNode { 2. char data;

3. struct BiNode* lchild; //左孩子 4. struct BiNode* rchild; //右孩子 5. }BiTree;

用一个字符型保存节点数据,分别定义两个struct BiNode类型的指针来指向左孩子和右孩子。在BiTree.h中实现相关的功能。

3.2队列的实现

1. typedef struct { 2. ElemType* data; 3. int head;//队头指针 4. int tail;//队尾指针 5. } SqQueue;

队列主要用于二叉树遍历过程中的层序遍历,从根节点开始分别将左右孩子放入队列,然后从对头开始输出。队列的相关操作封装在SqQueue.h中,包括入队、出队、判断队列是否为空等操作。

2

四、全局函数的设计

本程序中应用了一些全局函数,本着用到那个函数就把哪个函数设为全局函数的原则,抽象出了以下全局函数:

4.1全局函数列表

(1)BiTree* createBinaryTree(BiTree* b)

本函数用于建立二叉树

(2)void Traverse(BiTree* b)

本函数用于遍历二叉树

(3)void PreOrderTraverse(BiTree* b)

本函数用于前序遍历二叉树

(4)void InOrderTraverse(BiTree* b)

本函数用于中序遍历二叉树

(5)void PostOrderTraverse(BiTree* b)

本函数用于后序遍历二叉树

(6)void LevelOrderTraverse(BiTree* b)

本函数用于层序遍历二叉树

(7)void getLeavesNum(BiTree* b)

本函数用于统计叶子结点个数 (8)int getHeight(BiTree* b)

本函数用于求二叉树的深度 (9)void swap(BiTree* b)

本函数用子树交换

(10)void displayMenu()

本函数用于展示菜单

4.2全局函数在具体系统中的分布

BiTree.h

此文件为二叉树的头文件,包含上述所有全局函数

五、功能实现

二叉树的基本操作这个程序的主要功能就是建立二叉树,然后运用先序、中序等遍历方法遍历二叉树,然后还有统计二叉树的叶子结点个数、求二叉树的深度以及进行子树的交换。

3