/**
*
本类为树（多叉，双亲存储）的结点

* @version 1.0, 2008-01-23
* @author 
* @since JDK1.6
*/
public class TNode
{
/**结点的数据*/
char data;
/**双亲的位置*/
int parent;

/**
* 构造一个结点（同时设置数据和双亲位置）
*
* @param c char 数据
* @param e int 双亲位置
*/
public TNode(char c,int e)
{
data = c;
parent = e;

}

/**
* 获得结点的数据
*
* @return char 结点的数据
*/
public char getData()
{
return data;
}
/**
* 获得双亲的位置
*
* @return int 双亲的位置
*/
public int getParent()
{
return parent;
}

/**
* 显示提示“输入子结点”,显示当前结点的数据并提示输入其孩子结点
*
*/
public void showInputChild()
{
System.out.println("请输入"+data+"的孩子结点，回车结束：");
}

}

Tree.java

import java.util.*;

/**
*
本类实现了树（多叉）的双亲存储

* @version 1.0, 2008-01-23
* @author 
* @since JDK1.6
*/
public class Tree
{
/**存储区最大结点数，值为{@value}*/
private static int MAX =100;
/**结点存储区*/
private TNode [] elem = new TNode[MAX];
/**结点数量*/
int n = 0;

/**
* 构造函数，调用构造树
*
*/
public Tree()
{
createTree();
}

/**
* 构造树
*
*/
public void createTree()
{
Scanner scan = new Scanner(System.in);
scan.useDelimiter("\n");
String str = null;
int i = 0;
LinkedList<Integer> list = new LinkedList<Integer>();

//设置根节点
System.out.println("请输入根结点的值");

if(scan.hasNext())
{
str = scan.next();
}
elem[i] = new TNode(str.charAt(0),-1);
list.add(i);
i++;

//依次获得子结点
while(!list.isEmpty() && i<MAX)
{
int parent = list.remove();
TNode t = elem[parent];
t.showInputChild();
str = scan.next();

for(int j=0;j<str.length();j++)
{
elem[i] = new TNode(str.charAt(j),parent);
list.add(i);
i++;
}
}
//更新树结点数量
n = i;

//结点超出存储区处理
if(i==MAX)
{
System.out.println("构造失败，超过大小！");
System.exit(-1);
}

}

/**
* 获得树的深度
*
* @return int 当前树的深度
*/
public int treeDepth()
{
int i,j,m,max = 1;
for(i = 0;i<n;i++)
{
m = 0;
j = i;
while(elem[j].getParent()!=-1)
{
j = elem[j].getParent();
m++;
}

if(m>max)
{
max = m;
}
}

return max;
}

/**
* 获得树的结点数量
*
* @return int 结点数量
*/
public int nodeNum()
{
return n;
}

/**
* “层序”遍历树
*
*/
public void traverse()
{
System.out.println("结点数据\t双亲");
System.out.format("%8c\n",elem[0].getData());
for(int i=1;i<n;i++)
{
System.out.format("%8c\t%4c\n", elem[i].getData(),elem[elem[i].getParent()].getData());
}
}

/**
* 获得某结点的双亲结点
*
* @param i int 结点在数组种的存储位置
* @return char 双亲结点的数据
*/
public char getParent(int i)
{
return elem[elem[i].getParent()].getData();
}

/**
* 根据数据定位某结点位置
*
* @param char c 要查找的结点数据
* @return int 结点的位置
*/
public int getPos(char c)
{
for(int i=0;i<n;i++)
{
if(elem[i].getData()==c)
{
return i;
}
}

return -1;
}

/**
* 获得某结点的所有孩子结点
*
* @param char c 要查找的结点数据
*/
public void getChilds(char c)
{
int pos = getPos(c);
if(pos==-1)
{
System.out.println("结点"+c+"不存在.");
return ;
}
getChilds(pos);
}
/**
* 获得某结点的所有孩子结点
*
* @param int i 要查找的结点在数组种的下标
*/
public void getChilds(int i)
{
System.out.print(elem[i].getData()+"的孩子有：");
for(int j = 0;j<n;j++)
{
if(elem[j].getParent()==i)
{
System.out.print(elem[j].getData()+" ");
}
}
System.out.println("\n");
}

/**
* 获得某结点的最左孩子结点
*
* @param char c 要列出左孩子结点的双亲结点的数据
* @return char 左孩子结点的数据
*/
public char leftChild(char c)
{
int pos = getPos(c);

if(pos==-1)
{
if(pos==-1)
{
System.out.println("结点"+c+"不存在.");
}
}

for(int i=pos+1;i<n;i++)
{
if(elem[i].getParent() == pos)
{
return elem[i].getData();
}
}

return 1;
}

/**
* 获得某结点的最右孩子结点
*
* @param char c 要列出右孩子结点的双亲结点的数据
* @return char 右孩子结点的数据
*/
public char rightChild(char c)
{
int pos = getPos(c);

if(pos==-1)
{
if(pos==-1)
{
System.out.println("结点"+c+"不存在.");
}
}

for(int i=n-1;i>=pos+1;i--)
{
if(elem[i].getParent() == pos)
{
return elem[i].getData();
}
}

return 1;
}
/**
* 获得某结点的右兄弟结点
*
* @param char c 要列出右孩子结点的结点
* @return char 右兄弟结点的数据
*/
public char rightSibling(char c)
{
int pos = getPos(c);

if(pos==-1)
{
System.out.println("结点"+c+"不存在.");
return 0;
}

int p1 = elem[pos+1].getParent();
if(p1 == elem[pos].getParent())
return elem[pos+1].getData();
else
return 1;
}

/**
* 判断某树是否为空
*
* @return boolean 空则返回为true，否则返回false
*/
public boolean isTreeEmpty()
{
return n==0;
}

/**
* 测试函数
*
*/
public static void main(String [] args)
{
Tree t = new Tree();

System.out.println("共有结点"+t.nodeNum()+"个，树高度："+t.treeDepth());
t.traverse();
System.out.println("F的左孩子结点为"+t.leftChild('F'));
System.out.println("F的右孩子结点为"+t.rightChild('F'));
System.out.println("H的右兄弟结点为"+t.rightSibling('H'));
t.getChilds('R');
}
}