-
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);
}
}
更多相关内容 -
深度优先遍历解多叉树转二叉树,二叉树转多叉树
2022-01-05 20:01:33多叉树转二叉树图示: 将同一个父节点的所有子节点用虚线相连起来 将上面的红线断开 然后将虚线顺时针旋转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; }
-
[转] 多叉树转换二叉树
2021-03-15 19:56:31(转自:多叉转二叉,前提是我们仍要把树的信息保留下来,也就是谁是谁的孩子,谁是谁的兄弟。但是二叉只能保存两个孩子,但我们可以把两个孩子改成两个关系,也就是我们利用二叉来储存关系,一个是孩子,一个是兄弟...(转自:
多叉转二叉,前提是我们仍要把树的信息保留下来,也就是谁是谁的孩子,谁是谁的兄弟。但是二叉只能保存两个孩子,但我们可以把两个孩子改成两个关系,也就是我们利用二叉来储存关系,一个是孩子,一个是兄弟。
于是,就出现了网上广泛介绍的方法,当一个节点是另一个节点的孩子时,就放在父亲节点的左孩子上,是兄弟,就该放在右孩子上,也就是所谓的“左儿子,右兄弟”。
当然多叉转二叉的形式不止一种,上图是其中的一种。
因为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的左孩子的右孩子直到该孩子的右孩子为空为止,放到该孩子的右孩子上。
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 }
代码
二、
当孩子过多的时候,会发现循环可能会过慢,降低效率。
我们还可以用类似储存链式前向星的方法,让父亲的左孩子为读入的孩子,然后这个孩子的右孩子是父亲的之前第一个左孩子。
如:
我们现在读入的是4是1的孩子,按照方法一的话最终是这样的
很明显当右孩子过多的时候,循环可能会过久,方法二减小循环就是这样做的:
读入4是1的孩子,那么
把1的左孩子给4的右孩子
然后4给1的左孩子
最终就是这样子啦~
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 0Type 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 *¤t, 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; }
-
树的转化 多叉树和二叉树之间的互转
2013-12-20 14:05:12// 此代码为 多叉树转化为 二叉树并且二叉树转化为多叉树的代码 #include "stdafx.h" #include #include // 树的结点分布信息 struct SCreateNormalTree { int nData ; int nPrev... -
二叉树与多叉树
2020-05-10 17:09:59多叉树 2-3树 B树 B+树 B*树 序言 二叉树的缺点 二叉树需要加载到内存中,如果节点少,没什么问题,若是节点非常多,就会带来问题 当构建二叉树时,需要进行多次I/O操作,构造速度会有影响 节点海量,会造成二叉树... -
多叉树转换为二叉树算法
2021-03-15 19:56:20方法:将多叉树的第一个儿子结点作为二叉树的左结点,将其兄弟结点作为二叉树的右结点。举例,如下图:树的结构为:typedef struct BinaryTreeNode{struct BinaryTreeNode* leftChild;struct BinaryTreeNode* right... -
数据结构----树----多叉树转二叉树
2017-04-25 14:06:36一、多叉树转二叉树的方法 1、输入一颗多叉树 2、找到根节点,把它除最左边的儿子以外的所有儿子的关系断掉 3、从左儿子开始,把同层的兄弟依次连接起来 4、然后对根节点的儿子依次递归进行次操作,... -
Java基础 - 多叉树、森林和二叉树之间的转换
2021-03-15 19:55:58*多叉树向二叉树转换的方法如下:*(1)加虚线:同一个父节点的相邻兄弟节点之间加虚线。*(2)抹实线:每个节点只保留它与最左子节点的连线,与其他子节点的连线都抹掉。*(3)虚改实:虚线改为实线。*例如,如图所示就是... -
机器学习面试题——决策树DT(Decision Tree),二叉树或多叉树分支决策分类
2022-04-30 23:15:24决策树的决策标准:ID3(最大信息增益)【偏好性过强】、C4.5(最大信息增益率)【改进偏好性问题】、CART(基尼系数)【改进前面计算量大的问题】 后面的是对前面的改进 -
二叉树与多叉树和森林之间的转化
2021-03-13 16:12:29多叉树转化为二叉树 森林转化为二叉树 二叉树转化为树或者森林 -
多叉树转换二叉树
2019-09-28 02:29:27多叉转二叉,前提是我们仍要把树的信息保留下来,也就是谁是谁的孩子,谁是谁的兄弟。但是二叉只能保存两个孩子,但我们可以把两个孩子改成两个关系,也就是我们利用二叉来储存关系,一个是孩子,一个是兄弟。 于是... -
数据结构之二叉树、N叉树、多叉树
2022-04-06 20:24:09数据结构之二叉树、N叉树、多叉树 -
[AGC009B] Tournament(多叉树转二叉树后的最小可能深度)
2021-11-19 10:14:21把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为例, ... -
星星之火OIer:多叉树转二叉树
2019-03-05 14:12:51多叉树转二叉树 题目描述:: 截图可方便了 方法: 举个栗子,如图:: 好和谐啊 这是一棵多叉树 如何转化为二叉树?? 连接每一组兄弟,如图: 把右儿子断掉,如图: 然后再整理一下,就变成了: ... -
蓝桥杯真题 多叉树转为二叉树 C++实现
2022-04-02 15:34:34每棵树最大可能形成的高度为其最深子树的高度(根节点高度为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(); ... -
poj 3437 Tree Grafting(多叉树转二叉树)
2020-07-30 18:30:11问这么一个多叉树的高度转为二叉树,这个二叉树的高度有多高 转二叉树的方法题目已经告诉你了: “左儿子,右兄弟” 就是将一个节点的第一个儿子放在左儿子的位置,下一个的儿子,即左儿子的第一个兄弟, 放在左儿子的右... -
c语言多叉树转二叉树
2016-12-05 19:25:13多叉树转二叉树原理: 二叉树节点的左子树为对应多叉树节点的第一个孩子,右子树为多叉树中它的右兄弟,以此类推 #include #include #define M 5 /* 多叉树最大子数量为5 */ typedef struct mtree_node { int val;... -
多叉树转二叉树+树形dp(codevs 1746 贪吃的九头龙 2002noi)
2017-07-27 20:39:10看到这个题目我们要先把问题简化了,条件中是多叉树,我们可以把它转换成二叉树,左边是儿子右边是兄弟的储存方式。 首先先判断否的部分,当总的果子小于需求,也就是N-k时输出-1。 我们再判断是的部分 如果没有... -
凹入表打印、多叉树转二叉树遍历
2021-05-25 20:04:39//lastchild[f]不等于0,创建兄弟,即右儿子 }//i每加一次就要创建一个左儿子或右儿子,意思是第i个元素是上一个元素(若是兄弟,则是i-1,若是父亲则f(f=nodes[i].parent))的左子树或者右子树 } } void Preorder... -
多叉树(森林)转二叉树
2017-04-10 14:11:37多叉转二叉有“左儿子右兄弟”的说法,然而对于什么都不知道的小白,这句话没有任何用……思路大体就两步,很好理解,如图是用来举栗的多叉树: 兄弟连将所有的兄弟间连一条线,如图: 右子断将所有右儿子与父亲的... -
多叉树转换为二叉树算法.doc
2022-05-10 23:16:01多叉树转换为二叉树算法.doc -
一种基于二叉树与多叉树搜索的RFID防碰撞算法研究
2021-01-12 19:53:24按照搜索步骤,前半部分使用多叉树搜索,由于未知扫码标签的数量,所以在进行多叉树搜索之后再用二叉树进行搜索。当该方法识别到仅有一个碰撞位时,直接对标签编码进行识别。仿真实验结果表明,该基于二叉树与多叉树... -
【LUOGU P2014】选课(树形DP,多叉树转二叉树)
2018-07-30 17:10:00关于如何把多叉树转化为二叉树,有个口诀,叫做左儿子不变,右儿子兄♂弟。 详细的不多说,可以去参考一下相关资料。 等转化为二叉树了过后,让我们来琢磨一下。 左儿子:原根节点的孩子。 右儿子:原根节点的兄 ♂... -
多叉树的二叉树表示法(左儿子右兄弟)
2022-01-05 08:25:42即,多叉树。然而,此时又面临着另外一个问题: 当孩子结点无限制时,我们并不知道预先要分配多少个属性,且当仅有少数元素拥有多个子节点时,将会造成大量的空间浪费。 此时,提出了一种新的表示形式: left−...