数据结构课程设计树与二叉树的转换.docx

《数据结构课程设计树与二叉树的转换.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计树与二叉树的转换.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计树与二叉树的转换 数据结构课程设计报告 设计题目：_树与二叉树的转换_ 姓名：_李锦_ 学号：_211214011_ 专业：_物联网工程_ 院系：_计算机科学与技术_ 班级：_1205_ 指导教师：_高秀梅_ 2022年 2 月14 日 目录 一、问题描述 (2) 二、基本要求 (2) 三、概要设计 (2) 四、数据结构设计 (2) 五、算法设计 (3) 1、算法分析 (3) 2、算法实现 (3) 六、程序测试与实现 (6) 1、函数之间的调用关系 (6) 2、主程序 (6) 3、测试数据 (8) 4、测试结果 (8) 七、调试分析 (10) 八、遇到的问题及解决办法 (10)

2、 九、心得体会 (10) 一、问题描述 完成树与二叉树的转换 二、基本要求 1、树采用双亲表示法 2、能够将树转换为二叉树 3、对转换的二叉树进行算法设计统计人一结点的孩子数 4、利用转换的二叉树计算树的高度 三、概要设计 操作集合： (1) CTreeNode *SearchCTree(CTreeNode *root ,char data) 查找树结点 (2) CTreeNode *CreateSTree() 生成树 (3) void preorderTree(CTreeNode *ctroot) 树的遍历 (4) void PrintTree(CTreeNode *troot,int de

3、pth) 树的输出 (5 void initQueueCTree(QueueCTree *&q) 初始化树队列 (6) void initQueueBTree(QueueBTree *&q) 初始化二叉树队列 （7）void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot) /树转化为二叉树ctroot指向树的根节点，btroot,指向二叉树的根 四、数据结构设计 struct CTreeNode/树节点的类型 char data;/数据域，采用char星 struct CTreeNode *childrenDEGREE;/指向孩子节点的指针域

4、 ; struct BTreeNode char data;/数据域 BTreeNode *lchild,*rchild;/左右孩子节点的指针 ; /树队列结构体类型 struct QueueCTree CTreeNode *CTreeArrayMAX_NODE_NUM;/结构体指针数组，存放节点的地址 /struct nodeCTree *next; int CTreeFront,CTreeRear; ; /二叉树队列结构类型 struct QueueBTree BTreeNode *BTreeArrayMAX_NODE_NUM;/结构体指针数组，存放节点的地址 /struct nodeBT

5、ree *next; int BTreeFront,BTreeRear; ; 五、算法设计 1、算法分析 将树转换成二叉树的步骤是：（1）加线。就是在所有兄弟结点之间加一条连线；（2）抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；（3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。 2、算法实现 void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)/树转化为二叉树ctroot 指向树的根节点，btroot,指向二叉树的跟 QueueCTree *Visited

6、CTreeNodes; QueueBTree *VisitedBTreeNodes;/辅助队列 initQueueCTree(VisitedCTreeNodes); initQueueBTree(VisitedBTreeNodes);/初始化队列 CTreeNode *ctnode; BTreeNode *btnode,*p,*LastSibling; int i; btroot=new BTreeNode;/添加开辟内存空间语句 btroot-data=ctroot-data;/树的根节点作为二叉树的根节点 btroot-lchild=btroot-rchild=NULL; addQueue

7、CTree(VisitedCTreeNodes,ctroot);/树的跟节点入队 addQueueBTree(VisitedBTreeNodes,btroot);/二叉树的跟节点入队 while(!QueueCTreeEmpty(VisitedCTreeNodes) ctnode=delQueueCTree(VisitedCTreeNodes);/树节点出队 btnode=delQueueBTree(VisitedBTreeNodes);/二叉树节点出队 for(i=0;ichildreni=NULL)/孩子节点访问完毕 break; p=new BTreeNode;/分配二叉树节点 p-data=ctnode-childreni-data; p-lchild=p-rchild=NULL; if(i=0) btnode-lchild=p;/长子，作为父节点的做孩子 else LastSibling-rchild=p;/作为上一个兄弟节点的右孩子 LastSibling=p; addQueueCTree(VisitedCTreeNodes,ctnode-childreni);/树节点进队列 addQueueBTree(VisitedBTreeNodes,p);/二叉树节点进门队列 3、算法流程图 六、程序测试与实现 1、函数之间的调用关系