• 多叉树转换为二叉树
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
• (转自：多叉转二叉，前提是我们仍要把的信息保留下来，也就是谁是谁的孩子，谁是谁的兄弟。但是二叉只能保存两个孩子，但我们可以把两个孩子改成两个关系，也就是我们利用二叉来储存关系，一个是孩子，一个是兄弟...

(转自：

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

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

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

因为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 }

代码

展开全文
• 多叉树转换为二叉树算法。算法描述：将多叉树的第一个儿子结点作为二叉树的左结点，将其兄弟结点作为二叉树的右结点。 举例，如下图： 树的结构： 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)虚改实：虚线改实线。*例如，如图所示就是...
• 一、多叉树二叉树的方法 1、输入一颗多叉树 2、找到根节点，把它除最左边的儿子以外的所有儿子的关系断掉 3、从左儿子开始，把同层的兄弟依次连接起来 4、然后对根节点的儿子依次递归进行次操作，...
• 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...
• 多叉转二叉，前提是我们仍要把的信息保留下来，也就是谁是谁的孩子，谁是谁的兄弟。但是二叉只能保存两个孩子，但我们可以把两个孩子改成两个关系，也就是我们利用二叉来储存关系，一个是孩子，一个是兄弟。 于是...
• 多叉树二叉树 题目描述：： 截图可方便了 方法： 举个栗子，如图：： 好和谐啊 这是一棵多叉树 如何转化为二叉树？？ 连接每一组兄弟，如图： 把右儿子断掉，如图： 然后再整理一下，就变成了： ...
• 多叉树转化为二叉树 森林转化为二叉树 二叉树转化树或者森林
• 看到这个题目我们要先把问题简化了，条件中是多叉树，我们可以把它转换二叉树，左边是儿子右边是兄弟的储存方式。 首先先判断否的部分，当总的果子小于需求，也就是N-k时输出-1。 我们再判断是的部分 如果没有...
• ## 多叉树（森林）转二叉树

千次阅读 多人点赞 2017-04-10 14:11:37
多叉转二叉有“左儿子右兄弟”的说法，然而对于什么都不知道的小白，这句话没有任何用……思路大体就两步，很好理解，如图是用来举栗的多叉树： 兄弟连将所有的兄弟间连一条线，如图： 右子断将所有右儿子与父亲的...
• 多叉树二叉树原理: 二叉树节点的左子树对应多叉树节点的第一个孩子,右子树为多叉树中它的右兄弟,以此类推 #include #include #define M 5 /* 多叉树最大子数量5 */ typedef struct mtree_node { int val;...
• LeetCode 431：设计一个算法，可以将 N 叉编码为二叉树，并能将该二叉树解码原 N 叉。 一个 N 叉是指每个节点都有不超过 N 个孩子节点的有根树。 类似地，一个二叉树是指每个节点都有不超过 2 个孩子节点的...
• 多叉树转二叉树的应用非常广泛，因为如果一个节点的儿子太多，一个一个存下来不方便去查询，并且会增加复杂度，但是这里我们就有一个O(n)的复杂度的方法把多叉树转换为二叉树，转换成二叉树后就更方便查询，因为每个...
• // 此代码 多叉树转化 二叉树并且二叉树转化为多叉树的代码 #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转换而成，那

...