精华内容
下载资源
问答
  • 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, BNode left, BNode right) {

    super();

    this.data = data;

    this.left = left;

    this.right = right;

    }

    }

    public class MTreeToBTree {

    public static BNode generateBNode(List mnodes, int start) {

    if (mnodes.size() == start)

    return null;

    if (mnodes.size() == 0)

    return null;

    BNode bnode = new BNode(mnodes.get(start).data, generateBNode(mnodes

    .get(start).children, 0), generateBNode(mnodes, start + 1));

    return bnode;

    }

    public static BNode transform(MNode root) {

    return new BNode(root.data, generateBNode(root.children, 0), null);

    }

    private static MNode nodea;

    private static void initMTree() {

    nodea = new MNode();

    nodea.data = ‘a‘;

    MNode nodeb = new MNode();

    nodeb.data = ‘b‘;

    MNode nodec = new MNode();

    nodec.data = ‘c‘;

    MNode noded = new MNode();

    noded.data = ‘d‘;

    MNode nodee = new MNode();

    nodee.data = ‘e‘;

    MNode nodef = new MNode();

    nodef.data = ‘f‘;

    MNode nodeg = new MNode();

    nodeg.data = ‘g‘;

    MNode nodeh = new MNode();

    nodeh.data = ‘h‘;

    nodea.children.add(nodeb);

    nodea.children.add(nodec);

    nodea.children.add(noded);

    nodeb.children.add(nodee);

    nodec.children.add(nodef);

    noded.children.add(nodeg);

    noded.children.add(nodeh);

    }

    private static void printBTreePreOrder(BNode root) {

    if (root != null) {

    System.out.print(root.data + " ");

    printBTreePreOrder(root.left);

    printBTreePreOrder(root.right);

    }

    }

    private static void printBTreeInOrder(BNode root) {

    if (root != null) {

    printBTreeInOrder(root.left);

    System.out.print(root.data + " ");

    printBTreeInOrder(root.right);

    }

    }

    private static void printBTreePostOrder(BNode root) {

    if (root != null) {

    printBTreePostOrder(root.left);

    printBTreePostOrder(root.right);

    System.out.print(root.data + " ");

    }

    }

    public static void main(String[] args) {

    initMTree();

    BNode broot = transform(nodea);

    printBTreePreOrder(broot);

    System.out.println();

    printBTreeInOrder(broot);

    System.out.println();

    printBTreePostOrder(broot);

    }

    }

    更多相关内容
  • 多叉树二叉树图示: 将同一个父节点的所有子节点用虚线相连起来 将上面的红线断开 然后将虚线顺时针旋转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;
        }

     

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

    (转自:

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

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

    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 }

    代码

    展开全文
  • 数据结构-多叉树二叉树

    千次阅读 2018-12-22 10:09:22
    多叉树的含义 多叉树即为子结点有任意个的树,而在转换时所涉及的多叉树是一棵有序的多叉树,也就是其子结点的顺序是不能够随便交换的。...而二叉树相对于多叉树便有了这些方面的优势,能够节省浪费...

    多叉树的含义
    多叉树即为子结点有任意个的树,而在转换时所涉及的多叉树是一棵有序的多叉树,也就是其子结点的顺序是不能够随便交换的。
    二叉树的定义
    二叉树是每个结点最多有两个后件,且子树有左右之分(次序不能任意颠倒)。

    多叉树转二叉树的作用
    在用数组等表示或保存多叉树时,会浪费存储的空间,而且由于树中每个结点的度各不相同,在搜索过程中会比较的困难。而二叉树相对于多叉树便有了这些方面的优势,能够节省浪费的存储空间,又能使搜索变得简便快捷。因此可以通过将多叉树转换成为二叉树从而实现优化。

    转换规则
    将一棵多叉树转换成二叉树,我们遵循的原则是:左儿子,右兄弟。算法描述:将多叉树的第一个儿子结点作为二叉树的左结点,将其兄弟结点作为二叉树的右结点。
    假设多叉树为T,新转化的二叉树为K
    (1)T中的结点与K中的结点一一对应。
    (2)T中的某个结点N的第一个子结点为N1,则K中N1为N的左儿子结点
    (3)T中的某个结点N的第i个子结点记为Ni(除第一个子结点),则K中Ni为Ni-1的右儿子结点(N2为N1的右儿子结点,N3为N2的右儿子结点)

    转换示意图

    例1

    【输入】
    第一行仅一个数字n,表示有n个结点。之后n行,每行第一个数字为结点编号,后几个数字按顺序为该结点的子结点。每行以0结尾。
    【样例输入】
    18
    1 2 3 4 0
    2 5 6 0
    3 7 0
    4 8 9 10 0
    5 0
    6 11 12 0
    7 0
    8 0
    9 13 14 0
    10 0
    11 15 0
    12 0
    13 16 17 18 0
    14 0
    15 0
    16 0
    17 0
    18 0

    【输出】
    N行,每行第一个数字为结点编号,第二个为父结点,第三个为左结点,最后为右结点。
    【样例输出】
    1 0 2 0
    2 1 5 3
    3 2 7 4
    4 3 8 0
    5 2 0 6
    6 5 11 0
    7 3 0 0
    8 4 0 9
    9 8 13 10
    10 9 0 0
    11 6 15 12
    12 11 0 0
    13 9 16 14
    14 13 0 0
    15 11 0 0
    16 13 0 17
    17 16 0 18
    18 17 0 0

    Type
     Code=record
      Left,right,father,data:longint;
      end;
    Var
     Tree:array[1..1000]of code;
     I,j,n,p:longint;
    Begin
     Readln(n); i:=1;
     Fillchar(tree,sizeof(tree),0); {二叉树初始化}
     While i<=n do
      begin
       Read(tree[i].data);Read(j);
       If j<>0 then {j不是叶子}
        Begin
         tree[i].left:=j;tree[j].father:=I; {j为结点i的左儿子}
         P:=j;
        Repeat
         Read(j);
         If j<>0 then
          Begin
           Tree[p].right:=j;tree[j].father:={j为p的右儿子}
           P:=j;
         End;
         Until j=0;
        End;
        i:=i+1;readln;
      End;
      For i:=1 to n do 
       writeln(tree[i].data,’ ’tree[i].father,’ tree[i].left,’ ’tree[i].right);
    End.

    例2

    【问题描述】树采用的存储结构见表一,转化为二叉树见表二,之后再将表转化为二叉链表的存储方式

    #include<iostream> 
    #include <string> 
    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 << "输入结点个数(<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 ;
    			cout << table[i].lchild<< table[i].rchild << endl;
    		} 
    	}
    	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(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()
    {
    	Node node[20];
    	int n = creattable(node); 
    TreeNode *root = 0;
    	Build(root, node, 0, n); 
    if (root) 
    {
    		cout << "先序遍历:"; 
    Preorder(root); 
    cout << endl; 
    }
    	else 
    		cout << "空树!" << endl; 
    	return 0; 
    }
    

     

    展开全文
  • // 此代码为 多叉树转化为 二叉树并且二叉树转化为多叉树的代码 #include "stdafx.h" #include  #include  // 树的结点分布信息 struct SCreateNormalTree {  int nData ;  int nPrev...
  • 二叉树多叉树

    2020-05-10 17:09:59
    多叉树 2-3树 B树 B+树 B*树 序言 二叉树的缺点 二叉树需要加载到内存中,如果节点少,没什么问题,若是节点非常多,就会带来问题 当构建二叉树时,需要进行多次I/O操作,构造速度会有影响 节点海量,会造成二叉树...
  • 方法:将多叉树的第一个儿子结点作为二叉树的左结点,将其兄弟结点作为二叉树的右结点。举例,如下图:树的结构为:typedef struct BinaryTreeNode{struct BinaryTreeNode* leftChild;struct BinaryTreeNode* right...
  • 数据结构----树----多叉树二叉树

    千次阅读 2017-04-25 14:06:36
    一、多叉树二叉树的方法 1、输入一颗多叉树 2、找到根节点,把它除最左边的儿子以外的所有儿子的关系断掉 3、从左儿子开始,把同层的兄弟依次连接起来 4、然后对根节点的儿子依次递归进行次操作,...
  • *多叉树二叉树转换的方法如下:*(1)加虚线:同一个父节点的相邻兄弟节点之间加虚线。*(2)抹实线:每个节点只保留它与最左子节点的连线,与其他子节点的连线都抹掉。*(3)虚改实:虚线改为实线。*例如,如图所示就是...
  • 决策的决策标准:ID3(最大信息增益)【偏好性过强】、C4.5(最大信息增益率)【改进偏好性问题】、CART(基尼系数)【改进前面计算量大的问题】 后面的是对前面的改进
  • 多叉树转化为二叉树 森林转化为二叉树 二叉树转化为树或者森林
  • 多叉树转换二叉树

    2019-09-28 02:29:27
    多叉转二叉,前提是我们仍要把的信息保留下来,也就是谁是谁的孩子,谁是谁的兄弟。但是二叉只能保存两个孩子,但我们可以把两个孩子改成两个关系,也就是我们利用二叉来储存关系,一个是孩子,一个是兄弟。 于是...
  • 数据结构之二叉树、N叉树、多叉树
  • 把aia_iai​看成faifa_ifai​,建出一棵多叉树,再把多叉树转成二叉树,转出来的每棵二叉树对应着一种比赛方式。 以n=8,a2,...,8=1,1,2,4,3,3,3n=8,a_{2,...,8}=1,1,2,4,3,3,3n=8,a2,...,8​=1,1,2,4,3,3,3为例, ...
  • 多叉树二叉树 题目描述:: 截图可方便了 方法: 举个栗子,如图:: 好和谐啊 这是一棵多叉树 如何转化为二叉树?? 连接每一组兄弟,如图: 把右儿子断掉,如图: 然后再整理一下,就变成了: ...
  • 每棵最大可能形成的高度为其最深子树的高度(根节点高度为0)+其孩子的数量 #include #include using namespace std; const int N = 1e5 + 10; vector g[N]; int dfs(int u) { int ans = 0; int len = g[u].size(); ...
  • 问这么一个多叉树的高度转为二叉树,这个二叉树的高度有多高 转二叉树的方法题目已经告诉你了: “左儿子,右兄弟” 就是将一个节点的第一个儿子放在左儿子的位置,下一个的儿子,即左儿子的第一个兄弟, 放在左儿子的右...
  • c语言多叉树二叉树

    千次阅读 2016-12-05 19:25:13
    多叉树二叉树原理: 二叉树节点的左子树为对应多叉树节点的第一个孩子,右子树为多叉树中它的右兄弟,以此类推 #include #include #define M 5 /* 多叉树最大子数量为5 */ typedef struct mtree_node { int val;...
  • 看到这个题目我们要先把问题简化了,条件中是多叉树,我们可以把它转换成二叉树,左边是儿子右边是兄弟的储存方式。 首先先判断否的部分,当总的果子小于需求,也就是N-k时输出-1。 我们再判断是的部分 如果没有...
  • //lastchild[f]不等于0,创建兄弟,即右儿子 }//i每加一次就要创建一个左儿子或右儿子,意思是第i个元素是上一个元素(若是兄弟,则是i-1,若是父亲则f(f=nodes[i].parent))的左子树或者右子 } } void Preorder...
  • 多叉树(森林)转二叉树

    千次阅读 多人点赞 2017-04-10 14:11:37
    多叉转二叉有“左儿子右兄弟”的说法,然而对于什么都不知道的小白,这句话没有任何用……思路大体就两步,很好理解,如图是用来举栗的多叉树: 兄弟连将所有的兄弟间连一条线,如图: 右子断将所有右儿子与父亲的...
  • 多叉树转换为二叉树算法.doc
  • 按照搜索步骤,前半部分使用多叉树搜索,由于未知扫码标签的数量,所以在进行多叉树搜索之后再用二叉树进行搜索。当该方法识别到仅有一个碰撞位时,直接对标签编码进行识别。仿真实验结果表明,该基于二叉树多叉树...
  • 关于如何把多叉树转化为二叉树,有个口诀,叫做左儿子不变,右儿子兄♂弟。 详细的不多说,可以去参考一下相关资料。 等转化为二叉树了过后,让我们来琢磨一下。 左儿子:原根节点的孩子。 右儿子:原根节点的兄 ♂...
  • 即,多叉树。然而,此时又面临着另外一个问题: 当孩子结点无限制时,我们并不知道预先要分配多少个属性,且当仅有少数元素拥有多个子节点时,将会造成大量的空间浪费。 此时,提出了一种新的表示形式: left−...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,485
精华内容 2,994
关键字:

多叉树和二叉树