Reserve to Binary Tree

看完這篇
雖然我們公司 90%的工程師都用你開發的工具，但我們還是不聘用你
http://www.techbang.com/posts/24183
我驚了一下

突然問我怎麼反轉二元樹，我一點頭緒都沒有，趕緊去查答案


資料結構 - 一般樹轉二元樹

喔原來是這個簡單的原理
把一般的樹轉變為二元樹而已
因為限定每層sibling互連
所以保證一定是二元樹

規則是
1. LChild不變
2. Sibling變為RChild


LCRS Tree

從上面的轉換結果，我們可以知道這個二元樹的左子節點代表的是原來的第一個子節點，右子節點代表下一個兄弟節點，而這樣的性質的樹也稱為LCRS Tree(Left-Child-Right-Sibling Tree)。

CODE

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;
	}
	}
	}

view raw RBTC# hosted with ❤ by GitHub

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;
	}
	}

view raw RBTJava hosted with ❤ by GitHub

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

view raw RBTC++ hosted with ❤ by GitHub

原來我學過，真的要學而時習之