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

《树转换成二叉树,树的前序、后序的递归、非递归和层次序的非递归》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#include#include#defineMAX_TREE_SIZE100typedefstruct{intdata;intparent;//双亲位置域}PTNode;/*双亲表示法树结构*/typedefstruct{PTNodenode[MAX_TREE_SIZE];intcount;//根的位置和节点个数}PTree;/*树的孩子兄弟表示结点结构定义*/typedefstructnode{intdata;structnode*firstchild;structnode*rightsib;}BTNo

2、de,*BTree;voidinit_ptree(PTree*tree){tree->count=-1;}//初始化树结点(孩子兄弟表示法)BTNodeGetTreeNode(intx){BTNodet;t.data=x;t.firstchild=t.rightsib=NULL;returnt;}//树的前序遍历(递归)voidpreorder(BTNode*T){if(T!=NULL){printf("%d",T->data);preorder(T->firstchild);preorder(T->rightsib);}}//树的前序遍历(非递归)voidpreorder2(P

3、TreeT){inti;for(i=0;ifirstchild);printf("%d",T->data);inoeder(T->rightsib);}}//树后序遍历(非递归)voidinoeder2(PTreeT){inti;for(i=T.count-1;i>=0;i--){printf("%d",T.node[i]);}}//层次遍历voidlevel(PTreeT){inti;for

4、(i=0;irightsib,level+1);for(i=1;i<=8*level;i++)printf("");printf("-------%d",root->data);PrintBTree(root->firstchild,level+1);}}//输出树voidprint_ptree(PTreetree){inti;prin

5、tf("序号结点双亲");for(i=0;i<=tree.count;i++){printf("%8d%8d%8d",i,tree.node[i].data,tree.node[i].parent);printf("");}}/*用双亲表示法创建树*/PTreeCreatTree(PTreeT){inti=1;intfa,ch;PTNodep;for(i=1;ch!=-1;i++){printf("输入第%d结点:",i);scanf("%d,%d",&fa,&ch);printf("");p.data=ch;p.parent=fa;T.count++;T.nod

6、e[T.count].data=p.data;T.node[T.count].parent=p.parent;}printf("");printf("创建的树具体情况如下:");print_ptree(T);returnT;}/*一般树转换成二叉树*/BTNode*change(PTreeT){inti,j=0;BTNodep[MAX_TREE_SIZE];BTNode*ip,*is,*ir,*Tree;ip=(BTNode*)malloc(sizeof(BTNode));is=(BTNode*)malloc(sizeof(BTNode));ir=(BTNode*)mal

7、loc(sizeof(BTNode));Tree=(BTNode*)malloc(sizeof(BTNode));for(i=0;idata){j++;is=&p[j];}if(!(is->firstchild)){is->firstchild=ip