不过楼主的类架构似乎差了点,
TreeNode 与 Tree应该成为两个独立的概念才对啊,
一棵树是一个独立的概念,他引用了0...n个TreeNode。下面是我自己平时做的Tree class的最基本架构,和大家分享一下,希望大家给出意见public class Tree {
// Constuctors
public Tree() { root = null; }
public boolean isEmpty() {
return root == null ? true : false;
}
public void clear() { root = null; }
public Object find( Object x ) {
/*
* Do something
* ......
*/
}
public void insert( Object x ) {
/*
* Do something
* ......
*/
}
public void remove( Object x ) {
/*
* Do something
* ......
*/
}
public String toString() {
/*
* Do something
* ......
*/
}
private TreeNode root; // The root of the tree.
class TreeNode {
Object element;
TreeNode firstChild;
TreeNode nextSibling;
// Constructors
TreeNode( Object element ) { this( element, null, null ); }
TreeNode( Object element, TreeNode firstChild, TreeNode nextSibling ) {
this.element = element;
this.firstChild = firstChild;
this.nextSibling = nextSibling;
}
}
} ///@.@||~一棵树将引用0...n个树节点,由于一个根或者一个子根将拥有可能多个孩子,
所以在TreeNode class中,我放了对第一个孩子节点的引用以及,该节点对于下一个兄弟节点的引用。
TreeNode 与 Tree应该成为两个独立的概念才对啊,
一棵树是一个独立的概念,他引用了0...n个TreeNode。下面是我自己平时做的Tree class的最基本架构,和大家分享一下,希望大家给出意见public class Tree {
// Constuctors
public Tree() { root = null; }
public boolean isEmpty() {
return root == null ? true : false;
}
public void clear() { root = null; }
public Object find( Object x ) {
/*
* Do something
* ......
*/
}
public void insert( Object x ) {
/*
* Do something
* ......
*/
}
public void remove( Object x ) {
/*
* Do something
* ......
*/
}
public String toString() {
/*
* Do something
* ......
*/
}
private TreeNode root; // The root of the tree.
class TreeNode {
Object element;
TreeNode firstChild;
TreeNode nextSibling;
// Constructors
TreeNode( Object element ) { this( element, null, null ); }
TreeNode( Object element, TreeNode firstChild, TreeNode nextSibling ) {
this.element = element;
this.firstChild = firstChild;
this.nextSibling = nextSibling;
}
}
} ///@.@||~一棵树将引用0...n个树节点,由于一个根或者一个子根将拥有可能多个孩子,
所以在TreeNode class中,我放了对第一个孩子节点的引用以及,该节点对于下一个兄弟节点的引用。
我把原来的贴一下:
import java.util.*;
public class TreesNode
{
TreesNode(Object element)
{
this.element=element;
count=0;
LinkedList lklist=new LinkedList();
}
public void getElement()
{
System.out.println( element);
}
public int getCount()
{
return count;
}
public LinkedList getLinkedList()
{
return lklist;
}
public void setCount(int count)
{
this.count=this.count+count;
}
public void setElement(Object element)
{
this.element=element;
}
public boolean equal(Object element)
{
return this.element==element;
}
private Object element;
private int count;
private LinkedList lklist;
public TreesNode node;
}import java.util.*;
public class Tree
{
Tree(TreesNode root)
{
this.root=root;
}
public void preOrder(TreesNode root,Object[][] arraylist,int i,int j)
{
root.setElement((String)arraylist[i][j++]);
root.setCount(1);
LinkedList itr=new LinkedList();
if (root.getLinkedList().isEmpty())
{
root.getLinkedList().add(new TreesNode(arraylist[i][j]));
itr=root.getLinkedList();
preOrder((TreesNode)itr.getLast(),arraylist,i,j);
}
else
{
TreesNode tempnode=new TreesNode("");
tempnode = (TreesNode)itr.listIterator().next();
int k=0;
if(j<=arraylist[i].length)
{
do
{
if(tempnode.equal(arraylist[i][j]))
preOrder(tempnode,arraylist,i,j); //继续向下走
k++;
}
while(itr.listIterator().hasNext());
if(itr.size()<=k)
{ //新建子节点
itr.add(new TreesNode(arraylist[i][j]));
preOrder((TreesNode)itr.getLast(),arraylist,i,j);
}
}//end if
}//end else
i++;
}
private TreesNode root;
}import java.util.*;
public class TreeTest
{
public static void main(String args[])
{
String[][] arraylist=new String[][]{{"","i2","i1","i5"},{"","i2","i1","i3","i5"},{"","i2","i1","i4"},{"","i2","i3"},{"","i2","i4"},{"","i1","i3"}};
//ArrayList doubarray=new ArrayList
/*int i=0;int j=0;
System.out.println(arraylist.length);
for(;i<arraylist.length;i++)
for(j=0;j<arraylist[i].length;j++)
System.out.println(i+" "+j+" "+arraylist[i][j]);*/
TreesNode root=new TreesNode("");
root.preOrder(arraylist,0,0);
}
}编译肯定能通过,但是链接 不行
希望高手们解答啊
public void preOrder(TreesNode root,Object[][] arraylist,int i,int j)
定义在Tree里面.
那下面这段代码是什么意思啊?
TreesNode root=new TreesNode("");
root.preOrder(arraylist,0,0);
首先,问题很明显出在下列方法的第一个if中,事实上else永远也不会被触发,因为每一次第归调用
所引用的TreesNode,起LinkedList均为空,所以,不断调用的事实是,永远按照左边排成了个最差情况的树结构,即一个链表结构。
public void preOrder( TreesNode root, Object[][] arraylist, int i, int j ) {
root.setElement( (String)arraylist[i][j++] );
root.setCount(1);
LinkedList itr = new LinkedList();
// Warning, Warning, Warning!!!
if( root.getLinkedList().isEmpty() ) {
root.getLinkedList().add( new TreesNode(arraylist[i][j]) );
itr = root.getLinkedList();
preOrder( (TreesNode)itr.getLast(), arraylist, i, j );
}
else {
TreesNode tempnode = new TreesNode("");
tempnode = (TreesNode)itr.listIterator().next();
int k = 0;
if( j <= arraylist[i].length ) {
do {
if( tempnode.equal(arraylist[i][j]) )
preOrder( tempnode,arraylist, i, j ); //继续向下走
k++;
} while( itr.listIterator().hasNext() );
if( itr.size() <= k ) { //新建子节点
itr.add( new TreesNode(arraylist[i][j]) );
preOrder((TreesNode)itr.getLast(),arraylist,i,j);
}
}//end if
}//end else
i++;
}
==========================================================================
e.........
其次,上段代码的逻辑错误即使被修正了,也未必能运行的起来,因为还有一些错误(也可能不是)
==========================================================================
e.........
再次,楼主在架构和树概念方面确实非常混乱,可以尝试使用在下的架构来实现这棵树结构,
楼主的概念错误,包括TreesNode应该只为Tree内部调用,而不该变成public修饰,树内部的业务逻辑应该完全与外界屏蔽,否则偶合度实在太高,越修改,越混乱。另外初始化一棵树应该public Tree() { root = null; },
上述方法才是构造一棵树的正确方法,即节点为null,而非直接赋予了一个节点,节点必须添加。还有包括TreesNode中的
private int count; // What's mean?
public TreesNode node; // What's mean?
======================================================================
e.........
最后提个小建议^^
楼主莫生气,不过在下愚笨,看代码实在是非常苦累的差使,我想楼主也深有同感吧。
恩,如果能够在方法面前写明该方法的作用,所调用的参量作用,返回的值是什么,已经该方法所要注意的一些方法的话,那么他人阅读您的代码将会很愉快,呵呵,我真得读的头痛了,抱歉,抱歉。@.@||~
代码附上:
package tree;
import java.util.*;
public class TreesNode
{
TreesNode(Object element)
{
this.element=element;
count=0;
lklist=new LinkedList();
}
public void getElement()
{
System.out.println( element);
}
public int getCount()
{
return count;
}
public LinkedList getLinkedList()
{
return lklist;
}
public void setCount(int count)
{
this.count=this.count+count;
}
public void setElement(Object element)
{
this.element=element;
}
public boolean equal(Object element)
{
return this.element==element;
} private Object element;
private int count;
private LinkedList lklist;
}package tree;
import java.util.*;
public class Tree{
Tree(TreesNode root)
{
this.root=root;
}
public void preOrder(TreesNode roots,Object[][] arraylist,int i,int j)
{ if (i<arraylist.length){//// confirm the row
roots.setElement( (String) arraylist[i][j]);
System.out.println(arraylist[i][j]);
j=j+1;
roots.setCount(1);
LinkedList itr = new LinkedList();
if(j < arraylist[i].length)
{//confirm the column
if (roots.getLinkedList().isEmpty()) { //lklist is empty
roots.getLinkedList().add(new TreesNode(arraylist[i][j]));
//System.out.println(arraylist[i][j]);
itr = roots.getLinkedList();
preOrder( (TreesNode) itr.getFirst(), arraylist, i, j);
}
else if (j < arraylist[i].length) {// lklist is not empty and arraylist[i][j]is the arraylist[i]
TreesNode tempnode = new TreesNode("");
tempnode = (TreesNode) roots.getLinkedList().listIterator().next();
int k = 0;
while (itr.listIterator().hasNext()){
if (tempnode.equal(arraylist[i][j]))
preOrder(tempnode, arraylist, i, j); //继续向下走
k++;
} if (itr.size() <= k)
{ //新建子节点
itr.add(new TreesNode(arraylist[i][j]));
//System.out.println(arraylist[i][j]);
preOrder( (TreesNode) itr.getLast(), arraylist, i, j);
}
} //end else
}
}
}
private TreesNode root;
}package tree;
import java.util.*;
public class TreeTest
{
public static void main(String args[])
{
String[][] arraylist=new String[][]{{"","i2","i1","i5"},{"","i2","i1","i3","i5"},{"","i2","i1","i4"},{"","i2","i3"},{"","i2","i4"},{"","i1","i3"}};
//ArrayList doubarray=new ArrayList
/*int i=0;int j=0;
System.out.println(arraylist.length);
for(;i<arraylist.length;i++)
for(j=0;j<arraylist[i].length;j++)
System.out.println(i+" "+j+" "+arraylist[i][j]);*/ TreesNode root=new TreesNode("");
Tree tree=new Tree(root);
for(int i=0; i<arraylist.length;i++)
tree.preOrder(root,arraylist,i,0);
}
}
结帖时再给分
public boolean OrderFun(Object e);
}class PreOrederFun implements OrderFun{
public boolean OrderFun(Object e){
System.out.println(e);
return true;
}
}class TreeNode{
private Object elem;
private LinkedList list = new LinkedList(); public TreeNode(Object e){
this.elem = e;
} public void addChild(TreeNode t){
list.addLast(t);
} public void removeChild(TreeNode t){
list.remove(t);
} public boolean isChild(TreeNode t){
return list.contains(t);
} public ListIterator getChilds(int iIndex){
return list.listIterator(iIndex);
} public ListIterator getChilds(){
return list.listIterator();
} public TreeNode getChild(Object e){
Iterator it = list.listIterator();
while(it.hasNext()){
TreeNode t = (TreeNode)it.next();
if(t.elem.equals(e))
return t;
}
return null;
} public String toString(){
return elem.toString();
}
}public class Tree { private TreeNode root = new TreeNode("root"); public TreeNode getRoot(){
return root;
} public boolean preOreder(OrderFun order){
Stack s = new Stack();
s.push(root);
while(!s.empty()){
TreeNode temp = (TreeNode)s.pop();
if(!order.OrderFun(temp))
return false;
ListIterator it = temp.getChilds();
while(it.hasNext())
s.push(it.next());
}
return true;
} public static void main(String[] args){
Tree myTree = new Tree();
TreeNode t = myTree.getRoot();
TreeNode test = new TreeNode("test");
t.addChild(test);
t.addChild(new TreeNode("test2"));
test.addChild(new TreeNode("hello"));
myTree.preOreder(new PreOrederFun());
}
}
public boolean OrderFun(Object e);
}class PreOrederFun implements OrderFun{
public boolean OrderFun(Object e){
System.out.println(e);
return true;
}
}class FillTree implements OrderFun{
private Object[][] arraylist;
private int iLine;
public FillTree(Object[][] arraylist){
this.arraylist = arraylist;
iLine = 0;
}
public boolean OrderFun(Object e){
if(iLine >= arraylist.length)
return false;
TreeNode t = (TreeNode)e;
for(int j=0;j<arraylist[iLine].length;j++)
t.addChild(new TreeNode(arraylist[iLine][j]));
iLine++;
return true;
}}
class TreeNode{
private Object elem;
private LinkedList list = new LinkedList(); public TreeNode(Object e){
this.elem = e;
} public void addChild(TreeNode t){
list.addLast(t);
} public void removeChild(TreeNode t){
list.remove(t);
} public boolean isChild(TreeNode t){
return list.contains(t);
} public ListIterator getChilds(int iIndex){
return list.listIterator(iIndex);
} public ListIterator getChilds(){
return list.listIterator();
} public TreeNode getChild(Object e){
Iterator it = list.listIterator();
while(it.hasNext()){
TreeNode t = (TreeNode)it.next();
if(t.elem.equals(e))
return t;
}
return null;
} public String toString(){
return elem.toString();
}
}public class Tree { private TreeNode root = new TreeNode("root"); public TreeNode getRoot(){
return root;
} public boolean preOreder(OrderFun order){
Stack s = new Stack();
Stack sTemp = new Stack();
s.push(root);
while(!s.empty()){
TreeNode temp = (TreeNode)s.pop();
if(!order.OrderFun(temp))
return false;
ListIterator it = temp.getChilds();
while(it.hasNext())
sTemp.push(it.next());
while(!sTemp.empty())
s.push(sTemp.pop());
}
return true;
} public static void main(String[] args){
Tree myTree = new Tree();
String[][] arraylist=new String[][]{{"","i2","i1","i5"},{"","i2","i1","i3","i5"},{"","i2","i1","i4"},{"","i2","i3"},{"","i2","i4"},{"","i1","i3"}};
myTree.preOreder(new FillTree(arraylist));
myTree.preOreder(new PreOrederFun());
}
}