// 此代码为 多叉树转化为 二叉树并且二叉树转化为多叉树的代码



#include "stdafx.h"
#include <vector>
#include <iostream>



//  树的结点分布信息
struct SCreateNormalTree
{
      int nData ;
      int nPrev ;   //
 -1 为跟结点
};



const static int _NORMAL_TREE_NODE_NUM_ =
 9;
SCreateNormalTree createNormalTreeMap [_NORMAL_TREE_NODE_NUM_];



void CreateNormalTreeMap()
{
      createNormalTreeMap[0].nData = 
 5;
      createNormalTreeMap[0].nPrev =
 -1;



      createNormalTreeMap[1].nData = 
 3;
      createNormalTreeMap[1].nPrev = 
 5;



      createNormalTreeMap[2].nData = 
 4;
      createNormalTreeMap[2].nPrev = 
 5;



      createNormalTreeMap[3].nData = 
 2;
      createNormalTreeMap[3].nPrev = 
 5;



      createNormalTreeMap[4].nData = 
 8;
      createNormalTreeMap[4].nPrev = 
 3;



      createNormalTreeMap[5].nData =
 10;
      createNormalTreeMap[5].nPrev = 
 3;



      createNormalTreeMap[6].nData =
 11;
      createNormalTreeMap[6].nPrev = 
 3;



      createNormalTreeMap[7].nData =
 12;
      createNormalTreeMap[7].nPrev = 
 2;



      createNormalTreeMap[8].nData =
 100;
      createNormalTreeMap[8].nPrev =  
 5;
}
// 树的结点分布信息






// 多叉树
struct SNormalTreeNode
{
      int nData ;                                   //  元素的值
      SNormalTreeNode* pParent ;                    //　双亲结点
      std::vector <SNormalTreeNode*> vecChildNode;  //  孩子结点
};









struct SBinaryTreeNode      // 二叉孩子兄弟链表                   
{
      int nData ;                                  //  元素的值
      SBinaryTreeNode* pParent ;                   //　双亲结点
      SBinaryTreeNode* pFirstChild ;               //  孩子结点 ( 左孩子 )
      SBinaryTreeNode* pSibling ;                  //  兄弟结点 ( 右兄弟 )
};






SNormalTreeNode * InitializeNormalTree(
 );
SNormalTreeNode * InsertValueToNormalTree( SNormalTreeNode * pRoot, int nValue , int nParent );
SNormalTreeNode * FindNodeByValue( SNormalTreeNode* pRoot , int nValue );
void TravarseNormalTree( SNormalTreeNode* pRoot );



// 多叉树转化为二叉树
SBinaryTreeNode * GetBinary( SNormalTreeNode* pNormalTree );
void ConvertNormalToBinary( SBinaryTreeNode * pBinaryTree, SNormalTreeNode * pNormalTree );
void InOrderBinaryTree( SBinaryTreeNode* pBinaryTree );



// 同时将二叉树转化为多叉树
SNormalTreeNode * GetNormalTreeFromBinary( SBinaryTreeNode * pBinaryTree );
void   ConvertFromBinaryToNormal( SBinaryTreeNode * pBinaryTree , SNormalTreeNode* pNormalTree );






int _tmain( int argc , _TCHAR* argv[])
{
      CreateNormalTreeMap();
      SNormalTreeNode*  pNormalTree = InitializeNormalTree ();
      TravarseNormalTree( pNormalTree );



      SBinaryTreeNode* pBinaryTree = GetBinary( pNormalTree );
      InOrderBinaryTree( pBinaryTree );



      SNormalTreeNode*  pConvertNormal = GetNormalTreeFromBinary ( pBinaryTree );
      TravarseNormalTree( pConvertNormal );



      system( "pause" );
      return 0;
}



SNormalTreeNode *  InitializeNormalTree()   // 多叉树 InitializeNormalTree()
{
      SNormalTreeNode* pNormalTree = NULL;
     
      for( int i =
 0; i < _NORMAL_TREE_NODE_NUM_ ;
 ++i )
     {
           pNormalTree = InsertValueToNormalTree ( pNormalTree , createNormalTreeMap[ i].nData , createNormalTreeMap [i]. nPrev );
     }



      return pNormalTree ;
}



SNormalTreeNode * InsertValueToNormalTree( SNormalTreeNode * pRoot, int nValue , int nParent )
{
      if(
 !pRoot )
     {
           if( nParent !=
 -1 )
          {
               return NULL ;
          }
     }



      if( nParent ==
 -1 )
     {
           pRoot = NULL ;
           pRoot = new SNormalTreeNode;
           pRoot->nData = nValue;
           pRoot->pParent = NULL;
     }
      else
     {
           if(
 !pRoot )
          {
               return NULL ;
          }



           SNormalTreeNode* pParent  
 = FindNodeByValue( pRoot, nParent );
           SNormalTreeNode* pNewNode = new SNormalTreeNode;
           pNewNode->nData   
 = nValue;
           pNewNode->pParent = pParent;
           pParent->vecChildNode .push_back( pNewNode );
     }



      return pRoot ;
}



SNormalTreeNode * FindNodeByValue( SNormalTreeNode* pRoot , int nValue )
{
      if(
 !pRoot )
           return NULL ;



      if( pRoot ->nData == nValue )
           return pRoot ;



      std::vector <SNormalTreeNode*>:: iterator iBegin = pRoot->vecChildNode .begin();
      std::vector <SNormalTreeNode*>:: iterator iEnd   
 = pRoot->vecChildNode .end();
      for(
 ; iBegin != iEnd;
 ++ iBegin )
     {
           SNormalTreeNode* pChildNode =
 (*iBegin);
           if( pChildNode )
          {
               if( pChildNode = FindNodeByValue( pChildNode , nValue )
 )
                    return pChildNode ;
          }
     }



      return NULL ;
}



void TravarseNormalTree( SNormalTreeNode* pRoot )
{
      if(
 !pRoot )
           return ;



      std::cout <<" 当前结点为 :
 "<<pRoot ->nData<< std::endl ;
      std::cout <<" 子结点为 :
 ";
      std::vector <SNormalTreeNode*>:: iterator iBegin = pRoot->vecChildNode .begin();
      std::vector <SNormalTreeNode*>:: iterator iEnd   
 = pRoot->vecChildNode .end();
      for(
 ; iBegin != iEnd;
 ++ iBegin )
     {
           SNormalTreeNode* pChild =
 (*iBegin);
           if( pChild )
               std::cout <<"   
 "<<pChild ->nData;
     }
      std::cout <<std:: endl;



      iBegin = pRoot ->vecChildNode. begin();
      for(
 ; iBegin != iEnd;
 ++ iBegin )
     {
           SNormalTreeNode* pChild =
 (*iBegin);
           if( pChild )
               TravarseNormalTree( pChild );
     }
}



SBinaryTreeNode * GetBinary( SNormalTreeNode* pNormalTree )
{
      if(
 !pNormalTree )
           return NULL ;



      // 根结点
      SBinaryTreeNode* pBinaryNewNode = new SBinaryTreeNode ;
      pBinaryNewNode->nData           
 = pNormalTree ->nData;
      pBinaryNewNode->pParent         
 = NULL;
      pBinaryNewNode->pSibling        
 = NULL;
      pBinaryNewNode->pFirstChild     
 = NULL;



      ConvertNormalToBinary ( pBinaryNewNode, pNormalTree );



      return pBinaryNewNode ;
}



void ConvertNormalToBinary( SBinaryTreeNode * pBinaryNode, SNormalTreeNode * pNormalTree )
{
      if(
 !pNormalTree ||
 !pBinaryNode )
           return ;



      SBinaryTreeNode* pFirstChild = NULL;
      std::vector <SNormalTreeNode*>:: iterator  iLeftChild    
 = pNormalTree ->vecChildNode. begin();
      std::vector <SNormalTreeNode*>:: iterator  iEnd          
 = pNormalTree ->vecChildNode. end();
      if( iLeftChild == iEnd )
           return ;
      else
     {
           SNormalTreeNode* pNormalSubTree =
 (*iLeftChild);
           pFirstChild = new SBinaryTreeNode;
           pFirstChild->nData       
 = pNormalSubTree ->nData;
           pFirstChild->pFirstChild = NULL;
           pFirstChild->pParent     
 = pBinaryNode;
           pFirstChild->pSibling    
 = NULL;



           pBinaryNode->pFirstChild = pFirstChild;
          
           ConvertNormalToBinary ( pFirstChild, pNormalSubTree );
     }



      std::vector <SNormalTreeNode*>:: iterator  iSiblingBegin = iLeftChild +
 1;
      if( iSiblingBegin == iEnd )
           return ;
      else
     {
           SBinaryTreeNode* pLinkNode = pFirstChild;
           for(
 ; iSiblingBegin != iEnd;
 ++ iSiblingBegin )
          {
               SNormalTreeNode* pSubBeginNormal =
 (*iSiblingBegin );



               SBinaryTreeNode* pNewBinaryNode = new SBinaryTreeNode ;
               pNewBinaryNode->nData = pSubBeginNormal ->nData;
               pNewBinaryNode->pFirstChild = NULL;
               pNewBinaryNode->pParent     
 = pLinkNode;
               pNewBinaryNode->pSibling    
 = NULL;
               pLinkNode->pSibling         
 = pNewBinaryNode ;



               ConvertNormalToBinary ( pNewBinaryNode, pSubBeginNormal );
               pLinkNode = pNewBinaryNode ;
          }
     }



}



void InOrderBinaryTree( SBinaryTreeNode* pBinaryTree )
{
      if(
 !pBinaryTree )
           return ;



      InOrderBinaryTree(pBinaryTree ->pFirstChild);



      SBinaryTreeNode* pParent = pBinaryTree-> pParent;
      if( pParent == NULL )
           std::cout <<"
 Root Node ";
      else
     {
           if( pParent ->pFirstChild == pBinaryTree )
               std::cout <<"
 ParentNode "<< pParent->nData <<"
 Left Child";
           else
               std::cout <<"
 ParentNode "<< pParent->nData <<"
 Right Child";
     }



      std::cout <<"
 node Value is"<< pBinaryTree->nData <<std:: endl;



     
      InOrderBinaryTree(pBinaryTree ->pSibling);
}



SNormalTreeNode * GetNormalTreeFromBinary( SBinaryTreeNode * pBinaryTree )
{
      if(
 !pBinaryTree )
           return NULL ;



      SNormalTreeNode* pRootNode = new SNormalTreeNode;
      pRootNode->nData   
 = pBinaryTree-> nData;
      pRootNode->pParent = NULL;



      ConvertFromBinaryToNormal ( pBinaryTree-> pFirstChild, pRootNode );



      return pRootNode ;
}



void ConvertFromBinaryToNormal( SBinaryTreeNode * pBinaryTree , SNormalTreeNode* pNormalTree )
{
      if(
 !pBinaryTree ||
 !pNormalTree )
           return ;



      do
     {
           SNormalTreeNode* pNormalBegin = new SNormalTreeNode ;
           pNormalBegin->nData   
 = pBinaryTree-> nData;
           pNormalBegin->pParent = pNormalTree;



           pNormalTree->vecChildNode .push_back( pNormalBegin );



           ConvertFromBinaryToNormal ( pBinaryTree ->pFirstChild, pNormalBegin );



           pBinaryTree = pBinaryTree ->pSibling;
     } while( pBinaryTree );



}






转化前的多叉树










转化后的二叉树










二叉树 再次 转化为 多叉树

多叉树转二叉树



int x,y;
scanf("%d%d",&x,&y);//x->y
Rson[y]=Lson[x];
Lson[x]=y;

今天复习树形dp时发现一道比较古老的题，叫选课，是树形dp的一道基础题，也是多叉树转二叉树应用的模版题
多叉树转二叉树的应用非常广泛，因为如果一个节点的儿子太多，一个一个存下来不方便去查询，并且会增加复杂度，但是这里我们就有一个O(n)的复杂度的方法把多叉树转换为二叉树，转换成二叉树后就更方便查询，因为每个节点最多就两个儿子节点，减少了复杂度并且让代码实现起来更容易
 
多叉树转二叉树图示：

在这张图中，右边那棵二叉树由左边的多叉树转换而来，并且这棵二叉树是竖着相连的是父子关系，横着相连的是兄弟关系，也就是左儿子，右兄弟
接着就是代码实现了，其实代码实现也有一些小小的技巧
比如我们要求输入a,b表示a是b的儿子
例子： 2 1 
           4 1
           3 1
如果我们按着顺序处理，那1的左儿子就是2,2的右儿子是4,4的右儿子是3，但是这样的话会有一点的麻烦，所以我们就不断的变更
方法：1的左儿子是2，读入第二行，4的右儿子就是当前1的左儿子节点2，然后1的左儿子变成4，读入第三行，3的右儿子是节点4，然后1的左儿子变成3
这种方法在代码上更加容易实现并且复杂度也要小一些
转换成代码就是

1 for(int i=1;i<=n;i++)
2 {
3      cin>>a>>b;
4      tree[a].right=tree[b].left;
5      tree[b].left=a;
6 }

View Code
代码就是这样，然后推荐一道模拟题，叫做选课，不过我还不知道出处，但是后面我会把这道题补到我的博客
转载于:https://www.cnblogs.com/Danzel-Aria233/p/7462403.html

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;
}