多叉树转二叉树图示：

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

将上面的红线断开

 然后将虚线顺时针旋转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;
    }

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

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

转换规则
将一棵多叉树转换成二叉树，我们遵循的原则是：左儿子，右兄弟。算法描述：将多叉树的第一个儿子结点作为二叉树的左结点，将其兄弟结点作为二叉树的右结点。
假设多叉树为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; 
}