精华内容
下载资源
问答
  • // 此代码为 多叉树转化为 二叉树并且二叉树转化为多叉树的代码 #include "stdafx.h" #include  #include  // 树的结点分布信息 struct SCreateNormalTree {  int nData ;  int nPrev...
    // 此代码为 多叉树转化为 二叉树并且二叉树转化为多叉树的代码

    #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 );

    }


    转化前的多叉树



    转化后的二叉树



    二叉树 再次 转化为 多叉树


    展开全文
  • 多叉树二叉树

    2018-05-16 17:52:12
    多叉树二叉树 int x,y; scanf("%d%d",&amp;x,&amp;y);//x-&gt;y Rson[y]=Lson[x]; Lson[x]=y;

    多叉树转二叉树

    int x,y;
    scanf("%d%d",&x,&y);//x->y
    Rson[y]=Lson[x];
    Lson[x]=y;
    展开全文
  • 今天复习树形dp时发现一道比较古老的题,叫选课,是树形dp的一道基础题,也是多叉树二叉树应用的模版题 多叉树二叉树的应用非常广泛,因为如果一个节点的儿子太多,一个一个存下来不方便去查询,并且会增加...

    今天复习树形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语言多叉树二叉树

    千次阅读 2016-12-05 19:25:13
    多叉树二叉树原理: 二叉树节点的左子树为对应多叉树节点的第一个孩子,右子树为多叉树中它的右兄弟,以此类推 #include #include #define M 5 /* 多叉树最大子数量为5 */ typedef struct mtree_node { int val;...

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

    展开全文
  • 多叉树的含义 多叉树即为子结点有任意个的树,而在转换时所涉及的多叉树是一棵有序的多叉树,也就是其子结点的顺序是不能够随便交换的。...而二叉树相对于多叉树便有了这些方面的优势,能够节省浪费...
  • POJ 3437 Tree Grafting 多叉树二叉树

    千次阅读 2014-02-22 09:56:33
    POJ 3437 Tree Grafting 多叉树二叉树
  • 多叉树二叉树 题目描述:: 截图可方便了 方法: 举个栗子,如图:: 好和谐啊 这是一棵多叉树 如何转化为二叉树?? 连接每一组兄弟,如图: 把右儿子断掉,如图: 然后再整理一下,就变成了: ...
  • 前言 先来讲讲我是怎么用四天的时间来做这道题的吧。 第一天:看老师的课件,了解了思路,并得知了状态转移方程是如何得出的。...第一,如果不用多叉树二叉树,此题真的会变得非常复杂,不信...
  • 选课 树形DP 多叉树二叉树

    千次阅读 2017-03-19 00:20:52
    选课&ndsp树形DP&ndsp多叉树二叉树 题目描述 学校实行学分制。每门的必修课都有固定的学分,同时还必须获得相应的选修课程学分。学校开设了N门的选修课程,每个学生可选课程的数量M是给定的。学生选修了这M门课并...
  • 多叉树转换二叉树

    2019-09-28 02:29:27
    多叉转二叉,前提是我们仍要把的信息保留下来,也就是谁是谁的孩子,谁是谁的兄弟。但是二叉只能保存两个孩子,但我们可以把两个孩子改成两个关系,也就是我们利用二叉来储存关系,一个是孩子,一个是兄弟。 于是...
  • (转自:多叉树转换二叉树 -~Lanly~ 原文日期:2017.01.19) 多叉转二叉,前提是我们仍要把树的信息保留下来,也就是谁是谁的孩子,谁是谁的兄弟。但是二叉只能保存两个孩子,但我们可以把两个孩子改成两个关系,...
  • 数据结构----树----多叉树二叉树

    千次阅读 2017-04-25 14:06:36
    一、多叉树二叉树的方法 1、输入一颗多叉树 2、找到根节点,把它除最左边的儿子以外的所有儿子的关系断掉 3、从左儿子开始,把同层的兄弟依次连接起来 4、然后对根节点的儿子依次递归进行次操作,...
  • 问这么一个多叉树的高度转为二叉树,这个二叉树的高度有多高 转二叉树的方法题目已经告诉你了: “左儿子,右兄弟” 就是将一个节点的第一个儿子放在左儿子的位置,下一个的儿子,即左儿子的第一个兄弟, 放在左儿子的右...
  • 2 多叉树二叉树的方法 1、输入一颗多叉树 2、找到根节点,把它除最左边的儿子以外的所有儿子的关系断掉 3 从左儿子开始,把同层的兄弟依次连接起来 4 然后对根节点的儿子依次递归进行次操作...
  • //lastchild[f]不等于0,创建兄弟,即右儿子 }//i每加一次就要创建一个左儿子或右儿子,意思是第i个元素是上一个元素(若是兄弟,则是i-1,若是父亲则f(f=nodes[i].parent))的左子树或者右子 } } void Preorder...
  • 关于如何把多叉树转化为二叉树,有个口诀,叫做左儿子不变,右儿子兄♂弟。 详细的不多说,可以去参考一下相关资料。 等转化为二叉树了过后,让我们来琢磨一下。 左儿子:原根节点的孩子。 右儿子:原根节点的兄 ♂...
  • poj3437 多叉树转为二叉树

    千次阅读 2014-04-01 12:51:19
    #include using namespace std; string s; int i,yuan,hou,len=1; void f(int yu,int ho){ int t=0; while(s[i]=='d'){ t++; i++; f(yu+1,ho+t); } yuan=yu>yuan? yu:yuan; hou=ho>hou?...}

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,971
精华内容 2,388
关键字:

多叉树和二叉树