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

- - PAGE - -可修编- 数据构造课程设计 ?数据构造?课程设计报告 设计题目：_树与二叉树的转换___ XX：_______李锦_____________ 学号：________211214011_______ 专业：_______物联网工程_______ 院系：_______计算机科学与技术_______ 班级：__________1205___________ 指导教师：_________高秀梅______ 2014年 2 月 目录 TOC \o 1-3 \h \z \u 一、问题描述 2 二、根本要求 2 三、概要设计 2 四、数据构造设计 2 五、算法设计 3 1、算法分析 3 2、算法实现 3 六、程序测试与实现 6 1、函数之间的调用关系 6 2、主程序 6 3、测试数据 8 4、测试结果 8 七、调试分析 10 八、遇到的问题及解决方法 10 九、心得体会 10 一、问题描述 完成树与二叉树的转换 二、根本要求 树采用双亲表示法 能够将树转换为二叉树 对转换的二叉树进展算法设计统计人一结点的孩子数 利用转换的二叉树计算树的高度 三、概要设计 操作集合： (1) CTreeNode *SearchCTree(CTreeNode *root ,char data) 查找树结点 (2) CTreeNode *CreateSTree() 生成树 (3) void preorderTree(CTreeNode *ctroot) 树的遍历 (4) void PrintTree(CTreeNode *troot,int depth) 树的输出 (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 *children[DEGREE];//指向孩子节点的指针域 }; struct BTreeNode { char data;//数据域 BTreeNode *lchild,*rchild;//左右孩子节点的指针 }; //树队列构造体类型 struct QueueCTree { CTreeNode *CTreeArray[MAX_NODE_NUM];//构造体指针数组，存放节点的地址 //struct nodeCTree *next; int CTreeFront,CTreeRear; }; //二叉树队列构造类型 struct QueueBTree { BTreeNode *BTreeArray[MAX_NODE_NUM];//构造体指针数组，存放节点的地址 //struct nodeBTree *next; int BTreeFront,BTreeRear; }; 五、算法设计 1、算法分析 将树转换成二叉树的步骤是： 〔1〕加线。就是在所有兄弟结点之间加一条连线； 〔2〕抹线。就是对树中的每个结点，只保存他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线； 〔3〕旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之构造层次清楚。 2、算法实现 void TreeToBTree(CTreeNode *ctroot,BTreeNode *btroot)//树转化为二叉树ctroot指向树的根节点，btroot,指向二叉树的跟 { QueueCTree *VisitedCTreeNodes; QueueBTree *VisitedBTreeNodes;//辅助队列 initQueueCTree(VisitedCTreeNodes); initQue