/**
* BST樹的節點類型
* @param <T>
*/
class BSTNode <T extends Comparable<T>>{
private T data; // 資料域
private BSTNode<T> left; // 左孩子域
private BSTNode<T> right; // 右孩子域
public BSTNode(T data, BSTNode<T> left, BSTNode<T> right) {
this.data = data;
this.left = left;
this.right = right;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public BSTNode<T> getLeft() {
return left;
}
public void setLeft(BSTNode<T> left) {
this.left = left;
}
public BSTNode<T> getRight() {
return right;
}
public void setRight(BSTNode<T> right) {
this.right = right;
}
}
/**
* BST樹的實作
* @param <T>
*/
class BST<T extends Comparable<T>>{
private BSTNode<T> root; // 指向根節點
/**
* BST樹的初始化
*/
public BST() {
this.root = null;
}
public void rebuild(T[] pre, T[] in) {
this.root = rebuild(pre,0,pre.length-1,
in,0,in.length-1);
}
private BSTNode<T> rebuild(T[] pre, int i, int j, T[] in, int m, int n) {
if (i>j||m>n){
return null;
}
BSTNode<T> node = new BSTNode<>(pre[i], null, null);
for(int k=m; k<=n; ++k){
// 在中序數組種找到根節點pre[i] m, k-1 k+1,n
if(pre[i].compareTo(in[k]) == 0){
node.setLeft(rebuild(pre,i+1,i+(k-m),in,m,k-1));
node.setRight(rebuild(pre,i+(k-m)+1,j,in,k+1,n));
break;
}
}
return node;
}
}