John Zhao
BAN USERJob Seeker
Here is my solution in JAVA. It's tested.
----------InputString.java----------
package TreeTest;
public class InputString
{
public char[] inputStringArray;
public int index = 0;
public InputString(String str)
{
inputStringArray = str.toCharArray();
}
public char next()
{
char tmp = 0;
if (index < inputStringArray.length)
{
tmp = inputStringArray[index];
index++;
}
return tmp;
}
public String toString()
{
String result = "";
if(inputStringArray.length>0)
{
for(int i=0; i<inputStringArray.length; i++)
{
result += String.valueOf(inputStringArray[i]);
}
}
return result;
}
}
----------Link.java----------
package TreeTest;
public class Link<T>
{
public T element;
public Link<T> child;
public Link<T> sibling;
public Link(T data)
{
this.element = data;
child = null;
sibling = null;
}
public Link<T> addChild(T data)
{
Link<T> newnode = new Link<T>(data);
child = newnode;
return newnode;
}
public Link<T> addSibling(T data)
{
Link<T> newnode = new Link<T>(data);
sibling = newnode;
return newnode;
}
}
----------Tree.java----------
package TreeTest;
public class Tree<T>
{
public Link<T> root;
public int num;//how many nodes
public Tree()
{
root = null;
num = 0;
}
public Link<T> addChild(Link<T> parentLink, T newValue)
{
num++;
if (null == parentLink)
{
root = new Link<T>(newValue);
return root;
}
else
{
return parentLink.addChild(newValue);
}
}
public Link<T> addSibling(Link<T> currentLink, T newValue)
{
num++;
return currentLink.addSibling(newValue);
}
public void serialize()
{
if (null == root)
{
System.out.println("No tree can be serialized.");
return;
}
else
{
preorderViewTree(root);
}
}
public void preorderViewTree(Link<T> node)
{
if ( null == node )
{
return;
}
else
{
System.out.print(node.element + "<");
if(null != node.child)
{
preorderViewTree(node.child);
}
System.out.print(">");
preorderViewTree(node.sibling);
}
}
public void deSerialize(String str)
{
if( null == str || "" == str)
System.out.println("Please input a tree string.");
else
{
InputString inStr = new InputString(str.replace("<",""));// "<" is useless for creating a tree.
//1: add sibling 2: add child
preorderCreateTree(root, 2, inStr);
}
}
public void preorderCreateTree(Link<T> pnode, int relation, InputString inputStr)
{
char currentStr = inputStr.next();
if ( currentStr == 0)
return;
/* for debug-------------------------------------
System.out.print("CurrentChar: "+ currentStr +" Tree:");
this.serialize();
System.out.println("");
----------------------------------------------*/
if('>' == currentStr)
{
return;
}
else
{
if(relation == 1)
pnode = this.addSibling(pnode,(T)String.valueOf(currentStr));
else
pnode = this.addChild(pnode, (T)String.valueOf(currentStr));
preorderCreateTree(pnode, 2, inputStr);//child
preorderCreateTree(pnode, 1, inputStr);//sibling
}
}
}
----------HandleTree.java----------
package TreeTest;
public class HandleTree
{
public static void main(String argus[])
{
Tree<String> tree = new Tree<String>();
/*
tree.addChild(tree.addChild(tree.addChild(null, "A"), "B"), "E");
tree.addChild(tree.addSibling(tree.addSibling(tree.root.child, "C"), "D"), "F");
tree.serialize();
System.out.println("");
*/
tree.deSerialize("A<B<E<>>C<>D<F<>>>");
tree.serialize();
System.out.println("");
System.out.println("How many nodes:" + tree.num);
}
}
Make a new empty array, loop the input array for each element. Take the first element and save to the new array; take the second one and compare if it's same as all elements in the new array before you save it onto. Continue this process until reaches the end of the input array.
- John Zhao September 25, 2013
Do we need a very long codes? Here is my simplest one.
- John Zhao November 04, 2013