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

举例，如下图：

树的结构为：

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为头结点的多叉树，其第一个孩子节点挂在其左侧，然后第二个孩子节点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;
    }