package Data_Structure.Tree;
import java.io.IOException;
import java.util.NoSuchElementException;
import java.util.Scanner;
//双亲表示法构造树，该树使用层序进行构造，通过parent下标索引双亲结点
public class ParentTree{
private static final int CAPACITY=100;
private Node nodes[];
private final int root;
private int length;
static class Node{private char data;private int parent;public Node(char data,int parent) {this.parent = parent;this.data = data;}public char getData(){return data;}public void setData(char val){this.data = val;}public int getParent(){return parent;}public void setParent(int index){}
}//构造函数，给数组分配内存
public ParentTree(){nodes = new Node[CAPACITY];root=0;length=0;
}//构造树结构, 输入时，按照层序排序输入
public void createTree(int n) throws IOException {if(n<=0||n>CAPACITY)throw new IllegalArgumentException("非法参数:"+ n);Scanner in =new Scanner(System.in);System.out.println("请先输入根结点元素：");nodes[0] = new Node(in.next().charAt(0),-1); //根结点没有双亲结点clearCacheArea(); //清空缓存区length++;System.out.println("输入子结点以及对应双亲结点的索引\n字符与数字输入完后回车再输入下一对");for(int i=1;i<n;i++){nodes[i] = new Node((char)System.in.read(),in.nextInt());clearCacheArea();length++;}
}//根据传入数组构造树
public void createTree(int n,char[] data,int[] parents){if(n>CAPACITY || n<=0 || data.length!= parents.length && data.length!=n)throw new IllegalArgumentException("非法参数");for(int i=0;i<n;i++){nodes[i] = new Node(data[i],parents[i]);length++;}
}public void show(){if(length<=0)throw new NoSuchElementException("无元素");for(int i=0;i<length;i++){System.out.println(nodes[i].data+": 双亲结点 "+ nodes[i].parent);}
}//清空输入缓存区
public static void clearCacheArea() throws IOException {while (System.in.available() > 0) {System.in.read();}
}// 清空该树
public void clearTree(){nodes=new Node[CAPACITY]; //分配新的内存length=0;}//判断树是否为空
public boolean treeEmpty(){return this.length == 0;
}//返回T的根结点元素
public char root(){return nodes[0].data;
}//返回树的结点数
public int getLength()
{return this.length;
}// 返回树的深度
public int treeDepth(){if(length==0)return 0;int depth=0;/*我设计让nodes[0]始终存储的为根结点所以，从下往上遍历即从数组最后一个元素往前找* *///从叶子结点往上遍历for(int i=length-1;i>=0;i--){int curDepth=0;int cursor =i; // 游标，根据当前节点的parent往上爬while(cursor!=-1){ // 如果游标不等于根结点cursor = nodes[cursor].getParent(); //就记录当前游标结点的双亲结点索引，往上爬curDepth++; //深度+1}if(curDepth>depth)depth = curDepth;}return depth;
}//返回指定结点的值
public char value(int index){if(index <0 ||index>=getLength())throw new ArrayIndexOutOfBoundsException(index +"out bound");return nodes[index].getData();
}// 赋予指定结点新值 ,并返回旧的值
public char assign(int index ,char val){if(index <0 ||index>=getLength())throw new ArrayIndexOutOfBoundsException(index +"out bound");char oldValue = nodes[index].getData();nodes[index].setData(val);return oldValue;
}//返回指定索引的双亲结点的元素
public char parent(int index ){if(index <0 ||index>=getLength())throw new ArrayIndexOutOfBoundsException(index +"out bound");if(index==0)throw new NoSuchElementException("根结点没有双亲");return nodes[nodes[index].getParent()].getData();
}// 返回指定索引的最左孩子结点data域
public char leftChild(int index){if(index<0 ||index >=length)throw new ArrayIndexOutOfBoundsException(index+"使数组溢出");//从最头开始找/*条件为，该结点的双亲结点索引 == index* 并且是第一个* */for(int i=0;i<length;i++){if(nodes[i].getParent()==index)return nodes[i].getData();}//循环结束就代表没找到，返回-return ' ';
}// 返回指定索引的最右孩子结点data域
public char rightChild(int index){if(index<0 ||index >=length)throw new ArrayIndexOutOfBoundsException(index+"使数组溢出");//从最尾开始找/*条件为，该结点的双亲结点索引 == index* 并且是第一个* */for(int i=length-1;i>=0;i--){if(nodes[i].getParent()==index)return nodes[i].getData();}//循环结束就代表没找到，返回-return ' ';
}// 双亲表示符实现插入和删除比较复杂，且不符合设计理论，双亲表示法适合需大量查询父节点的场景
// 且双亲表示法本身就是用静态数组表示，若你插入后，移动了数组，parent将全部失效，需要考虑的地方很多public static void main(String[] args) throws IOException {ParentTree tree = new ParentTree();//测试时的数据char[] data = {'R','A','B','C','D','E','F','G','H','K'};int[] parents = {-1,0,0,0,1,1,3,6,6,6};tree.createTree(10,data,parents);tree.show();System.out.println("tree的结点数为："+ tree.getLength());System.out.println("tree的深度为：" + tree.treeDepth());System.out.println("tree的根结点为："+tree.root());System.out.println("tree位于"+5+"索引的数据为"+tree.value(5));char val = 'O';System.out.println("为索引"+6+"的结点赋新值,它的旧值为："+tree.assign(6,val));tree.show();System.out.println("索引1的双亲结点元素为"+tree.parent(1));System.out.println("索引为1的结点的左孩子为 "+tree.leftChild(1));System.out.println("索引为1的结点的右孩子为 "+tree.rightChild(1));System.out.println("索引为2的结点的右孩子为 "+tree.rightChild(2));}
}