我必须在实现层中使用任何一个公共方法来确定比率（根左边的节点数）（树的大小-1），这是一棵树平衡程度的指标。这些方法中的任何一个都是用来在应用层确定上面给出的比率的.这是我的代码。
public class BinarySearchTree<T extends Comparable<T>>
implements BSTInterface<T>
{
protected BSTNode<T> root; // reference to the root of this BST
boolean found; // used by remove
// for traversals
protected ArrayQueue<T> inOrderQ;
protected ArrayQueue<T> preOrderQ;
protected ArrayQueue<T> postOrderQ;
protected LLStack<T> revOrderStack;
T[] rebalanceArray;
protected BSTNode<T> rebalanceRoot; // reference to the root of rebalancing tree
public BinarySearchTree() {
root = null;
}
public void add (T element) {
root = recAdd(element, root);
}
private BSTNode<T> recAdd(T element, BSTNode<T> tree) {
if (tree == null) {
tree = new BSTNode<T>(element);
}
else {
if (element.compareTo(tree.getInfo()) <= 0) {
tree.setLeft(recAdd(element, tree.getLeft())); // add to left subtree
}
else {
tree.setRight(recAdd(element, tree.getRight())); // add to right subtree
}
}
return tree;
}
public boolean remove (T element) {
root = recRemove(element, root);
return found;
}
private BSTNode<T> recRemove(T element, BSTNode<T> tree) {
if (tree == null) {
found = false;
}
else {
if (element.compareTo(tree.getInfo()) < 0) {
tree.setLeft(recRemove(element, tree.getLeft()));
}
else {
if (element.compareTo(tree.getInfo()) > 0) {
tree.setRight(recRemove(element, tree.getRight()));
}
else {
tree = removeNode(tree);
found = true;
}
}
}
return tree;
}
private BSTNode<T> removeNode(BSTNode<T> tree) {
T payload;
if (tree.getLeft() == null) {
return tree.getRight();
}
else {
if (tree.getRight() == null) {
return tree.getLeft();
}
else {
payload = getPredecessor(tree.getLeft());
tree.setInfo(payload);
tree.setLeft(recRemove(payload, tree.getLeft()));
return tree;
}
}
}
private T getPredecessor(BSTNode<T> tree) {
while (tree.getRight() != null) {
tree = tree.getRight();
}
return tree.getInfo();
}
public int size() {
return recSize(root);
}
private int recSize(BSTNode<T> tree) {
if (tree == null) {
return 0;
}
else {
return recSize(tree.getLeft()) + recSize(tree.getRight()) + 1;
}
}
// this implementation of a size operation demonstrates that
// it is possible to visit all the nodes of the tree without recursion
public int size2() {
int count = 0;
if (root != null) {
LLStack<BSTNode<T>> hold = new LLStack<BSTNode<T>>();
BSTNode<T> currNode;
hold.push(root);
while (!hold.isEmpty()) {
currNode = hold.peek();
hold.pop();
count++;
if (currNode.getLeft() != null) {
hold.push(currNode.getLeft());
}
if (currNode.getRight() != null) {
hold.push(currNode.getRight());
}
}
}
return count;
}
public boolean isEmpty() {
return (root == null);
}
public boolean contains (T element) {
return recContains(element, root);
}
private boolean recContains(T element, BSTNode<T> tree) {
if (tree == null) return false;
else
if (element.compareTo(tree.getInfo()) < 0)
return recContains(element, tree.getLeft()); // search left subtree
else
if (element.compareTo(tree.getInfo()) > 0)
return recContains(element, tree.getRight()); // search right subtree
else
return true; // element is found!
}
public T get(T element) {
return recGet(element, root);
}
private T recGet(T element, BSTNode<T> tree) {
if (tree == null)
return null;
else
if (element.compareTo(tree.getInfo()) < 0)
return recGet(element, tree.getLeft()); // get from left subtree
else
if (element.compareTo(tree.getInfo()) > 0)
return recGet(element, tree.getRight()); // get from right subtree
else
return tree.getInfo(); // element is found!
}
// populate inOrderQ with tree elements based on in-order traversal
private void inOrder(BSTNode<T> tree) {
if (tree != null) {
inOrder(tree.getLeft());
inOrderQ.enqueue(tree.getInfo());
inOrder(tree.getRight());
}
}
// populate preOrderQ with tree elements based on pre-order traversal
private void preOrder(BSTNode<T> tree) {
if (tree != null) {
preOrderQ.enqueue(tree.getInfo());
preOrder(tree.getLeft());
preOrder(tree.getRight());
}
}
// populate postOrderQ with tree elements based on post-order traversal
private void postOrder(BSTNode<T> tree) {
if (tree != null) {
postOrder(tree.getLeft());
postOrder(tree.getRight());
postOrderQ.enqueue(tree.getInfo());
}
}
// populate revOrderStack with tree elements in order to enable reverse order traversal
private void revOrder(BSTNode<T> tree) {
if (tree != null) {
revOrder(tree.getLeft());
revOrderStack.push(tree.getInfo());
revOrder(tree.getRight());
}
}
public int reset(TraversalType orderType) {
// returns current number of nodes in the tree
int numNodes = size();
switch (orderType) {
case INORDER :
inOrderQ = new ArrayQueue<T>(numNodes);
inOrder(root);
break;
case PREORDER :
preOrderQ = new ArrayQueue<T>(numNodes);
preOrder(root);
break;
case POSTORDER :
postOrderQ = new ArrayQueue<T>(numNodes);
postOrder(root);
break;
case REVORDER :
revOrderStack = new LLStack<T>();
revOrder(root);
break;
}
return numNodes;
}
public T getNext (TraversalType orderType) {
/*
* preconditions
* - the BST is not empty
* - the BST has been reset for orderType
* - the BST has not been modified since the most recent reset
* - application code is responsible for not iterating beyond the end of the tree
*
* Returns the element at the current position on the BST for the specified traversal type
* and advances the value of the current position.
*
*/
switch (orderType) {
case INORDER : return inOrderQ.dequeue();
case PREORDER : return preOrderQ.dequeue();
case POSTORDER: return postOrderQ.dequeue();
case REVORDER : return revOrderStack.pop();
default: return null;
}
}
/*
* PP#5 methods supporting new operations start here
*
*/
public int treeHeight() {
return recNodeHeight(root);
}
private int recNodeHeight(BSTNode<T> tree) {
if (tree == null) {
return -1;
}
if (tree.getLeft() == null && tree.getRight() == null) {
return 0;
}
if (tree.getLeft() == null && tree.getRight() != null) {
return 1 + recNodeHeight(tree.getRight());
}
if (tree.getLeft() != null && tree.getRight() == null) {
return 1 + recNodeHeight(tree.getLeft());
}
// only possibility left is two children
return 1 + Math.max(recNodeHeight(tree.getLeft()),recNodeHeight(tree.getRight()));
}
public void rebalance() {
int size = reset(TraversalType.INORDER);
rebalanceArray = (T[]) new Comparable[size];
for (int i=0; i < size; i++) {
rebalanceArray[i] = inOrderQ.dequeue();
}
rebalanceRoot = null;
recRebalance(0, size-1);
root = rebalanceRoot;
}
private void recRebalance(int first, int last) {
if (first > last) {
return;
}
else {
if (first == last) {
rebalanceRoot = recAdd(rebalanceArray[first], rebalanceRoot);
}
else {
int mid = first + (last - first) / 2;
rebalanceRoot = recAdd(rebalanceArray[mid], rebalanceRoot);
recRebalance(first, mid-1);
recRebalance(mid+1, last);
}
}
}
public int oobScore1() {
return treeHeight() - (int)(Math.log(size()) / Math.log(2));
}
public int oobScore2() {
return recOobScore2(root, 0);
}
private int recOobScore2(BSTNode<T> tree, int max) {
if (tree == null) {
return max;
}
if (tree.getLeft() == null && tree.getRight() == null) {
return max;
}
if (tree.getLeft() != null && tree.getRight() == null) {
return Math.max(max, recNodeHeight(tree));
}
if (tree.getLeft() == null && tree.getRight() != null) {
return Math.max(max, recNodeHeight(tree));
}
// tree has both a left and right child:
int heightLeft = recNodeHeight(tree.getLeft());
int heightRight = recNodeHeight(tree.getRight());
max = Math.max(max, Math.abs(heightLeft - heightRight));
int maxLeft = recOobScore2(tree.getLeft(), max);
max = Math.max(max, maxLeft);
int maxRight = recOobScore2(tree.getRight(), max);
return Math.max(max, maxRight);
}
}
我不知道该用哪种方法，因为它说的是树左边的节点数。而且我不认为有任何方法可以给我树左边的节点。我试过用size()-treeHeight()，但我不认为那有用。这是我在应用层面的代码。
public class Tree {
public static void main(String[] args) {
BinarySearchTree<String> bTree = new BinarySearchTree<String>();
bTree.add("1");
bTree.add("2");
bTree.add("3");
bTree.add("4");
bTree.add("5");
bTree.add("6");
bTree.add("7");
int size = abcTree.treeHeight() - 1;
int leftNode = abcTree.size() - abcTree.oobScore2();
double balanced = leftNode / size;
for (int i = 0; i < size; i++ ) {
if (i < leftNode) {
//abcTree.rebalance();
System.out.println(balanced);
return;
}
}
}
}
把代码放在这里，因为我发现自己为了这个答案而改变了我开始的repl.it空间。
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import static java.util.Objects.isNull;
public class Main {
public static void main(String[] args) {
System.out.println("================================================");
System.out.println("======= Unbalanced Tree =====================");
System.out.println("================================================");
printTreeData(getUnbalancedTree());
System.out.println("================================================");
System.out.println("======= Balanced Tree =======================");
System.out.println("================================================");
printTreeData(getBalancedTree());
}
private static BTree<Integer> getBalancedTree() {
BTree<Integer> tree = new BTree<>();
tree.add(15);
tree.add(10);
tree.add(16);
tree.add(4);
tree.add(2);
tree.add(36);
return tree;
}
private static BTree<Integer> getUnbalancedTree() {
BTree<Integer> tree = new BTree<Integer>();
tree.add(15);
tree.add(2);
tree.add(36);
tree.add(12);
tree.add(4);
tree.add(10);
tree.add(16);
return tree;
}
private static void printTreeData(BTree<Integer> tree) {
System.out.println("Depth: [" + tree.getDepth() + "] \nisBalanced [" + tree.isBalanced() + "]");
System.out.println("Tree --> \n" + tree);
List<Integer> values = tree.getValues();
System.out.println("Values: " + values);
}
}
class BTree<T extends Comparable<T>> {
private BNode<T> root;
public BNode<T> getRoot() {
return root;
}
public void setRoot(BNode<T> root) {
this.root = root;
}
public void add(T value) {
if (isNull(root)) {
root = new BNode<T>(value);
} else {
add(value, root);
}
}
private void add(T value, BNode<T> node) {
if (node.getValue().compareTo(value) >= 0) {
if (isNull(node.getLeft())) {
node.setLeft(new BNode<T>(value));
} else {
add(value, node.getLeft());
}
} else {
if (isNull(node.getRight())) {
node.setRight(new BNode<T>(value));
} else {
add(value, node.getRight());
}
}
}
public boolean isBalanced() {
int diff = getNodeDepth(root.getLeft()) - getNodeDepth(root.getRight());
diff = (diff < 0)? diff * -1: diff;
return (diff <= 1);
}
public List<T> getValues() {
return getValuesForNode(root);
}
private List<T> getValuesForNode(BNode<T> node) {
if (isNull(node)) return new ArrayList<>();
List<T> retList = new ArrayList<T>(getValuesForNode(node.getLeft()));
retList.add(node.getValue());
retList.addAll(getValuesForNode(node.getRight()));
return retList;
}
public int getDepth() {
return getNodeDepth(root);
}
private int getNodeDepth(BNode<T> node) {
return (isNull(node)) ? 0 :
(Math.max(getNodeDepth(node.getLeft()), getNodeDepth(node.getRight())) + 1);
}
private String getString(BNode<T> node, int level, String type) {
return ((level > 0) ? "\\" : type) +
IntStream.range(0, level).mapToObj(i -> "--").collect(Collectors.joining()) + " " +
(isNull(node) ? "None" + type + "\n" :
node.getValue() + type + "\n"
+ getString(node.getLeft(), level + 1, "[L]")
+ getString(node.getRight(), level + 1, "[R]"));
}
@Override
public String toString() {
return getString(root, 0, "Root");
}
}
class BNode<T> {
T value;
BNode<T> left;
BNode<T> right;
public BNode(T value) {
this.value = value;
left = null;
right = null;
}
public T getValue() {
return value;
}
public BNode<T> getLeft() {
return left;
}
public void setLeft(BNode<T> left) {
this.left = left;
}
public BNode<T> getRight() {
return right;
}
public void setRight(BNode<T> right) {
this.right = right;
}
}