简介

在树状结构中我们可能会使用阵列或指标来表示子节点，然而许多的阵列或指标并没有真的利用到，造成记忆体上的浪费。透过特定的储存方式，能够将各种树都转换成二元树，就能有效解决这个问题。转换的规则如下：

  1. 原节点的第一个子节点转成二元树中的左子节点 。
  2. 原节点的下一个兄弟节点转成二元树中的右子节点。

从图形的角度来看也可以这样说：

  1. 原节点的第一个指标指向第一个子节点。
  2. 原节点的第二个指标指向下一个兄弟节点。

转换过程以下面这张图为例：

lcrs_tree  

左上角的图表示原来的一般树，从图形的角度并以节点3为例，透过规则1将节点3的第一个指标指向第一个子节点，第一个节点我们简单取最左边的节点，为节点1；透过规则2将节点3的第二个指标指向下一个兄弟节点，为节点4。

其他以此类推，接著我们可以得到左下角的图形，与原来的规则做对应我们可以知道，第一个指标指的就是二元树的左子节点，第二个指标就是右子节点，所以依据左右子节点的位置重新调整图形，最后可以得到右边的徒刑，也就是转换成二元树的结果。

LCRS Tree

从上面的转换结果，我们可以知道这个二元树的左子节点代表的是原来的第一个子节点，右子节点代表下一个兄弟节点，而这样的性质的树也称为LCRS Tree(Left-Child-Right-Sibling Tree)。

原始的树如果在后序(Post-order)的情况为排序好的，再转换为二元树后，也同时会是一个二元搜索树。

语法

这边利用之前文章写过的树和二元树程式来做转换。

C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using BinaryTree;
using Tree;

namespace LcrsTree
{
    public class LcrsTree
    {
        static public BinaryTree<T> Convert<T>(Tree<T> tree)
        {
            BinaryTree<T> binaryTree = new LinkedBinaryTree<T>(tree.Value);
            IEnumerator<Tree<T>> enu = tree.Children.GetEnumerator();
            if (enu.MoveNext())
            {
                binaryTree.AddLeft(Convert(enu.Current));
                BinaryTree<T> node = binaryTree.Left;
                while (enu.MoveNext())
                {
                    node.AddRight(Convert(enu.Current));
                    node = node.Right;
                }
            }
            return binaryTree;
        }
    }
}

Java

import java.util.Iterator;


public class LcrsTree {
	
	static public <T> BinaryTree<T> convert(Tree<T> tree) throws Exception 
	{
		BinaryTree<T> binaryTree = new LinkedBinaryTree<T>(tree.getValue());
        Iterator<Tree<T>> iterator = tree.children().iterator();
        if (iterator.hasNext())
        {
            binaryTree.addLeft(convert(iterator.next()));
            BinaryTree<T> node = binaryTree.left();
            while (iterator.hasNext())
            {
                node.addRight(convert(iterator.next()));
                node = node.right();
            }
        }
        return binaryTree;
	}
}

C++

#ifndef LCRSTREE_H
#define LCRSTREE_H

template<typename T>
class LcrsTree
{
    public:
        LcrsTree() {}
        virtual ~LcrsTree() {}

        static BinaryTree<T>* convert(Tree<T>* tree)
        {
            BinaryTree<T>* binaryTree = new LinkedBinaryTree<T>(tree->getValue());
            TreeList<string>* children = tree->children();
            children->begin();
            if(Tree<T>* child = children->next())
            {
                binaryTree->addLeft(convert(child));
                BinaryTree<T>* node = binaryTree->left();
                while (child = children->next())
                {
                    node->addRight(convert(child));
                    node = node->right();
                }
            }
            return binaryTree;
        }
    protected:
    private:
};

#endif // LCRSTREE_H

下载

VS2010 C#版本

Eclipse Java版本

Code::Blocks C++版本

相关文章