树的双亲表示法是用一组连续空间(数组)存储树的节点，同时在每个节点中附设一个指示器指示其双亲节点在数组中的位置。

其结构如图：

 

 

 

 

 

 

 

 

 

package tree;import java.util.*;public class PTree
    
      {	 int max=100;	 int n,root;	 int a[]=new int[max];     //用于存放孩子结点在数组中的位置	 PTNode nodes[]=new PTNode[max];	      class PTNode
     
      {   	      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
      
       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
       
        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
        
         j){    							 nodes[b-1].parent--;    						 }	        					 }     					    					 j--;    					 n--;    				 }    				      			 }    		 }    		    		 }    	 }    	     	           public AnyType getRoot(){    //返回根结点元素,根结点不一定存在数组中第一个位置    	 for(int i=0;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){ return null; } return (AnyType)getParent(p).data; } public int getChildCount(int p){ //返回孩子结点数 int count=0; for(int i=0;i
           
            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
            
             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