树与二叉树的转换实现3.docxVIP

河南工程学院《数据结构与算法》课程设计成果报告 树与二叉树的转换实现2014年12月29日 2. 5测试程序说明 本次课程设计任务是完成树与二叉树的转换，将（a）树转换成二叉树其步 骤及过程如下： ⑴加线：就是在所有兄弟结点间加一条线;  (2)抹线：就是对树中的每个结点只保存它与左孩子结点之间的连线，删 除它与其它孩子结点之间的连线； (3)旋转：就是以树的根结点为轴心，将整棵树顺时针旋转45度，使二叉 树结构层次清楚。 三、程序清单 #include stdio.h #include malloc.h #include stdlib.h #define MaxSize 100 typedef char ElemType; 〃二叉树定义 typedef struct bnode { ElemType data;struct bnode *lchild; struct bnode *rchild; } bTNode,*bTree; 〃树的双亲表示结点结构定义 typedef struct { int data,parent;}PTNode; 〃双亲表示法树结构 typedef struct { PTNode node[MaxSize];int count; }PTree; 〃树的孩子兄弟表示结点结构定义 typedef struct node{int data; struct node *firstchild,*nextchild; } BTNode,*BTree;〃二叉链表的创立 BiTree* createTree(){ DataType ch; Bi tree *T; ch=getchar();if(ch==#)return NULL;} else{ T=(BiTree*)malloc(sizeof(BiTree)); T-data=ch; T-lchild=createB iT ree(); T-rchild=createBiTree(); return T;}}//树的前序遍历 void preorder (B TN ode *T) {if(T!=NULL){ printf(n%d H,T-data); preorder(T-firstchild);preorder(T-nextchild); }} 〃树后序遍历 void inoeder(BTNode *T) { if(T!二NULL){ inoeder(T-firstchild); printf(n%d H,T-data);inoeder(T-nextchild);}} 〃输出二叉树 void PrintBTree(BTNode *rootJnt level) { int i;if(root!=NULL) { PrintBTree(root-nextchildJevel+l);for(i= 1 ;i=8*level;i++) printf( )；printf(H %d\n M,root-data); PrintBTree(root-firstchild,level+l); }} 〃输出树 void print__ptree(PTree tree) { int i;printf(n 序号 结点 双亲\n”)； for(i=0;i=tree.count;i++){printf(H%8d%8d%8dn,i,tree.node[i].data,tree.node[i].parent); printf(H\nn); }} 〃用双亲表示法创立树 PTree CreatTree(PTree T) { int i=l;int fa,ch; PTNode p;printf(”请依次输入各节点(以数据域-1结束)：”)； for(i= 1 ;ch!-1 ;i++){ scanf(％d,%d”,fa,ch); printf(n\nn);p.data=ch; p.parent=fa;T.count++; T.node[T.count].data = p.data; T.nodc[T.count] .parent = p.parcnt; } printf(n\nn); printf(创立的树如下:\n)；print_ptree(T); return T;}io //一般树转换成二叉树 BTNode *change(PTree T){int i,j=0； BTNode p[MaxSize];BTNode *a,*b,*c,*Tree; a=(BTNode *)malloc(sizeof(BTNode));b=(BTNode *)malloc(sizeof(BTNode)); c=(BTNode *)malloc(sizeof(BTNode));Tree=(BTNode *)malloc