数据结构课程设计----二叉树的应用.doc

信息科学与技术学院 数据结构课程设计报告 题目名称： 二叉树的应用 专业班级： 计算机科学与技术 目 录 1、课程设计的目的、课程设计题目、题目要求 2 1.1课程设计的目的 3 1.2课程设计的题目 3 1.3题目要求 3 2课程设计的实验报告内容: 4 3课程设计的原程序代码: 4 4运行结果 16 5. 课程设计总结 21 6参考书目 22 1课程设计的目的 1.1课程设计的目的: 通过以前的学习以及查看相关资料,按着题目要求编写程序,进一步加强对编程的训练,使得自己掌握一些将书本知识转化为实际应用当中.在整个程序中,主要应用的是链表,但是也运用了类.通过两种方法解决现有问题. 1.2课程设计的题目: 二叉树的应用 1.3题目要求: 建立二叉树的二叉链表存储算法 二叉树的先序遍历，中序遍历和后序遍历输出 非递归的先序遍历，中序遍历 二叉树的层次遍历 判断此二叉树是否是完全二叉树 二叉树的左右孩子的交换 2课程设计的实验报告内容: 通过递归对二叉树进行遍历。二叉树的非递归遍历主要采用利用队进行遍历。此后的判断此二叉树是否是完全二叉树也才采用队，而二叉树的左右孩子的交换则采用的是一个简单的递归。 3课程设计的原程序代码: #includeiostream using namespace std; #define MAXSIZE 100 int sign=0; void menu(); // typedef struct BiTNode { char data; BiTNode *left_child,*right_child; }BiTNode,*BiTree; int CreateBiTree(BiTree T) //创建二叉树 { char ch; cout请输入数据（#为结束）: ; cinch; if(ch==#) T=NULL; else { if(!(T=new BiTNode)){ coutOverflow!; //no alloction return 0; } T-data=ch; CreateBiTree(T-left_child); //create leftchild CreateBiTree(T-right_child); //create rightchild } return 1; } //判断此树是否是完全二叉树 int LevelOrder1(BiTree T) { BiTree stack[MAXSIZE]; BiTree p; int front,rear; front=-1,rear=0; stack[rear]=T; while(rear!=front) { front++; p=stack[front]; if((p-left_child==NULL)(p-right_child)) sign=1; if(p-left_child) { rear++; stack[rear]=p-left_child; } if(p-right_child) { rear++; stack[rear]=p-right_child; } } return 1; } void Output(BiTree T) //输出二叉树 { if(!T) { cout空树!\n; return ; } //空树 coutT-data ;// 输出根结点 if(T-left_child) Output(T-left_child); //输出左子树 if(T-right_child)Output(T-right_child);//输出右子树 } int Depth(BiTree T) //求树深 { int i,j; if(!T) return 0; i = Depth(T-left_child); j = Depth(T-right_child); return (ij?i:j) + 1; } int Node(BiTree T)//求结点数 { if(!T) return 0; return 1+Node(T-left_child)+Node(T-right_child); } int Leaf(BiTree T) //求叶子结点 { if(!T) return 0; if(!T-left_child!T-right_child) return 1;//仅有根结点 retur