C语言练手.多叉树转二叉树
原理: 二叉树节点的左子树为对应多叉树节点的第一个孩子,右子树为多叉树中它的右兄弟,以此类推
#include <stdio.h> #include <stdlib.h> #define M 5 /* 多叉树最大子数量为5 */ typedef struct mtree_node { int val; struct mtree_node *subTree[M]; }MTREE_NODE; /* 多叉树结构 */ typedef struct btree_node { int val; struct btree_node *offspring; /* 左子树 */ struct btree_node *sibling; /* 右子树 */ }BTREE_NODE; /* 二叉树结构 */ static int to_btree(struct mtree_node *pmnode, struct btree_node *pbroot) { int i = 0; BTREE_NODE *ptmep; pbroot->val = pmnode->val; if (pmnode->subTree[0] == NULL) { pbroot->offspring = NULL; return 0; } BTREE_NODE *pbnode = (BTREE_NODE *)malloc(sizeof(BTREE_NODE)); pbroot->offspring = pbnode; to_btree(pmnode->subTree[0],pbnode); i = 1; ptmep = pbnode; while (i < M && pmnode->subTree[i] != NULL) { BTREE_NODE *pbnode = (BTREE_NODE *)malloc(sizeof(BTREE_NODE)); ptmep->sibling = pbnode; ptmep = pbnode; to_btree(pmnode->subTree[i],pbnode); i++; } ptmep->sibling = NULL; return 0; } static int btree_print(BTREE_NODE *proot) { BTREE_NODE *pnode = proot; printf("%d",pnode->val); if (pnode->offspring != NULL) { btree_print(pnode->offspring); } if (pnode->sibling != NULL) { btree_print(pnode->sibling); } free(proot); return 0; } int main (int args, char *argv[]) { MTREE_NODE *mtree; BTREE_NODE *btree; MTREE_NODE *mtemp; MTREE_NODE *mstemp; int i = 0; int j = 0; mtree = (MTREE_NODE *)malloc(sizeof(MTREE_NODE)); mtree->val = 0; /* 为了测试构建一颗多叉树 */ for (;i<3;i++) { mtemp = (MTREE_NODE *)malloc(sizeof(MTREE_NODE)); mtree->subTree[i] = mtemp; mtemp->val = i+1; for(j=0;i<2 && j<3;j++) { mstemp = (MTREE_NODE *)malloc(sizeof(MTREE_NODE)); mtemp->subTree[j] = mstemp; mstemp->val = j+4+3*i; } } if (mtree == NULL) { return 0; } btree = (BTREE_NODE *)malloc(sizeof(BTREE_NODE)); /* 可将任意多叉树转换成二叉树,参数为多叉树和二叉树的根节点 */ to_btree(mtree,btree); btree_print(btree); /* 前序遍历打印二叉树,测试用 */ return 0; }