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

PAGEPAGE8二叉树的基本操作摘要：本次课程设计通过对二叉树的一系列操作主要练习了二叉树的建立、四种遍历方式：先序遍历、中序遍历、后序遍历和层序遍历以及节点数和深度的统计等算法。增加了对二叉树这一数据结构的理解，掌握了使用c语言对二叉树进行一些基本的操作。关键字：递归、二叉树、层序遍历、子树交换一、程序简介本程序名为“二叉树基本操作的实现”，其主要为练习二叉树的基本操作而开发，其中包含了建立、遍历、统计叶子结点和深度等一系列操作。其中定义二叉链表来表示二叉树，用一个字符类型的数据来表示每一个节点中存储的数据。由于没有进行图形界面的设计，用户可以通过程序中的遍历二叉树一功能来查看操作的二叉树。二、功能模块2.1功能模块图2.2功能模块详解2.2.1建立二叉树输入要建立的二叉树的扩展二叉树的先序遍历序列，来建立二叉树，建立成功会给出提示。2.2.2遍历二叉树执行操作之后会有四个选项可供选择：先序遍历、中序遍历、后序遍历、层序遍历。输入对应的序号即可调动相关函数输出相应的遍历序列。2.2.3统计叶子节点树执行之后输出叶子结点的个数。2.2.4求二叉树深度执行之后输出二叉树的深度。2.2.5子树交换交换成功则会给出提示，用户可通过遍历二叉树来观察子树交换之后的二叉树。三、数据结构和算法设计3.1二叉链表的设计typedef

struct

BiNode

{

char

data;

struct

BiNode*

lchild;

//左孩子

struct

BiNode*

rchild;

//右孩子}BiTree;

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

struct

{

ElemType*

data;

int

head;//队头指针

int

tail;//队尾指针

}

SqQueue;

队列主要用于二叉树遍历过程中的层序遍历，从根节点开始分别将左右孩子放入队列，然后从对头开始输出。队列的相关操作封装在SqQueue.h中，包括入队、出队、判断队列是否为空等操作。四、全局函数的设计本程序中应用了一些全局函数，本着用到那个函数就把哪个函数设为全局函数的原则，抽象出了以下全局函数：4.1全局函数列表BiTree*createBinaryTree(BiTree*b)本函数用于建立二叉树voidTraverse(BiTree*b)本函数用于遍历二叉树voidPreOrderTraverse(BiTree*b)本函数用于前序遍历二叉树voidInOrderTraverse(BiTree*b)本函数用于中序遍历二叉树voidPostOrderTraverse(BiTree*b)本函数用于后序遍历二叉树voidLevelOrderTraverse(BiTree*b)本函数用于层序遍历二叉树voidgetLeavesNum(BiTree*b)本函数用于统计叶子结点个数intgetHeight(BiTree*b)本函数用于求二叉树的深度voidswap(BiTree*b)本函数用子树交换voiddisplayMenu()本函数用于展示菜单4.2全局函数在具体系统中的分布BiTree.h此文件为二叉树的头文件，包含上述所有全局函数五、功能实现二叉树的基本操作这个程序的主要功能就是建立二叉树，然后运用先序、中序等遍历方法遍历二叉树，然后还有统计二叉树的叶子结点个数、求二叉树的深度以及进行子树的交换。5.1二叉树的基本操作流程图如下菜单界面如下：5.2二叉树的基本操作的代码如下5.2.1二叉树的建立//按照前序输入二叉树结点的值，“#”表示空

BiTree*

createBinaryTree(BiTree*

b)

{

char

ch;//定义变量用于储存输入的字符

scanf("%c",

&ch);

if

(ch

==

'#')

{

b

=

NULL;

}

else

{

if

((b

=

(BiTree*)malloc(sizeof(BiTree)))

!=

NULL)

{//如果内存分配成功就执行下面操作

//生成根节点

b->data

=

ch;

//构造左子树

b->lchild=createBinaryTree(b->lchild);

//构造右子树

b->rchild=createBinaryTree(b->rchild);

}

}

return

b;

}

5.2.2二叉树的遍历如图所示选择遍历后有三种方案可供选择：前序遍历void

PreOrderTraverse(BiTree*

b)

{

if

(b

==

NULL)

{

return;

}

//首先打印结点数据

printf("%c

",

b->data);

//再先序遍历左子树

PreOrderTraverse(b->lchild);

//最后先序遍历右子树

PreOrderTraverse(b->rchild);

}

中序遍历//中序遍历

void

InOrderTraverse(BiTree*

b)

{

if

(b

==

NULL)

{

return;

}

//首先中序遍历左子树

InOrderTraverse(b->lchild);

//再打印结点数据

printf("%c

",

b->data);

//最后中序遍历右子树

InOrderTraverse(b->rchild);

}

后序遍历//后序遍历

void

PostOrderTraverse(BiTree*

b)

{

if

(b

==

NULL)

{

return;

}

//首先后序遍历左子树

PostOrderTraverse(b->lchild);

//再后序遍历右子树

PostOrderTraverse(b->rchild);

//最后打印结点数据

printf("%c

",

b->data);

}

层序遍历//层序遍历

void

LevelOrderTraverse(BiTree*

b)

{

SqQueue*

s

=

initSqQueue();

BiTree*

temp;

if

(b)

{

append(s,

*b);

while

(!isEmpty(s))

{

temp=pop(s);

printf("%c

",

temp->data);

if

(temp->lchild)

{

append(s,

*temp->lchild);

}

if

(temp->rchild)

{

append(s,

*temp->rchild);

}

}

}

}

5.2.3统计叶子结点个数//统计叶子节点

int

count;//全局变量，如果出现叶子结点就加一

void

getLeavesNum(BiTree*

b)

{

if

(b)

{

if

(!b->lchild

&&

!b->rchild)

{

count++;

}

getLeavesNum(b->lchild);

getLeavesNum(b->rchild);

}

}

5.3.4求二叉树的深度//求二叉树的深度

int

getHeight(BiTree*

b)

{

int

leftHeight,

rightHeight;

if

(!b)

{

return

0;

}

leftHeight

=

getHeight(b->lchild);

rightHeight

=

getHeight(b->rchild);

return

leftHeight

>

rightHeight

?

leftHeight

+

1

:

rightHeight

+

1;

}

5.2.5子树交换//子树交换

BiTree*

temp;//临时变量，用于交换

void

swap(BiTree*

b)

{

if

(b

==

NULL)

{

return;

}

else

{

temp

=

b->lchild;

b->lchild

=

b->rchild;

b->rchild

=

temp;