数据结构课程设计二叉树的创建和遍历.doc

安徽工程大学数据结构课程设计说明书学生姓名: 刘超学号: 3120702109 学院: 计算机与信息学院专业: 信息与计算科学题目: 二叉树的创建和遍历指导教师潘海玉 201 4年8月25日目录 1. 需求分析----------------------- 1 2. 概要设计----------------------- 1 3. 详细设计----------------------- 3 4. 调试分析----------------------- 9 5. 课程总结----------------------- 10 6. 附录----------------------- 12 第 1页 1. 需求分析问题描述: 根据运行时输入的先序序列, 创建一棵二叉树, 分别对其进行先序、中序、后序、层序遍历,并显示遍历结果。 void CreateBTree(BTree &T) // 按先序次序输入, 构造二叉树 void PreOrder(BTree T) // 递归先序遍历 void InOrder(BTree T) // 递归中序遍历 void PostOrder(BTree T) // 递归后序遍历 void LevelOrder(BTree T) // 层序遍历 void NRPreOrder(BTree bt) // 非递归先序遍历 void NRInOrder(BTree bt) // 非递归中序遍历 void NRPostOrder(BTree bt) // 非递归后序遍历 void main() // 二叉树的建立与遍历实现 2. 概要设计此次课程设计遍历算法的框架图遍历算法递归遍历非递归遍历先序遍历中序遍历后序遍历先序遍历中序遍历后序遍历层序遍历第 2页此次课程设计所用的三组二叉树本设计所使用的存储结构: typedef char ElemType;// 定义二叉树结点值的类型为字符型 typedef struct bnode{// 二叉链表结构定义 ElemType data; struct bnode *lchild,*rchild; }Bnode,* BTree; typedef struct { BTree ptr; int tag; ABD CFH G EF A BD C A B F EG CDH E第 3页}stacknode; 3. 详细设计 void CreateBTree(BTree &T){// 按先序次序输入, 构造二叉链表表示的二叉树 T,# 表示空树 char ch; ch=getchar(); if(ch=='#') T=NULL;// 读入# 时,将相应节点指针置空 else{ if(!(T=(Bnode *)malloc(sizeof(Bnode)))) printf(" 创建失败!");// 生成结点空间 T->data=ch; CreateBTree(T->lchild);// 构造二叉树的左子树 CreateBTree(T->rchild);// 构造二叉树的右子树}} void PreOrder(BTree T){// 递归先序遍历 if(T){ printf("%c ",T->data); PreOrder(T->lchild); PreOrder(T->rchild); 第 4页}} void InOrder(BTree T){// 递归中序遍历 if(T){ InOrder(T->lchild); printf("%c ",T->data); InOrder(T->rchild); }} void PostOrder(BTree T){// 递归后序遍历 if(T){ PostOrder(T->lchild); PostOrder(T->rchild); printf("%c ",T->data); }} void LevelOrder(BTree T){// 层序遍历 BTree Q[MAX]; int front=0,rear=0; 第 5页 BTree p; if(T){ // 根结点入队 Q[rear]=T; rear=(rear+1)%MAX; } while(front!=rear){ p=Q[front]; // 队头元素出队 front=(front+1)%MAX; printf("%c ",p->data); if(p->lchild){ // 左孩子不为空,入队 Q[rear]=p->lchild; rear=(rear+1)%MAX; } if(p->rchild){ // 右孩子不为空,入队 Q[rear]=p->rchild; rear=(rear+1)%MAX; }}} void NRPreOrder(BTree bt){// 非递归先序