二叉树的应用_数据结构课程设计

《二叉树的应用_数据结构课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、信息科学与技术学院数据结构课程设计报告题目名称：二叉树的应用专业班级：计算机科学与技术学生姓名：陈杰学生学号：200808261指导教师：高攀完成日期：2010-04目录1、课程设计的目的、课程设计题目、题目要求21.1课程设计的目的31.2课程设计的题目31.3题目要求32课程设计的实验报告内容:43课程设计的原程序代码:44运行结果165.课程设计总结216参考书目221课程设计的目的1.1课程设计的目的:通过以前的学习以及查看相关资料,按着题目要求编写程序,进一步加强对编程的训练,使得自己掌握一些将书本知识转化为实际应用当中.在整个程序中,主要应用的是链表

2、,但是也运用了类.通过两种方法解决现有问题.1.2课程设计的题目:二叉树的应用1.3题目要求:1.建立二叉树的二叉链表存储算法2.二叉树的先序遍历，中序遍历和后序遍历输出3.非递归的先序遍历，中序遍历4.二叉树的层次遍历5.判断此二叉树是否是完全二叉树6.二叉树的左右孩子的交换2课程设计的实验报告内容:7.通过递归对二叉树进行遍历。二叉树的非递归遍历主要采用利用队进行遍历。此后的判断此二叉树是否是完全二叉树也才采用队，而二叉树的左右孩子的交换则采用的是一个简单的递归。3课程设计的原程序代码:#includeusingnamespacestd;

3、#defineMAXSIZE100intsign=0;voidmenu();//typedefstructBiTNode{chardata;BiTNode*left_child,*right_child;}BiTNode,*BiTree;intCreateBiTree(BiTree&T)//创建二叉树{charch;cout<<"请输入数据（#为结束）:";cin>>ch;if(ch=='#')T=NULL;else{if(!(T=newBiTNode)){cout<<"Overflow!";//noalloctionreturn0;}T->data=ch;Cr

4、eateBiTree(T->left_child);//createleftchildCreateBiTree(T->right_child);//createrightchild}return1;}//判断此树是否是完全二叉树intLevelOrder1(BiTree&T){BiTreestack[MAXSIZE];BiTreep;intfront,rear;front=-1,rear=0;stack[rear]=T;while(rear!=front){front++;p=stack[front];if((p->left_child==NULL)&&(p->

5、right_child))sign=1;if(p->left_child){rear++;stack[rear]=p->left_child;}if(p->right_child){rear++;stack[rear]=p->right_child;}}return1;}voidOutput(BiTree&T)//输出二叉树{if(!T){cout<<"空树!";return;}//空树cout<data<<"";//输出根结点if(T->left_child)Output(T->left_child);//输出左子树if(T->right_chil

6、d)Output(T->right_child);//输出右子树}intDepth(BiTree&T)//求树深{inti,j;if(!T)return0;i=Depth(T->left_child);j=Depth(T->right_child);return(i>j?i:j)+1;}intNode(BiTree&T)//求结点数{if(!T)return0;return1+Node(T->left_child)+Node(T->right_child);}intLeaf(BiTree&T)//求叶子结点{if(!T)return0;if(!T->left_c

7、hild&&!T->right_child)return1;//仅有根结点returnLeaf(T->left_child)+Leaf(T->right_child);//返回叶子结点的数目}voidPreOrder(BiTree&T)//先序遍历算法DLR{if(!T)return;//递归调用的结束条件cout<data<<"";//访问根结点的数据域PreOrder(T->left_child);//先序递归遍历T的左子树PreOrder(T->right_child);//先序递归遍历T的右子树}voidInOrder(BiTree&T)//中序

8、遍历算法LDR{if(!