0
getHeight（）メソッドに問題があり、ツリーの正しい高さが返されません。問題は私のQueueListクラスと関係がありますが、私の人生は問題を解決できません。バイナリ検索をよりうまく実装する方法についての提案があります。以下は私のQueueListクラスです。queueListを使用してバイナリツリーの高さを調べる
package lab5;
import java.util.NoSuchElementException;
public class QueueList<E> implements Queue<E> {
private Node<E> front;
private Node<E> rear;
private int size = 0;
public QueueList (E it){
front = rear = new Node<E>(it);
size++;
}
public QueueList(){
front = rear = new Node<E>();
size=0;
}
public boolean isEmpty() {
return size==0;
}
public void enqueue(E it) {
rear.setNext(rear);
rear.setElement(it);
size++;
}
public void clear() {
front=new Node<E>();
rear=new Node<E>();
front.setNext(null);
rear.setNext(null);
front.setNext(null);
size=0;
}
public int size() {
return size;
}
public E front() {
return front.getElement();
}
public E dequeue() {
Node<E> temp = front;
if(isEmpty()){
throw new NoSuchElementException();
}
else{
front = front.getNext();
size--;
return temp.getElement();
}
}
}
私のバイナリ検索ツリークラスは、私のBSTNodeメソッドはすべて正しく動作するので、問題はないと仮定します。それは、高さ= 0の空の木のために返すこと
public int getHeight() {
return getHeight(root, 0);
}
private int getHeight(BSTNode node, int currentHeight) {
if (node == null) {
return currentHeight;
}
int rightHeight = getHeight(node.getRight(), currentHeight + 1)
int leftHeight = getHeight(node.getLeft(), currentHeight + 1);
return Math.max(rightHeight, leftHeight);
}
注：バイナリツリーを扱うときに再帰は非常に人気があるので
package lab5;
public class BinarySearchTree<E extends Comparable<E>> {
private BSTNode root;
private int size;
public BinarySearchTree() {
root = null;
size = 0;
}
public BinarySearchTree(BSTNode node) {
root = node;
size = 1;
}
/**
* searches for a node that contains it.
*
* if it finds it, it returns that node
*
* else it returns null
*
* @param it
* - the element to look for
*
* @return the node that contains it
*
*/
public BSTNode search(E it) {
BSTNode<E> parent = null;
BSTNode<E> child = null;
BSTNode<E> node = root;
while (node != null && node.getElement() != it) {
parent = node;
int compareResult = it.compareTo(node.getElement());
if (compareResult < 0) {
node = node.getLeft();
} else {
node = node.getRight();
}
}
if (node == null) {
return null;
}
return node;
}
/**
* determines if the tree contains the element
*
* @return true if it is in the tree
*
*/
public boolean contains(E it) {
return (search(it) != null);
}
/**
* Add the element to the correct location
*
* all elements to the left are less than the parent
*
* all elements to the rights are greater than the parent
*
* Do not allow duplicates
*
* @param it
* the element to insert
*
*/
public void insert(E it) {
BSTNode<E> newNode = new BSTNode<E>(it);
if (root == null) {
root = newNode;
return;
}
BSTNode<E> parent = null;
BSTNode<E> node = root;
while (node != null) {
parent = node;
int compareResult = it.compareTo(node.getElement());
if (compareResult < 0) {
node = node.getLeft();
} else if (compareResult > 0) {
node = node.getRight();
} else {
// duplicate
return;
}
}
int res = it.compareTo(parent.getElement());
if (res < 0) {
parent.setLeft(newNode);
} else {
parent.setRight(newNode);
}
size++;
}
/**
* Removes the node that contains it.
*
* If the tree does not contain it, it prints that to
*
* the user and does nothing else.
*
* Otherwise it removes the node and maintains the
*
* BST properties
*
* if removing a node with two children, replace it
*
* with its in order predecessor.
*
* @param the
* element of the node you want to remove.
*
*/
public void remove(E it) {
BSTNode<E> parent = null;
BSTNode<E> child = null;
BSTNode<E> node = root;
// Find the node that contains it
while (node != null && node.getElement() != it) {
parent = node;
int compareResult = it.compareTo(node.getElement());
if (compareResult < 0) {
node = node.getLeft();
} else {
node = node.getRight();
}
}
if (node == null) {
System.out.println("failed to find: " + it + " for removal");
return;
}
if (node.isLeaf()) {
if (parent == null) {
root = null;
} else if (it.compareTo(parent.getElement()) < 0) {
parent.setLeft(null);
} else {
parent.setRight(null);
}
} else if (node.getLeft() == null) {
child = node.getRight();
swapElements(node, child);
node.setLeft(child.getLeft());
node.setRight(child.getRight());
} else if (node.getRight() == null) {
child = node.getLeft();
} else {
child = node.getLeft();
parent = null;
while (child.getRight() != null) {
parent = child;
child = parent.getRight();
}
if (parent == null) {
swapElements(node, child);
node.setLeft(child.getLeft());
} else {
swapElements(node, child);
parent.setRight(child.getLeft());
}
}
size--;
}
/**
* Returns the height of the tree
*
* if tree is empty, height is -1
*
* if tree only has one node, height is 0
*
* @return the integer height of the tree
*
*
*
*/
public int getHeight() {
int height = -1;
QueueList<BSTNode> q = new QueueList<BSTNode>();
if (root == null) {
return height;
}
q.enqueue(root);
while (!q.isEmpty()) {
int nodeCount = q.size();
height++;
while (nodeCount > 0) {
BSTNode<E> node = q.dequeue();
if (node.hasLeft()) {
q.enqueue(node.getLeft());
}
if (node.hasRight()) {
q.enqueue(node.getRight());
}
nodeCount--;
}
}
return height;
}
/**
* Helper method
*
* For removal you need to swap elements of nodes
*
* @param node1
* , node2 the nodes whose contents you are swapping
*
*/
private void swapElements(BSTNode node1, BSTNode node2) {
BSTNode temp = null;
temp.setElement(node1.getElement());
node1.setElement(node2.getElement());
node2.setElement(temp.getElement());
}
/**
* prints each level of the tree on its own line
*
* use your Queue class
*
*/
public void printLevelOrder() {
QueueList<BSTNode> q = new QueueList<BSTNode>();
q.enqueue(root);//You don't need to write the root here, it will be written in the loop
while (q.size() > 0)
{
BSTNode n = q.dequeue();
System.out.println(n.toString()); //Only write the value when you dequeue it
if (n.hasLeft())
{
q.enqueue(n.getLeft());//enqueue the left child
}
if (n.hasRight())
{
q.enqueue(n.getRight());//enque the right child
}
}
}
/**
* prints the tree in a depth-first fashion
*
* use your Stack class
*
*/
public void printByDepth() {
StackList<BSTNode> s = new StackList<BSTNode>();
s.push(root);
while (s.isEmpty() == false) {
BSTNode x = s.pop();
if (x.getRight() != null)
s.push(x.getRight());
if (x.getLeft() != null)
s.push(x.getRight());
System.out.print(" " + x.toString());
}
}
/**
* prints the tree in an inorder fashion.
*
* uses a stack to push left children onto the stack
*
*/
public void printInOrder() {
if (root == null)
return;
StackList s = new StackList();
BSTNode currentNode = root;
while (!s.isEmpty() || currentNode != null) {
if (currentNode != null) {
s.push(currentNode);
currentNode = currentNode.getLeft();
} else {
BSTNode n = null;
n.setElement(s.pop());
System.out.printf("%d ", n.toString());
currentNode = n.getRight();
}
}
}
}