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

哈尔滨理工大学计算机学院 数据结构课程设计 建立二叉树 层序、先序遍历 班级：计05-1班 姓名：杨继伟 学号：0504110122 目录 1 需求分析 2 1.1题目分析 2 1.2二叉树构造模块 4 1.3层序遍历二叉树模块 4 1.4先序遍历二叉树模块 4 2 概要设计 4 2.1二叉树构造算法 4 2.2层序算法 7 2.3先序算法 9 3 详细设计 11 4 调试分析 15 5 课设总结 16 建立二叉树,层序、先序遍历 1需求分析: 1.1.题目： 建立二叉树，要求能够输入树的各个节点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储的输入函数，输出层序遍历序列的函数，输出 先序遍历序列的函数。 分析： 首先要输入元素建立二叉树，选择某一种存储结构存储二叉树，本程序采用二叉链表存储结构。由于二叉树的定义是递归的，因而一棵非空二叉树可以看作是由根结点、左子树和右子树这三个基本部分组成的。如果能依次遍历这三个部分的信息，也就遍历了整个二叉树。由此得到的二叉树的遍历是按某种策略访问二叉树中的每一个结点且仅访问一次的过程。 程序一共分为如下3个模块： 二叉树的构造: Insert_node(btree *root, int node) { …… } create_btree(int data[], int len) { …… } 层序遍历二叉树: Void levelorder(bitree *root) { …… } 先序遍历二叉树: Void preorder(bitree *root) { …… } 1.2.二叉树的构造 采用二叉链表存储结构建立二叉树, 二叉树的结点由一个数据元素和分别指向其左右子树的两个分支构成，即数据域和左、右指针域 lchild data rchild 数据结构： Typedef strcut bnode { Telemtype data; //结点数据类型 Struct bnode *lchild,*rchild; // 定义左右孩子为指针类型 }bnode,*btree; 其中Insert_node(btree *root, int node) 为插入二叉树结点函数，create_btree(int data[], int len)为建立二叉树函数 1.3.层序遍历二叉树 要采用一个队列。先将二叉树的根节点入队，然后退队，输出该节点，若它有左子树，便将左子树的根节点入队，若它有左子树，便将有子树的根节点入队，直到队列空为止。采用递归方法遍历。 1.4.先序遍历二叉树 若树不空，先访问根节点，其次访问左子树，最后访问右子树。 采用非递归方法遍历。 2．概要设计 1）二叉树的构造算法 先依序输入元素值，并存入数组nodelist中，再用函数一一插入二叉树的节点建立二叉树，节点的建立是将左子针指向左子树，右子针指向右子树 。 算法流程图如下： Insert_node(btree *root, int node): create_btree(int data[], int len): 2）层序遍历二叉树： 算法流程图如下： 3）先序遍历二叉树： 算法流程图如下： 5）主函数 流程图： 3．详细设计 #includestdlib.h #includestdio.h Typedef 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=null; Newpoiter-rchild=null; If(root==null) //当结点为空时 { return newpointer; }