精华内容
下载资源
问答
  • 多叉树转换为二叉树
    2021-03-15 19:56:20

    方法:将多叉树的第一个儿子结点作为二叉树的左结点,将其兄弟结点作为二叉树的右结点。

    举例,如下图:

    树的结构为:

    typedef struct BinaryTreeNode{

    struct BinaryTreeNode* leftChild;

    struct BinaryTreeNode* rightChild;

    int value;

    };

    typedef struct TreeNode{

    struct TreeNode* child[];

    int child_count;

    int value;

    };

    BinaryTreeNode* ToBinaryTree(TreeNode* root){

    if(root == null) return null;

    BinaryTreeNode* binaryRoot = new BinaryTreeNode();

    binaryRoot->leftChild =

    binaryRoot->rightChild = NULL;//注意初始化

    binaryRoot->value =

    root->value;

    binaryRoot->leftChild =

    ToBinaryTree(root->child[0]);

    BinaryTreeNode* brother =

    binaryRoot->leftChild;

    for(int i = 1; i <

    root->child_count;i++){

    brother->rightChild =

    ToBinaryTree(root->child[i]);

    brother = brother->rightChild;

    }

    return binaryRoot;

    }

    看是什么二叉树了。

    先遍历多叉树,将所有节点得到,然后根据相应的二叉树的规则构造二叉树就行了。

    树采用的存储结构见表一,转化为二叉树见表二,之后再将表转化为二叉链表的存储方式,程序及相应测试见代码:

    data

    parent

    0

    A

    -1

    1

    B

    0

    2

    C

    0

    3

    D

    0

    4

    E

    1

    5

    F

    1

    6

    G

    3

    data

    parent

    leftchild

    rightchild

    0

    A

    -1

    1(原值为0 )

    0

    1

    B

    0

    4

    2

    2

    C

    0

    0

    3

    3

    D

    0

    6

    0

    4

    E

    1

    0

    5

    5

    F

    1

    0

    0

    6

    G

    3

    0

    0

    #include

    #include

    using namespace std ;

    struct Node { //以表的形式存储的树结点

    char data;

    int parent;

    int lchild;

    int rchild;

    };

    struct TreeNode { //以二叉链表存储的树的结点

    char data;

    TreeNode* l;

    TreeNode* r;

    };

    int creattable( Node table[]){ //创建树的表并转化为二叉树

    int n,k,i,j;

    cout<

    cin>>n;

    if ( n>0 ){

    cout<

    a -1 ):"<

    for( i = 0; i <

    n; i++){

    cin>>table[i].data>>table[i].parent;

    table[i].lchild = table[i].rchild = 0;

    }

    for( i = 0; i <

    n; i++ ){

    for( j = 1;j

    < n; j++ ){

    if( table[j].parent == i )

    if( table[i].lchild == 0 ){

    table[i].lchild = j;

    k = j;

    }

    else{

    table[k].rchild = j;

    k = j;

    }

    }

    }

    for( i = 0; i <

    n; i++)

    cout<

    [i].lchild<

    }

    return n;

    }

    void Build ( TreeNode*&

    current,Node node[], int pos ,int n ){ //将表

    转化为二叉链表

    if (n>0)

    {if ( current == 0 ){

    current = new TreeNode;

    current->l =

    current->r = 0;

    }

    current->data = node[pos].data;

    if (node[pos].lchild )

    Build(

    current->l, node, node[pos].lchild, n);

    if (node[pos].rchild

    ) Build(

    urrent->r ,node, node[pos].rchild, n);

    }

    }

    void Visit ( TreeNode* current ){ //访问结点

    cout<data<

    ";

    }

    void Preorder( TreeNode* root ){ //按先序遍历

    TreeNode* current =

    root;

    if( current != 0

    ){ Visit(

    current );

    Preorder(

    current->l );

    Preorder(

    current->r

    ); }

    }

    int main(){

    Node node [20];

    int n = creattable( node );

    TreeNode* root = 0;

    Build ( root, node, 0 , n);

    if (root){

    cout<

    Preorder ( root );

    cout<

    }

    else

    cout<

    return 1;

    }

    更多相关内容
  • 多叉树转换为二叉树算法.doc
  • (转自:多叉转二叉,前提是我们仍要把的信息保留下来,也就是谁是谁的孩子,谁是谁的兄弟。但是二叉只能保存两个孩子,但我们可以把两个孩子改成两个关系,也就是我们利用二叉来储存关系,一个是孩子,一个是兄弟...

    (转自:

    多叉转二叉,前提是我们仍要把树的信息保留下来,也就是谁是谁的孩子,谁是谁的兄弟。但是二叉只能保存两个孩子,但我们可以把两个孩子改成两个关系,也就是我们利用二叉来储存关系,一个是孩子,一个是兄弟。

    于是,就出现了网上广泛介绍的方法,当一个节点是另一个节点的孩子时,就放在父亲节点的左孩子上,是兄弟,就该放在右孩子上,也就是所谓的“左儿子,右兄弟”。

    89b1702f38eeb0d2bfb4a4dde859460c.png

    当然多叉转二叉的形式不止一种,上图是其中的一种。

    因为2,3,4都是1的孩子,所以都位于1的左子树里。至于谁跟1相连,这个顺序不唯一,但不影响,看是如何读取吧。

    然后对于2,3,4互为兄弟,所以都放在各自的右子树里。

    7是4的孩子,所以7就放在4的左子树上。

    5,6是二的孩子,就放在2的左子树上。

    5,6互为兄弟,就放到6(或5)的右子树上。

    实现方法

    一、

    1.读入a,b表示a是b的孩子

    2.如果b的左孩子为空,那么a就放在b的左孩子,否则循环b的左孩子的右孩子直到该孩子的右孩子为空为止,放到该孩子的右孩子上。

    8f900a89c6347c561fdf2122f13be562.png

    961ddebeb323a10fe0623af514929fc1.png

    1 for (int i=1;i<=m;i++)2 {3 cin>>a>>b //a是b的孩子

    4 if (tree[b].l==0) tree[b].l=a;5 else{6 int tmp=tree[b].l;7 while (tree[tmp].r!=0) tmp=tree[tmp].r;//直到该孩子没有右孩子为止

    8 tree[tmp].r=a;9 }10 }

    代码

    二、

    当孩子过多的时候,会发现循环可能会过慢,降低效率。

    我们还可以用类似储存链式前向星的方法,让父亲的左孩子为读入的孩子,然后这个孩子的右孩子是父亲的之前第一个左孩子。

    如:

    e18c51e157efe85f0320c2ace8e474ae.png

    我们现在读入的是4是1的孩子,按照方法一的话最终是这样的

    51012d592928fb8e4e9d14361cd4cb27.png

    很明显当右孩子过多的时候,循环可能会过久,方法二减小循环就是这样做的:

    读入4是1的孩子,那么

    4cf1439edfaca4cbd828bdad279c87b3.png

    把1的左孩子给4的右孩子

    aaea1dc76385692195ab02c733bcf7ab.png

    然后4给1的左孩子

    ecdfabeaf03e1516525e54a65e396ab8.png

    最终就是这样子啦~

    8f900a89c6347c561fdf2122f13be562.png

    961ddebeb323a10fe0623af514929fc1.png

    1 for (int i=1;i<=m;i++)2 {3 cin>>a>>b //a是b的孩子

    4 tree[a].r=tree[b].l; //把b的左孩子给a的右孩子

    5 tree[b].l=a; //把a给b的左孩子

    6 }

    代码

    展开全文
  • 多叉树 转换为二叉树 算法

    千次阅读 2014-09-23 00:03:43
    多叉树转换为二叉树算法。算法描述:将多叉树的第一个儿子结点作为二叉树的左结点,将其兄弟结点作为二叉树的右结点。 举例,如下图: 树的结构: typedef struct BinaryTreeNode{ struct BinaryTreeNode* ...

    多叉树转换为二叉树算法。算法描述:将多叉树的第一个儿子结点作为二叉树的左结点,将其兄弟结点作为二叉树的右结点。

    举例,如下图:


    树的结构为:

    typedef struct BinaryTreeNode{

    struct BinaryTreeNode* leftChild;

    struct BinaryTreeNode* rightChild;

    int value;

    };

    typedef struct TreeNode{

    struct TreeNode* child[];

    int child_count;

    int value;

    };

     

    BinaryTreeNode* ToBinaryTree(TreeNode*root){

        if(root == null) return null;

        BinaryTreeNode* binaryRoot = new BinaryTreeNode();

     

        binaryRoot->leftChild = binaryRoot->rightChild = NULL;//注意初始化

        binaryRoot->value = root->value;

        binaryRoot->leftChild = ToBinaryTree(root->child[0]);

        BinaryTreeNode* brother = binaryRoot->leftChild;

        for(int i = 1; i < root->child_count;i++){

            brother->rightChild = ToBinaryTree(root->child[i]);

            brother = brother->rightChild;

        }

        return binaryRoot;

    }

     

    树采用的存储结构见表一,转化为二叉树见表二,之后再将表转化为二叉链表的存储方式,程序及相应测试见代码:

     

     

     

    data

    parent

    0

    A

    -1

    1

    B

    0

    2

    C

    0

    3

    D

    0

    4

    E

    1

    5

    F

    1

    6

    G

    3

     

     

     

    data

    parent

    leftchild

    rightchild

    0

    A

    -1

    1

    0

    1

    B

    0

    4

    2

    2

    C

    0

    0

    3

    3

    D

    0

    6

    0

    4

    E

    1

    0

    5

    5

    F

    1

    0

    0

    6

    G

    3

    0

    0

     

     

                    表一                              表二

     

     

     

     

     

     

     

     

     

    #include<iostream>

    #include <string>

    using namespace std;

     

    struct Node    // 以表的形式存储的树结点

    {

        chardata;

        intparent;   

        intlchild;

        intrchild;

    };

     

    struct TreeNode // 以二叉链表存储的树结点

    {

        chardata;

        TreeNode*l;

        TreeNode*r;

    };

     

    // 创建树的表并转化为二叉树

    int creattable(Node table[])

    {

        intn, k, i, j;

        cout<< "输入结点个数(<20):";

        cin>> n;

        if(n > 0)

        {

           cout << "输入结点信息和双亲编号(第一个请输入根结点信息如a-1 ):" << endl;

           for (i = 0; i < n; i++)

           {

               cin >> table[i].data >> table[i].parent;

               table[i].lchild = table[i].rchild = 0;

           }

           for (i = 0; i < n; i++)

           {

               for (j = 1; j < n; j++)

               {

                    if (table[j].parent == i)

                    {

                        if (table[i].lchild == 0)

                        {

                            table[i].lchild = j;

                            k = j;

                        }

                        else

                        {

                            table[k].rchild = j;

                            k = j;

                        }

                    }

               }

           }

           for (i = 0; i < n; i++)

           {

               cout << table[i].data << table[i].parent <<table[i].lchild << table[i].rchild << endl;

           }

        }

        returnn;

    }

     

    // 将表转化为二叉链表

    void Build(TreeNode *&current, Nodenode[], int pos, int n)

    {

        if(n > 0)

        {

            if (current == 0)

           {

               current = new TreeNode;

               current->l = current->r = 0;

           }

           current->data = node[pos].data;

           if (node[pos].lchild)

               Build(current->l, node, node[pos].lchild, n);

           if (node[pos].rchild)

               Build(current->r, node, node[pos].rchild, n);

        }

    }

     

    // 访问结点

    void Visit(TreeNode *current)

    {

        cout<<current->data<<"";

    }

     

    // 按先序遍历

    void Preorder(TreeNode *root)

    {

      TreeNode *current = root;

       if(current != 0)

      {  

           Visit(current);

           Preorder(current->l);

           Preorder(current->r);

       }

    }

     

    int main()

    {

        Nodenode[20];

        intn = creattable(node);

        TreeNode*root = 0;

     

        Build(root,node, 0, n);

        if(root)

        {

           cout << "先序遍历:";

           Preorder(root);

           cout << endl;

        }

        else

        {

           cout << "空树!" << endl;

        }

       

        return0;

    }

    展开全文
  • 多叉树二叉树图示: 将同一个父节点的所有子节点用虚线相连起来 将上面的红线断开 然后将虚线顺时针旋转45°,虚线变实线 这样即可完成多叉树二叉树 简单来说,就是以a头结点的多叉树,其第一...

    多叉树转二叉树图示:

    将同一个父节点的所有子节点用虚线相连起来

    将上面的红线断开

     然后将虚线顺时针旋转45°,虚线变实线

     这样即可完成多叉树转二叉树

    简单来说,就是以a为头结点的多叉树,其第一个孩子节点挂在其左侧,然后第二个孩子节点c,挂在第一个孩子节点b的右侧,第三个孩子节点d挂在第二个孩子节点c的右侧。以b为头结点的多叉树,以c为头结点的多叉树也是同理。即将a的所有孩子节点连成一条链表,该链表是从水平变成顺时针旋转旋转45°。b.right=c   c.right=d即可实现将链表链表是从水平变成顺时针旋转旋转45°。

    那么用深度优先遍历算法如何将多叉树转成二叉树呢?

    如下是深度优先遍历算法将多叉树转成二叉树的代码实现

        /**
         * 多叉树节点类
         */
        public static class Node {
    
            public int val;
    
            public List<Node> children;
    
            public Node() {
            }
    
            public Node(int val, List<Node> children) {
                this.val = val;
                this.children = children;
            }
        }
    
        /**
         * 二叉树节点类
         */
        public static class TreeNode {
    
            public int value;
    
            public TreeNode left;
    
            public TreeNode right;
    
            public TreeNode(int value) {
                this.value = value;
            }
        }
    
    
    public static TreeNode encode(Node root) {
            if (root == null) {
                return null;
            }
            TreeNode head = new TreeNode(root.val);
            head.left = processEncode(root.children);
            return head;
        }
    
        /**
         * 按照深度优先遍历构建二叉树
         *
         * @param children
         * @return
         */
        public static TreeNode processEncode(List<Node> children) {
            //二叉树头结点
            TreeNode head=null;
            //当前节点
            TreeNode cur=null;
            for (Node child:children){
                //每遍历一个child,创建一个TreeNode节点
                TreeNode node=new TreeNode(child.val);
                if (head==null){ //若二叉树头结点为null,则node直接成为头结点
                    head=node;
                }else { //若二叉树头结点不为null,则让cur的right指针指向node
                    cur.right=node;
                }
                cur=node;
                //处理以cur为头的二叉树,让其直系孩子向右
                cur.left=processEncode(child.children);
            }
            return head;
        }
    

    二叉树又如何转回多叉树呢?

     将b和f,c和h,a和c,a和d用虚线相连,如下图

    将如下的红线断开,虚线变实线

     修改如下

    将上图摆正,即将二叉树还原成多叉树

     

    二叉树转多叉树的代码实现

        /**
         * 多叉树节点类
         */
        public static class Node {
    
            public int val;
    
            public List<Node> children;
    
            public Node() {
            }
    
            public Node(int val, List<Node> children) {
                this.val = val;
                this.children = children;
            }
        }
    
        /**
         * 二叉树节点类
         */
        public static class TreeNode {
    
            public int value;
    
            public TreeNode left;
    
            public TreeNode right;
    
            public TreeNode(int value) {
                this.value = value;
            }
        }
    
    
        /**
         * 利用深度优先遍历将二叉树转成多叉树
         *
         * @param root
         * @return
         */
        public Node decode(TreeNode root) {
            if (root == null) {
                return null;
            }
            return new Node(root.value, processDecode(root.left));
        }
    
        public List<Node> processDecode(TreeNode root) {
            List<Node> children = new ArrayList<>();
            while (root != null) {
                Node cur = new Node(root.value, processDecode(root.left));
                children.add(cur);
                root = root.right;
            }
            return children;
        }

     

    展开全文
  • *多叉树二叉树转换的方法如下:*(1)加虚线:同一个父节点的相邻兄弟节点之间加虚线。*(2)抹实线:每个节点只保留它与最左子节点的连线,与其他子节点的连线都抹掉。*(3)虚改实:虚线改实线。*例如,如图所示就是...
  • 数据结构----树----多叉树二叉树

    千次阅读 2017-04-25 14:06:36
    一、多叉树二叉树的方法 1、输入一颗多叉树 2、找到根节点,把它除最左边的儿子以外的所有儿子的关系断掉 3、从左儿子开始,把同层的兄弟依次连接起来 4、然后对根节点的儿子依次递归进行次操作,...
  • 多叉树二叉树

    2021-03-15 19:56:01
    import java.util.LinkedList;import java.util.List;class MNode {char data;List children = new LinkedList();public MNode() {super();}}class BNode {char data;BNode left;BNode right;public BNode(char data...
  • 多叉树转换二叉树

    2019-09-28 02:29:27
    多叉转二叉,前提是我们仍要把的信息保留下来,也就是谁是谁的孩子,谁是谁的兄弟。但是二叉只能保存两个孩子,但我们可以把两个孩子改成两个关系,也就是我们利用二叉来储存关系,一个是孩子,一个是兄弟。 于是...
  • 多叉树二叉树 题目描述:: 截图可方便了 方法: 举个栗子,如图:: 好和谐啊 这是一棵多叉树 如何转化为二叉树?? 连接每一组兄弟,如图: 把右儿子断掉,如图: 然后再整理一下,就变成了: ...
  • 多叉树转化为二叉树 森林转化为二叉树 二叉树转化树或者森林
  • 看到这个题目我们要先把问题简化了,条件中是多叉树,我们可以把它转换二叉树,左边是儿子右边是兄弟的储存方式。 首先先判断否的部分,当总的果子小于需求,也就是N-k时输出-1。 我们再判断是的部分 如果没有...
  • 多叉树(森林)转二叉树

    千次阅读 多人点赞 2017-04-10 14:11:37
    多叉转二叉有“左儿子右兄弟”的说法,然而对于什么都不知道的小白,这句话没有任何用……思路大体就两步,很好理解,如图是用来举栗的多叉树: 兄弟连将所有的兄弟间连一条线,如图: 右子断将所有右儿子与父亲的...
  • c语言多叉树二叉树

    千次阅读 2016-12-05 19:25:13
    多叉树二叉树原理: 二叉树节点的左子树对应多叉树节点的第一个孩子,右子树为多叉树中它的右兄弟,以此类推 #include #include #define M 5 /* 多叉树最大子数量5 */ typedef struct mtree_node { int val;...
  • LeetCode 431:设计一个算法,可以将 N 叉编码为二叉树,并能将该二叉树解码原 N 叉。 一个 N 叉是指每个节点都有不超过 N 个孩子节点的有根树。 类似地,一个二叉树是指每个节点都有不超过 2 个孩子节点的...
  • 多叉树转二叉树的应用非常广泛,因为如果一个节点的儿子太多,一个一个存下来不方便去查询,并且会增加复杂度,但是这里我们就有一个O(n)的复杂度的方法把多叉树转换为二叉树,转换成二叉树后就更方便查询,因为每个...
  • 树的相互转换 多叉树转化为二叉树

    千次阅读 2013-12-20 14:03:49
    // 此代码 多叉树转化 二叉树并且二叉树转化为多叉树的代码 #include "stdafx.h" #include  #include  // 树的结点分布信息 struct SCreateNormalTree {  int nData ;  int nPrev...
  • 将子女兄弟链表调整普通然后将普通调整子女兄弟链表,注意是在原上直接进行调整,不是根据原树创建转换后的新,为了操作方便,指针域用vector表示 C++代码: 子女兄弟链表存在共享子树情形: #...
  • 问这么一个多叉树的高度转为二叉树,这个二叉树的高度有多高 转二叉树的方法题目已经告诉你了: “左儿子,右兄弟” 就是将一个节点的第一个儿子放在左儿子的位置,下一个的儿子,即左儿子的第一个兄弟, 放在左儿子的右...
  • 把一个多叉树转换为二叉树的步骤(填空)5.sql语句(简答)5.TCP协议如何保证传输可靠性5.TCP协议如何保证传输可靠性 题目总共有单选题(6个)、填空题(4个)、简答题(4或者6个)、编程题(一道),简答题里面还有...
  • 二叉树转换就是这么简单

    千次阅读 多人点赞 2019-03-26 15:17:35
    二叉树是树结构的特例,现实生活中见的比较多的是多叉树。由于二叉树的链接浪费率最低,所以我们常常将树转化为二叉树来操作,这样不仅降低链接浪费率,而且还可以使得操作更加简便。 1. 树转化为二叉树 树转化...
  • 文章目录5、求树的最大宽度6、折纸问题(二叉树思想启蒙)7、判断一颗树是不是完全二叉树8、多叉树二叉树的互换(需要理解递归过程)8.1 多叉树二叉树8.2 二叉树多叉树9、给定一个二叉树节点,其中节点指针还...
  • // 此代码 多叉树转化 二叉树并且二叉树转化为多叉树的代码 #include "stdafx.h" #include  #include  // 树的结点分布信息 struct SCreateNormalTree {  int nData ;  int nPrev...
  • 数据结构笔记6树与二叉树 前言 数据结构笔记5数组 写一下树与二叉树的笔记。 思维框架图 文章目录数据结构笔记6树与二叉树前言思维框架图树的定义和基本术语二叉树遍历二叉树...13.如果二叉树T是由多叉树F转换而成,那

空空如也

空空如也

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

多叉树转换为二叉树