数据结构实训报告

目课程设计目 课程设计目 课程设计任 课程设计要 分析与设 题目需求分 结构设 算法描 程序流程 测试程序说 程序测 测试数 分 总 参考文 运用树特别是二叉树根据树的相关概念了解树的方法和算法及应用以及二叉树的方法、遍历、算法和应用。同时在此基础上对树和二叉树的转换的实现进行编程掌握。这次课程设计的目标是通过这次的课程设计，能够使在数的训练培养工作所需要的动手能力熟练的掌握数据结构有关知识的应用，分析树和二叉树的结构，二叉树的结构如图2.1图2.1二叉树的结构有三种结构，即双亲表示法、孩子表示法、和孩子兄弟表示法。事实上一棵树采用孩子兄弟表示法所建立的结构与它所对应的二叉树的二叉链表结构是完全相同的，只是两个指针域的名称及解释不同而已,通2.2123、层次调整：以根结点为，将整棵树旋转，使之层次分明2.4一般树的结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。具体结构如下typedefstructst1/{chardata;//charstructst1*children[DEGREE];/typedefstructst2{chardata;//structst2*lchild,*rchild;/voidpreorderTree(CTreeNode{CTreeNode*ctchild;inti; }}

voidPreorder(BTreeNode*T){{cout<<T->data<<"";Preorder(T-}}CTreeNode*CreateSTree(parentNode=SearchCTree(root,parent)查找指定数据的结点。CTreeNode*CreateSTree(){intchardata,CTreeNode*root,*parentNode,*node;returnNULL;//空树，结束函数root=(CTreeNode*)malloc(sizeof(CTreeNode));{node=(CTreeNode*)malloc(sizeof(CTreeNode));{if(parentNode-{}}}return}*CTreeArray[MAX_NODE_NUMtypedefstructnodeCTree{CTreeNode*CTreeArray[MAX_NODE_NUM];intCTreeFront,CTreeRear;typedefstruct{BTreeNode*BTreeArray[MAX_NODE_NUM];intBTreeFront,BTreeRear;下面是将树转换为二叉树的主要程序段，ctroot一直向右，遇到的右均依次作为树的(二叉树中结点的右中变为该voidTreeToBTree(CTreeNode*ctroot,BTreeNode{QueueCTree*VisitedCTreeNodes;QueueBTree*VisitedBTreeNodes;//辅助队列initQueueCTree(VisitedCTreeNodes);CTreeNode*ctnode;BTreeNode*btnode,*p,*LastSibling;inti;btroot=(BTreeNode*)malloc(sizeof(BTreeNode)); {{p=(BTreeNode*)malloc(sizeof(BTreeNode));

btnode-LastSibling-}}usingnamespacestd;#defineDEGREE5#defineNULL0#defineQUEUESIZE#defineMAX_NODE_NUMtypedefstructst1//树结点的类{chardata;//数据域，采用charstructst1*children[DEGREE]typedefstructst2{chardatastructst2*lchild,*rchild;/CTreeNode*SearchCTree(CTreeNode*root,char{intCTreeNode*returnNode;returnroot;{{returnNULL;{return}}}}CTreeNode{intchardata,CTreeNode*root,*parentNode,*node;returnNULL;//空树，结束函数root=(CTreeNode*)malloc(sizeof(CTreeNode));{cin>>data>>parent;//切记当以%c格式输入数据时候，不要输入空格node=(CTreeNode*)malloc(sizeof(CTreeNode));//printf("验证parent=%c\n",parent);{{}}}return}voidpreorderTree(CTreeNode*ctroot)//遍历每个节点的操作就是输出该结点的data{CTreeNode*ctchild;inti;cout<<ctroot->data<<"";//先遍历根结点{}}typedefstructnodeCTree{//structnodeCTree*next;int}typedefstructnodeBTree{//structnodeBTree*next;intvoidinitQueueCTree(QueueCTree{q=(QueueCTree*)malloc(sizeof(QueueCTree));}voidinitQueueBTree(QueueBTree{q=(QueueBTree*)malloc(sizeof(QueueBTree));}intaddQueueCTree(QueueCTree*&q,CTreeNode{return0;return1;//入队}intaddQueueBTree(QueueBTree*&q,BTreeNode{return0;return1;//入队}intQueueCTreeEmpty(QueueCTree{}intQueueBTreeEmpty(QueueBTree{}CTreeNode*delQueueCTree(QueueCTree{CTreeNodereturnNULL;//返回空指针returnctroot;//返回结}BTreeNode*delQueueBTree(QueueBTree{BTreeNodereturnNULL;//返回空指针returnbtroot;//返回节}voidTreeToBTree(CTreeNode*ctroot,BTreeNode*&btroot)//树转化为二叉树ctroot{QueueCTree*VisitedCTreeNodes;QueueBTree*VisitedBTreeNodes;//辅助队列CTreeNode*ctnode;BTreeNode*btnode,*p,*LastSibling;inti;btroot=(BTreeNode*)malloc(sizeof(BTreeNode));//添加开辟内存空间语句{{p=(BTreeNode*)malloc(sizeof(BTreeNode));//分配二叉树结 }}}voidPreorder(BTreeNode{{cout<<T->data<<"";}}int{CTreeNode*Tree;BTreeNode*BTree;return0;}树的先序遍历结果：bac