哈尔滨理工大学计算机学院 数据结构课程设计 建立二叉树层序、先序

1、哈尔滨理工大学计算机学院数据结构课程设计建立二叉树层序、先序遍历班级：计05-1班姓名：杨继伟学号：0504110122目录1 需求分析21.1题目分析2 1.2二叉树构造模块41.3层序遍历二叉树模块4 1.4先序遍历二叉树模块42 概要设计 42.1二叉树构造算法4 2.2层序算法72.3先序算法93 详细设计 114 调试分析 155 课设总结 16建立二叉树,层序、先序遍历1需求分析:1.1.题目：建立二叉树，要求能够输入树的各个节点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储的输入函数，输出层序遍历序列的函数，输出 先序遍历序列的函数。分析：首先要输入元素建立二叉树，选择

2、某一种存储结构存储二叉树，本程序采用二叉链表存储结构。由于二叉树的定义是递归的，因而一棵非空二叉树可以看作是由根结点、左子树和右子树这三个基本部分组成的。如果能依次遍历这三个部分的信息，也就遍历了整个二叉树。由此得到的二叉树的遍历是按某种策略访问二叉树中的每一个结点且仅访问一次的过程。程序一共分为如下3个模块：二叉树的构造: Insert_node(btree *root, int node) create_btree(int data, int len) 层序遍历二叉树:Void levelorder(bitree *root) 先序遍历二叉树:Void preorder(bitree *r

3、oot) 1.2.二叉树的构造采用二叉链表存储结构建立二叉树, 二叉树的结点由一个数据元素和分别指向其左右子树的两个分支构成，即数据域和左、右指针域lchilddatarchild数据结构：Typedef strcut bnodeTelemtype data; /结点数据类型Struct bnode *lchild,*rchild; / 定义左右孩子为指针类型bnode,*btree;其中Insert_node(btree *root, int node) 为插入二叉树结点函数，create_btree(int data, int len)为建立二叉树函数 1.3.层序遍历二叉树要采用一个队列

4、。先将二叉树的根节点入队，然后退队，输出该节点，若它有左子树，便将左子树的根节点入队，若它有左子树，便将有子树的根节点入队，直到队列空为止。采用递归方法遍历。1.4.先序遍历二叉树若树不空，先访问根节点，其次访问左子树，最后访问右子树。 采用非递归方法遍历。 2概要设计1）二叉树的构造算法先依序输入元素值，并存入数组nodelist中，再用函数一一插入二叉树的节点建立二叉树，节点的建立是将左子针指向左子树，右子针指向右子树。算法流程图如下：Insert_node(btree *root, int node):Node=>newpointer->data,Newpointer->

5、;lchild=nullNewpointer->rchild=nullCurrentpointer=rootParentpointer=currentpointerRoot=nullCurrentpointer=nullReturn newpointerY NNY12初始化，令插入结点为根指针，左右孩子为空存储目前结点指针存储父结点指针Parentpointer->data>nodeCurrentpointer->data>nodeCurrentpointer=currentpointer->lchildReturn rootCurrentpointer=c

6、urrentpointer->rchildParentpointer->lchild=newpointerParentpointer->rchild=newpointerNYYN21父结点大于插入结点目前结点大于插入结点create_btree(int data, int len):I=0,btree *root=nullRoot=insert_node()I+I<lenReturn root YN调用insert_node()函数2）层序遍历二叉树：算法流程图如下：Front=0,rear=0Vecrear=root,rear+Root=queue.vecfront,

7、front+Root=nullFront<rear输出root->dataYN结束12建立一个队列，队列为空根指针进队队首元素出队Root->rchild=null输出root->lchild->dataRear+,vecrear=root->lchildRoot->rcild=null输出root->rchild=nullVecrear=root->rchild,rear+结束12NNY3）先序遍历二叉树：算法流程图如下：Btree*p,*s100Top=0P=stop-P=p->rchilds+top=pp=p->lchil

8、d(p!=null)|(top>0)输出p->data结束P=null NYYNtop为栈顶指针5）主函数流程图：开始结束Btree*root=null,nodelist20,index=0输入value Nodelistindex=valueIndex+Root=create_btree(nodelist,index)输入value Preorder()Levelorder()Value=0N N N Y层序遍历前序遍历建立一维数组存取结点值输入各个结点以0为结束符建立二叉树3详细设计#include<stdlib.h>#include<stdio.h>T

9、ypedef struct btnode Int data; Struct btnode *lchild,*rchild; bitree;Bitree *insert_node(bitree *root,char node) /插入二叉树的节点bitree *newpointer; /根指针bitree *currentpointer; /目前节点指针 bitree *parentpointer; /父节点指针 Newpointer=(bitree *)malloc(sizeof(bitree); Newpointer->data=node;Newpointer->lchild=n

10、ull;Newpoiter->rchild=null;If(root=null) /当结点为空时return newpointer;Else Currentpointer=root; /存储目前节点的指针While(currentpointer!=null) parentpointer=currentpointer; /存储父节点的指针If(currentpointer->data>node) /当目前结点大于插入结点时currentpointer=currentpointer->lchild; /目前结点的左孩子赋为目前结点Elsecurrentpointer=cur

11、rentpointer->rchild; /右子树If(parentpointer->data>node) /当父结点大于插入结点parentpointer->lchild=newpointer;Else parentpointer->rchild=newpointer;Return root;Bitree *creatr_bittree(char data,int len) /建立二叉树 Int I;Bitree *root=null;For(i=0;i<len;i+)Root=insert_node(root,datai); /调用insert_node

12、()函数Return root;Void preorder(bitree *root) /前序非递归遍历二叉树 Bitree *p,*s100;Int top=0; / top为栈顶指针p=root;While(p!=null)|(top>0) While(p!=null)printf(“%d”,p->data);S+top=p;P=p->lchild;P=stop-;P=p->rchild;Void levelorder(bitree *root) /层序递归遍历二叉树 Struct nodebitree *vec100;Int front,rear;queue; /

13、队列Queue.front=0;Queue.rear=0; /队列为空If(root!=null)Printf(“%d”,root->data);Queue.vecqueue.rear=root; /根指针进队Queue.rear+;While(queue.front<queue.rear) /队列非空 Root=queue.vecqueue.front; /队首元素出队Queue.front+;If(root->lchild!=null)printf(“%d”,root->lchild->data);Queue.vecqueue.rear=root->lc

14、hild;Queue.rear+;If(root->rchild!=null)printf(“%d”,root->rchild->dara);Queue.vecqueue.rear=root->rchild;Queue.rear+;Main()bitree *root=null; /建立bitree型结点rootInt value,index,nodelist20; /建立数组nodelist存放结点值Printf(“please input data:n”);Index=0;Scanf(“%d”,&value); /输入结点值While(value!=0)No

15、delistindex=value;Index+;Scanf(“%d”,&value); Root=create_bitree(nodelist,index); /创建二叉树Printf(“the tree is already createdn”);Printf(“n”);Printf(“the result after levelorder processing”); Levelorder(root) /层序遍历二叉树Printf(“n”);Printf(“theresult after Preorder processing”); Preorder(root); /先序遍历二叉树

16、4调试分析编译后，有多处错误，都是一些输入性错误，经改正后，编译成功，运行正确。测试数据如下：以0为结束符原数据为：7 5 3 8 9 4 2 0建立的二叉树为： 75 83 9 2 4层序遍历为：7 5 8 3 9 2 4先序遍历为： 7 5 3 2 4 8 9时间复杂度分析：层序遍历采用递归算法，时间复杂度为O(n)；先序采用非递归算法，时间复杂度为O(n) 5.课设总结二叉树是一种非常重要的数据结构，几乎任何数据结构都可以用二叉树来表示，二叉树的衍生结构可以应用于很多结构描述上，因此熟练的掌握二叉树的操作方法，对实际程序编写有很大促进，对锻炼自己的算法意识也有好处。我总结了以下几点：1）二叉树的定义是递归的，所以二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成。2）采用二叉链表存储，链表的头指针指向二叉树的根结点，在含有n个节点的二叉链表中有 n+1个空链域3）二叉树的遍历有先序，中序后序层序 等 从递归执行的角度来看，先序，中序后序是完全相同的，对含n个结点的二叉树，其时间算法复杂度为O(n),所需辅助空间为遍历过程中占的最大容量，即树的深度，则空间复杂度也为O(n) 4）递归算法与非递归算法的差异: 从递归角度来看， 递归操作隐式地调用系统栈，使时间和空