数据结构课程设计

目录。摘要 - 1 -

1引言 - 2 -

1.1问题的提出 - 2 -

1.2 c语言 - 2 -

1.3 c语言发展过程 - 2 -

1.4任务与分析 - 2 -

1.4.1任务一 - 2 -

1.4.2任务二 - 3 -

1.4.3任务三 - 3 -

1.4.4任务四 - 4 -

2 设计方案 - 4 -

2.1头文件 - 4 -

2.2结构与函数的定义 - 4 -

2.3函数的实现 - 5 -

2.3.1主函数 - 5 -

2.3.2 功能函数 - 6 -

2.3.2.1任务一的实现 - 6 -

2.3.2.2任务二的实现 - 6 -

2.3.2.3任务三的实现 - 7 -

2.3.2.4任务四的实现 - 7 -

3程序演示： -8 -

结论 - 9 -

参考文献 - 10 -

该题是二叉树的综合运用，由四个部分组成如下：

第一部分：用户正确输入一棵二叉树的中序和后序序列，如下：

中序：g l d h b e i a c j f k

后序： l g h d i e b j k f c a

然后根据用户输入的中序与后序序列，创建出这棵二叉树。

第二部分：用户正确输入一棵二叉树的先序和中序序列，如下：

先序： a b c d e f g h i

中序： b c a e d g h f i

然后根据用户输入的先序与中序序列，创建这棵二叉树。

第三部分：中序遍历二叉树将其线索化。

第四部分：中序遍历二叉树。

关键词：二叉树，中序遍历，线索化。

以前的操作系统等系统软件主要是由汇编语言编写的（包括ｕｎｉ操作系统在内）。由于汇编语言依赖于计算机硬件，程序的可读性和可移植性都比较差。为了提高可读性和可移植性，最好改用高级语言，但一般高级语言难以实现汇编语言的某些功能（汇编语言可以直接对硬件进行操作，例如，对内存地址的操作、位操作等）。

人们设想能否找到一种既具有一般高级语言特性，又具有低级语言特性的语言，集它们的优点于一身。于是，ｃ语言就在这种情况下应运而生了。

c语言既有高级语言的特点，又具有汇编语言的特点；既是一个成功的系统设计语言，有时一个使用的程序设计语言；既能用来编写不依赖计算机硬件的应用程序，又能用来编写各种系统程序；是一种受欢迎、应用广泛的程序设计语言。

2024年，美国贝尔实验室的在b语言的基础上最终设计出了一种新的语言，他取了bcpl的第二个字母作为这种语言的名字，这就是c语言。

2024年dennis 发表了不依赖于具体机器系统的c语言编译文本《可移植的c语言编译程序》。

2024年brian 和dennis 出版了名著《the c programming language》，从而使c语言成为目前世界上流行最广泛的高级程序设计语言。

任务一：根据用户输入的二叉树的中序与后序序列，创建出该二叉树。

分析：后序遍历时，最后一个节点是根节点，然后查找出中序序列中的该节点的位置，于是就把中序遍历序列分成两部分，左边就是左子树，右边就是右子树。然后对左子树与右子树在分别用同样的方法遍历，即可用递归算法创建出改二叉树。

可用一个具体的例子来说明：

用户正确输入一棵二叉树的中序和后序序列，如下：

中序：g l d h b e i a c j f k

后序： l g h d i e b j k f c a

因为后序序列中的最后一个元素是根节点，为a，然后在中序序列中查找a的位置，于是就可以把中序序列分成两部分，a的左边：g l d h b e i；a的右边：c j f k。

于是g l d h b e i为左子树的部分，其对应后序序列的l g h d i e b。同理c j f k为右子树的部分，其对应的后序序列为j k f c a。这样就可以对左右子树运用递归算法得出改二叉树的结构，并创建出这棵二叉树。

任务二：根据用户输入的前序与中序序列，创建出该二叉树。

分析：先序序列的第一个节点就是根节点，然后在中序序列中找出该节点的位置，于是就可以把中序序列分成左右两部分，左边就是左子树部分，右边就是右子树部分。

然后对左子树与右子树分别用同样的方法遍历，就可以递归创建出该二叉树。

用一个具体的列子来说明：

用户正确输入一棵二叉树的先序和中序序列，如下：

先序： a b c d e f g h i

中序： b c a e d g h f i

因为先序遍历的第一个节点就是根节点为a，在中序找出节点a，把中序序列分成两个部分，a的左边为b c，a的右边e d g h f i。左子树序列b c对应先序序列中的b c，右子树序列e d g h f i对应先序序列中的d e f g h i。然后对左右子树用同样的方法遍历，即递归算法就可以创建出该二叉树。

任务三：中序遍历二叉树将其线索化。

分析：由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继的过程，而前驱或是后继的信息只有在遍历中才能得到，因此线索化的过程其实就是在遍历中修改空指针的过程。为了记下遍历过程中的访问节点的先后关系，可以用一个指针pre始终记录刚刚访问过的节点于是就可以得到中序遍历二叉树将其线索化的算法。

任务四：中序遍历二叉树。

分析：中序遍历二叉树可以用递归算法实现，先访问节点的左子树，然后访问该节点，然后再访问节点右子树，访问节点的左子树与右子树可以用同样的方法，即递归算法实现。这样就实现的二叉树的中序递归遍历。

根据以上对任务的分析就可以得到相应的算法。

#include<>

typedef struct node //定义节点的结构

char ch; /数据域

struct node *left,*right; /左右指针

pointertag ltag,rtag;//非线索二叉树就未用该标志。

*btree;

btree qzcreatbtree(char *pre,char *in,int len);/由前序与中序创建一颗二叉树

void zhcreatbtree(char *in,char *post,int len,btree &t);/由后序与中序创建一颗二叉树

void invisitthreading(btree &thrt,btree t);/中序遍历二叉树t,并将其线索化，thrt指向头结点。

void inthreading(btree p,btree &pre);

void invisit(btree head);/中序遍历二叉树。

main()

int lenpre,lenin;

char pre[30],in[30],post[30]; 存储先序、中序遍历、后序遍历的序列

btree head,t,thrt;

中序与前序的二叉树创建的调用。

head=(btree)malloc(sizeof(node));

printf("请输入前序与中序遍历二叉树串");

scanf("%s%s",pre,in);

lenpre=strlen(pre);

printf("创建二叉树···n");

head=qzcreatbtree(pre,in,lenpre); 前序与中序创建一颗二叉树。

printf("创建成功！");

printf("中序遍历二叉树： ")

invisit(head); 中序遍历二叉树。

printf("");printfn");

后序与中序创建二叉树的调用。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了