樹的雙親表示法是用一組連續空間(數組)存儲樹的節點，同時在每個節點中附設一個訓示器訓示其雙親節點在數組中的位置。
其結構如圖：
package tree;
import java.util.*;
public class PTree<AnyType> {
int max=100;
int n,root;
int a[]=new int[max]; //用于存放孩子結點在數組中的位置
PTNode nodes[]=new PTNode[max];
class PTNode<AnyType>{
AnyType data;
int parent;
public PTNode(AnyType d,int p){
this.data=d;
this.parent=p;
}
}
public PTree(){
n=0;
}
public boolean isEmpty(){ //判斷是否為空
return n==0;
}
public PTNode assign(AnyType d,int p){ //給結點指派
PTNode newNode=new PTNode(d,p);
return newNode;
}
public void insert(AnyType d,int p){ //添加新結點，給定結點位置
nodes[n]=assign(d,p);
n++;
}
public void insert(PTree tree,int p){ //添加子樹,給定結點位置
int m=n; //m為tree非根結點雙親位置的增加值
AnyType value=(AnyType)tree.getRoot();
insert(value,p);
for(int i=1;i<tree.n;i++){
AnyType x=(AnyType)tree.getData(i);
insert(x,tree.nodes[i].parent+m); //将tree的非根結點的雙親位置都加m後添加到另一個樹中
}
}
public void insert(PTree tree,AnyType d){ //添加子樹,給定結點data
int idx=0;
for(int i=0;i<n;i++){
int x=((String)(nodes[i].data)).compareTo((String)d);
if(x==0)
idx=i;
}
int m=n; //m為tree非根結點雙親位置的增加值
AnyType value=(AnyType)tree.getRoot();
insert(value,idx);
for(int i=1;i<tree.n;i++){
AnyType x=(AnyType)tree.getData(i);
insert(x,tree.nodes[i].parent+m); //将tree的非根結點的雙親位置都加m後添加到另一個樹中
}
}
public void delete(int p){
if(p>n)
System.out.println("資料不存在");
else if(getChildCount(p)==0){ //葉子
if(p==(n-1)){ //數組的最後一個
nodes[p].data=null;
nodes[p].parent=-2;
}
int k;
for(k=p+1;k<n;k++){
nodes[k-1]=nodes[k]; //令被删除的結點後面的結點向前平移
if(nodes[k].parent>p)
nodes[k].parent--;
}
n--;
}
else{
int dep=getDepth(p);
int num[]=new int[n];
num[0]=p;
int count=1,par=0;
for(int i=0;i<n;i++){
int d=getDepth(i);
par=nodes[i].parent;
while(par!=-1){
if(par==p){
num[count]=i;
count++;
break;
}
par=nodes[par].parent;
d--;
}
}
AnyType a[]=(AnyType[])new Object[count];
for(int i=0;i<count;i++){
a[i]=(AnyType)nodes[num[i]].data;
}/*
System.out.println(a.length);
for(int i=0;i<count;i++){
System.out.println(a[i]);
}*/
int j;
for(j=0;j<n;j++){
for(int x=0;x<a.length;x++){
int y=((String)nodes[j].data).compareTo((String)a[x]);
if(y==0){
int b;
for(b=j+1;b<n;b++) {
nodes[b-1]=nodes[b];
if(nodes[b].parent>j){
nodes[b-1].parent--;
}
}
j--;
n--;
}
}
}
}
}
public AnyType getRoot(){ //傳回根結點元素,根結點不一定存在數組中第一個位置
for(int i=0;i<n;i++){
if(nodes[i].parent==-1)
return (AnyType)nodes[i].data;
}
return null;
}
public AnyType getData(int i){ //傳回序号為i的結點的資料
if(i>n){
return null;
}
return (AnyType)nodes[i].data;
}
public PTNode getParent(int p){ //傳回父母結點,給定該結點位置
int pare=nodes[p].parent;
return nodes[pare];
}
public PTNode getParent(AnyType d){ //傳回父母結點，給定該結點data
int p=0;
for(int i=0;i<n;i++){
int x=((String)(nodes[i].data)).compareTo((String)d);
if(x==0)
p=i;
}
int pare=nodes[p].parent;
return nodes[pare];
}
public AnyType getParentData(int p){ //傳回父母結點元素
if(p>n){
return null;
}
return (AnyType)getParent(p).data;
}
public int getChildCount(int p){ //傳回孩子結點數
int count=0;
for(int i=0;i<n;i++){
if(nodes[i].parent==p){
a[count]=i; //将該結點的孩子結點在數組中的位置存下來
count++;
}
}
return count;
}
public int getChildCount(AnyType d){ //傳回孩子結點數,給定結點值
int p=0;
for(int i=0;i<n;i++){
int x=((String)(nodes[i].data)).compareTo((String)d);
if(x==0)
p=i;
}
int count=0;
for(int i=0;i<n;i++){
if(nodes[i].parent==p){
a[count]=i; //将該結點的孩子結點在數組中的位置存下來
count++;
}
}
return count;
}
public PTNode getFirstChild(int p){ //獲得第一個孩子結點
int c=getChildCount(p); //得到孩子結點個數
PTNode kong=new PTNode(null,-2);
if(c==0){
return kong;
}
else{
return nodes[a[0]];
}
}
public PTNode getNextChild(int p){
PTNode kong=new PTNode(null,-2);
int c=getChildCount(nodes[p].parent); //執行求該結點的雙親結點的孩子結點的個數的方法，以獲得儲存其兄弟結點在數組中的位置的數組及孩子個數
int next=0;
for(int i=0;i<c;i++){
if(a[i]==p){
if(i+1<c){ //判斷p是否有下一個兄弟結點
next=a[i+1]; //若有，獲得p的兄弟結點的位置 ，跳出循環
break;
}
else
return kong; //沒有，傳回null
}
}
return nodes[next]; //傳回兄弟結點
}
public int depth(){
int max=0,height,p=0;//max記錄目前的最大高度，p記錄雙親結點的位置，height為目前的深度
for(int i=0;i<n;i++){
height=1; //每次循環開始，初始化height
p=nodes[i].parent;
while(p!=-1){ //若目前結點不是根結點，執行此循環
p=nodes[p].parent; //不斷沿雙親結點向上走
height++; //沒向上一步，高度加一
}
if(height>max) //記錄目前最大深度
max=height;
}
return max;
}
public int getDepth(int m){ //獲得某一結點所處的層次
if(m>n)
return -2;
int max=0,height,p=0;
for(int i=0;i<n;i++){
height=1; //每次循環開始，初始化height
p=nodes[m].parent;
while(p!=-1){ //若目前結點不是根結點，執行此循環
p=nodes[p].parent; //不斷沿雙親結點向上走
height++; //沒向上一步，高度加一
}
if(height>max) //記錄目前最大深度
max=height;
}
return max;
}
public static void main(String[] args) {
PTree pt=new PTree();
PTree tr=new PTree();
pt.insert("aaa",-1);
pt.insert("bbb",0);
pt.insert("ccc",0);
pt.insert("ddd",1);
pt.insert("eee",2);
pt.insert("fff",2);
pt.insert("ggg",4);
tr.insert("A",-1);tr.insert("B",0);tr.insert("C",0);
pt.insert(tr,"ddd");
for(int i=0;i<10;i++){
System.out.println( pt.getData(i));
}
System.out.println("******************");
System.out.println( pt.n);
System.out.println("******************");
System.out.println( pt.getRoot());
System.out.println("******************");
System.out.println( pt.getParent("fff").data);
System.out.println("******************");
System.out.println( pt.getDepth(9));
System.out.println("******************");
System.out.println(pt.getFirstChild(3).data);
System.out.println("******************");
pt.delete(1);
System.out.println( pt.n);
System.out.println( pt.n);
for(int i=0;i<pt.n;i++){
System.out.println( pt.getData(i));
}
}
}
![HDU 6232 Confliction[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)