树转换成二叉树,树的前序、后序的递归、非递归和层次序的非递归.doc

#include #include #include #define MAX_TREE_SIZE 100typedef struct int data; int parent; /双亲位置域PTNode;/*双亲表示法树结构*/typedef struct PTNode nodeMAX_TREE_SIZE; int count; /根的位置和节点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct nodeint data;struct node *firstchild;struct node *rightsib;BTNode,*BTree;void init_ptree(PTree *tree) tree-count=-1;/初始化树结点(孩子兄弟表示法)BTNode GetTreeNode(int x)BTNode t;t.data=x;t.firstchild=t.rightsib=NULL;return t;/树的前序遍历(递归)void preorder(BTNode *T)if(T!=NULL)printf(%d ,T-data);preorder(T-firstchild);preorder(T-rightsib);/树的前序遍历(非递归)void preorder2(PTree T)int i;for(i=0;ifirstchild);printf(%d ,T-data);inoeder(T-rightsib);/树后序遍历(非递归)void inoeder2(PTree T)int i;for(i=T.count-1;i=0;i-)printf(%d ,T.nodei);/层次遍历void level(PTree T)int i;for(i=0;irightsib,level+1); for(i=1;idata); PrintBTree(root-firstchild,level+1); /输出树void print_ptree(PTree tree) int i; printf( 序号 结点 双亲n); for(i=0;i=tree.count;i+) printf(%8d%8d%8d,i,tree.nodei.data,tree.nodei.parent); printf(n); /*用双亲表示法创建树*/PTree CreatTree(PTree T)int i=1;int fa,ch;PTNode p;for(i=1;ch!=-1;i+)printf(输入第%d结点:n,i);scanf(%d,%d,&fa,&ch);printf(n);p.data=ch;p.parent=fa;T.count+; T.nodeT.count.data = p.data; T.nodeT.count.parent = p.parent;printf(n);printf(创建的树具体情况如下:n);print_ptree(T);return T;/*一般树转换成二叉树*/BTNode *change(PTree T)int i,j=0;BTNode pMAX_TREE_SIZE;BTNode *ip,*is,*ir,*Tree;ip=(BTNode *)malloc(sizeof(BTNode);is=(BTNode *)malloc(sizeof(BTNode);ir=(BTNode *)malloc(sizeof(BTNode);Tree=(BTNode *)malloc(sizeof(BTNode);for(i=0;iT.count;i+)pi=GetTreeNode(T.nodei.data);for(i=1;idata)j+;is=&pj;if(!(is-firstchild)is-firstchild=ip;ir=ip;elseir-rightsib=ip;ir=ip;Tree=&p0;return Tree;/*主菜单*/void Menu()printf(=主菜单=n);printf(*输入1-以双亲法创建一棵一般树*n); printf(*输入2-树的前序遍历(递归)*n); printf(*输入3-树的后序遍历(递归)*n); printf(*输入4-树的前序遍历(非递归)*n); printf(*输入5-树的后序遍历(非递归)*n); printf(*输入6-层次序的非递归遍历*n); printf(*输入0-退出程序*n); printf(=n); printf(请输入执行的指令:);/*副菜单*/void Menu2()printf(*副菜单*n);printf(*9-返回主菜单继续操作*n);printf(*0-退出程序*n);/*主函数*/void main() int i=0,c1,c2; PTree T; BTNode *Tree; init_ptree(&T); loop: Menu();scanf(%d,&c1); switch(c1) case 1: printf(建立一般树,依次输入各个结点情况:n); printf(输入结点方式:双亲数据,整型数据(第一个结点双亲数据为-1,最后以-1,-1结束)n例子:-1,1 1,3n);T=CreatTree(T);Tree=change(T);printf(一般树转换成二叉树后的情况:n);PrintBTree(Tree,i);getchar(); break; case 2: printf(树的前序遍历(递归):n); preorder(Tree); printf(n); break; case 3: printf(树的后序遍历(递归):n); inoeder(Tree); printf(n); break; case 4: printf(树的前序遍历(非递归):n); preorder2(T); printf(n); break; case 5: printf(树的后序遍历(非递归):n); inoeder2(T); printf(n); break; case 6: pri