问题：
我们如何对二叉搜索树进行操作
司徒兴德
--更新二--
public void balanceBST(TreeNode <E> node) {
if (node == null)
System.out.println("There is no tree to balance");
java.util.ArrayList<E> bstToArray = new java.util.ArrayList<E>();
Iterator<E> treeToArray = iterator();
while(treeToArray.hasNext()){
bstToArray.add(treeToArray.next());
}
int low = 0;
int high = bstToArray.size();
clear();
balanceHelper(bstToArray, low, high);
}
/** Helper method for the balanceBST method*/
public void balanceHelper(java.util.ArrayList<E> b, int low, int high) {
if(low == high)
return;
int midpoint = (low+high)/2;
insert(b.get(midpoint));
balanceHelper(b, midpoint+1, high);
balanceHelper(b, low, midpoint);
}
/** Balance BST */
public void balanceBST(TreeNode <E> node) {
if (node == null)
System.out.println("There is no tree to balance");
java.util.ArrayList<E> bstToArray = new java.util.ArrayList<E>();
Iterator<E> treeToArray = iterator();
while(treeToArray.hasNext()){
bstToArray.add(treeToArray.next());
}
//System.out.println(bstToArray);
int low = 0;
int high = bstToArray.size();
balanceHelper(bstToArray, low, high);
//System.out.println(bstToArray);
}
public void balanceHelper(java.util.ArrayList<E> b, int low, int high) {
if(low == high)
return;
int midpoint = (low+high)/2;
insert(b.get(midpoint));
balanceHelper(b, midpoint+1, high);
balanceHelper(b, low, midpoint);
}
所以我写了这些方法，但我对不同的对象以及如何在驱动程序/测试程序中调用这些方法有点迷惑。以下是我的问题（请原谅，因为它们对一些人来说可能很琐碎）：-
（1）为什么我们传递一个节点而不是树给这些方法？
（2）当我在驱动程序中创建树并试图调用treeHeight方法时，我得到一条错误消息，它告诉我传递了错误的参数（tree而不是node）.....我知道这个错误，并理解为什么会有这个错误，但我有点困惑，因为我在网上看到的大多数示例都将节点传递给treeHeight方法，通过在BST中插入元素，我们确实有节点，但我们如何调用这样的方法？这是我对OOP缺乏理解。
下面是我测试程序代码的一个片段：
BST<Integer> b1 = new BST<Integer>();
b1.insert(1);
b1.insert(2);
b1.insert(3);
b1.insert(4);
// How do I call the treeHeight on BST?
// I tried b1.treeHeight() but....
// and I tried treeHeight(BST) but....
// am a bit lost
这是BST类和我的方法（请注意，有些方法可能不正确，我仍在研究它们...我确信一旦我把基本原理弄清楚，我会把它们弄明白的）：
import java.lang.Math;
public class BST<E extends Comparable<E>> {
protected TreeNode<E> root;
protected int size = 0;
/** Create a default binary tree */
public BST() {
}
/** Create a binary tree from an array of objects */
public BST(E[] objects) {
for (int i = 0; i < objects.length; i++)
insert(objects[i]);
}
/** Returns true if the element is in the tree */
public boolean search(E e) {
TreeNode<E> current = root; // Start from the root
while (current != null) {
if (e.compareTo(current.element) < 0) {
current = current.left;
} else if (e.compareTo(current.element) > 0) {
current = current.right;
} else
// element matches current.element
return true; // Element is found
}
return false;
}
/**
* Insert element o into the binary tree Return true if the element is
* inserted successfully
*/
public boolean insert(E e) {
if (root == null)
root = createNewNode(e); // Create a new root
else {
// Locate the parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null)
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else
return false; // Duplicate node not inserted
// Create the new node and attach it to the parent node
if (e.compareTo(parent.element) < 0)
parent.left = createNewNode(e);
else
parent.right = createNewNode(e);
}
size++;
return true; // Element inserted
}
protected TreeNode<E> createNewNode(E e) {
return new TreeNode<E>(e);
}
/** Inorder traversal from the root */
public void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
protected void inorder(TreeNode<E> root) {
if (root == null)
return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}
/** Postorder traversal from the root */
public void postorder() {
postorder(root);
}
/** Postorder traversal from a subtree */
protected void postorder(TreeNode<E> root) {
if (root == null)
return;
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}
/** Preorder traversal from the root */
public void preorder() {
preorder(root);
}
/** Preorder traversal from a subtree */
protected void preorder(TreeNode<E> root) {
if (root == null)
return;
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);
}
/**
* This inner class is static, because it does not access any instance
* members defined in its outer class
*/
public static class TreeNode<E extends Comparable<E>> {
protected E element;
protected TreeNode<E> left;
protected TreeNode<E> right;
public TreeNode(E e) {
element = e;
}
}
/** Get the number of nodes in the tree */
public int getSize() {
return size;
}
/** Returns the root of the tree */
public TreeNode<E> getRoot() {
return root;
}
/** Return tree height - my own method */
public int treeHeight(TreeNode <E> node) {
// height of empty tree = ZERO
if (node == null)
return 0;
int leftHeight = treeHeight(node.left);
int rightHeight = treeHeight(node.right);
if (leftHeight > rightHeight)
return leftHeight;
else
return rightHeight;
}
/** Return the no of nodes at given level - my own method */
public int numberOfNodesAtLevel(TreeNode <E> node, int level) {
if (root == null)
return 0;
if (level == 0)
return 1;
return numberOfNodesAtLevel(node.left, level-1) + numberOfNodesAtLevel(node.right, level-1);
}
/** Return the no of nodes in binary tree - my own method */
public int numberOfNodes(TreeNode <E> node) {
if (node == null)
return 0;
return 1 + numberOfNodes(node.left) + numberOfNodes(node.right);
}
/** Calculate ACE - my own method */
public double calculateACE(TreeNode <E> node) {
int n = numberOfNodes(node);
int treeHeight = treeHeight(node);
int sum = 0;
int level = 0;
for (level=0, sum=0; level < treeHeight; level++ ) {
sum += numberOfNodesAtLevel(node, level) * (level + 1);
}
double ACE = sum / n;
return ACE;
}
/** Calculate MinACE - my own method */
public double calculateMinACE(TreeNode <E> node) {
int n = numberOfNodes(node);
int treeHeight = (int) Math.floor((Math.log(n))+1);
int sum = 0;
int level = 0;
for (level=0, sum=0; level < treeHeight; level++ ) {
sum += numberOfNodesAtLevel(node, level) * (level + 1);
}
double ACE = sum / n;
return ACE;
}
/** Calculate MaxACE - my own method */
public double calculateMaxACE(TreeNode <E> node) {
int n = numberOfNodes(node);
int treeHeight = n;
int sum = 0;
int level = 0;
for (level=0, sum=0; level < treeHeight; level++ ) {
sum += numberOfNodesAtLevel(node, level) * (level + 1);
}
double ACE = sum / n;
return ACE;
}
/** Needs Balancing - my own method */
public boolean needsBalancing(TreeNode <E> node) {
double k = 1.25;
double AceValue = calculateACE(node);
double MinAceValue = calculateMinACE(node);
if(AceValue > (MinAceValue*k))
return true;
return false;
}
/** Balance BST - my own method, not complete yet */
public void balanceBST(TreeNode <E> node) {
int size = numberOfNodes(node);
}
/** Returns a path from the root leading to the specified element */
public java.util.ArrayList<TreeNode<E>> path(E e) {
java.util.ArrayList<TreeNode<E>> list = new java.util.ArrayList<TreeNode<E>>();
TreeNode<E> current = root; // Start from the root
while (current != null) {
list.add(current); // Add the node to the list
if (e.compareTo(current.element) < 0) {
current = current.left;
} else if (e.compareTo(current.element) > 0) {
current = current.right;
} else
break;
}
return list; // Return an array of nodes
}
/**
* Delete an element from the binary tree. Return true if the element is
* deleted successfully Return false if the element is not in the tree
*/
public boolean delete(E e) {
// Locate the node to be deleted and also locate its parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null) {
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else
break; // Element is in the tree pointed at by current
}
if (current == null)
return false; // Element is not in the tree
// Case 1: current has no left children
if (current.left == null) {
// Connect the parent with the right child of the current node
if (parent == null) {
root = current.right;
} else {
if (e.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
}
} else {
// Case 2: The current node has a left child
// Locate the rightmost node in the left subtree of
// the current node and also its parent
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // Keep going to the right
}
// Replace the element in current by the element in rightMost
current.element = rightMost.element;
// Eliminate rightmost node
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
// Special case: parentOfRightMost == current
parentOfRightMost.left = rightMost.left;
}
size--;
return true; // Element inserted
}
/** Obtain an iterator. Use inorder. */
public java.util.Iterator<E> iterator() {
return new InorderIterator();
}
// Inner class InorderIterator
private class InorderIterator implements java.util.Iterator<E> {
// Store the elements in a list
private java.util.ArrayList<E> list = new java.util.ArrayList<E>();
private int current = 0; // Point to the current element in list
public InorderIterator() {
inorder(); // Traverse binary tree and store elements in list
}
/** Inorder traversal from the root */
private void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
private void inorder(TreeNode<E> root) {
if (root == null)
return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
/** More elements for traversing? */
public boolean hasNext() {
if (current < list.size())
return true;
return false;
}
/** Get the current element and move to the next */
public E next() {
return list.get(current++);
}
/** Remove the current element */
public void remove() {
delete(list.get(current)); // Delete the current element
list.clear(); // Clear the list
inorder(); // Rebuild the list
}
}
/** Remove all elements from the tree */
public void clear() {
root = null;
size = 0;
}
}
共有1个答案
耿招
（1）为什么我们传递一个节点而不是树给这些方法？
回答:
一个BST是由它的根定义的，您可以实现接受根或树的方法--这是一个任意的决定。
（2）...我在网上看到过将一个节点传递给treeHeight方法，并通过在BST中插入元素，我们确实有节点，但如何调用这样的方法呢？这是我对OOP缺乏理解。
BST<Integer> b1 = new BST<Integer>();
b1.insert(1);
b1.insert(2);
b1.insert(3);
b1.insert(4);
int h = b1.treeHeight(b1.getRoot()); // get the height
int arraySize = b1.getSize();
Integer[] treeToArray = new Integer[arraySize];
iterator iter = b1.iterator();
int i=0;
while(iter.hasNext()) {
treeToArray[i++] = (Integer)iter.next();
}
（4）为什么treeHeight（）不起作用（总是返回零）？
回答:
因为它有一个bug，下面是修复它的方法：
/** Return tree height - my own method */
public int treeHeight(TreeNode <E> node) {
// height of empty tree = ZERO
if (node == null)
return 0;
int leftHeight = treeHeight(node.left);
int rightHeight = treeHeight(node.right);
if (leftHeight > rightHeight)
return leftHeight+1; // bug was here: you should return the height of the child + 1 (yourself)
else
return rightHeight+1; // and here
}
类似资料：
-
我需要创建一个递归方法，它将二进制搜索树的根节点作为参数。这个递归方法随后将返回整个二叉搜索树中节点总数的int值。 这是我目前所掌握的： main方法调用节点如下所示： 所以我是按顺序运行搜索的，一旦我到达一个没有子节点的节点，我就会删除当前节点，返回父节点并继续。我对上面的方法进行了调试，当程序最终计数并删除根节点左右两侧的所有节点并尝试返回1时，程序以NullPointerException
-
我很难按我教授想要的格式打印出一个二叉搜索树。 他的格式是这样的： 我的代码：
-
树的特征和定义 树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树： 树有多个节点(node)，用以储存元素。某些节点之间存在一定的关系，用连线表示，连线称为边(edge)。边的上端节点称为父节点，下端称为子节点。树像是一个不断分叉的树根。 每个节点可以有多个子节点(children)，而该节点是相应子节点的父节点(parent)。比如说，3,5是6的子节点，6是3,
-
编写一个函数，如果给定的二叉搜索树包含给定的值，则返回1，否则返回0。 例如,对于以下树： N1（值：1,左：null,右：null) n2（值：2,左:n1,右:n3) N3（值：3,左：null,右：null) 对contains(&n2,3）的调用应返回1，因为根位于n2的树包含编号3。 函数应该返回1，然而，它返回0或者根本不返回。
-
在二元搜索树的情况下，为什么我们不能简单地在一个节点有两个子节点的情况下，将一个节点的前一个节点替换为后一个节点？
-
我必须编写一个二进制搜索树的实现，它可以处理库的库存。它读取一个包含所有书籍的文本文件，并将这些书籍按字母顺序添加到树中。我已经与Insertar（）函数代码斗争了几天，但我无法使它正常工作，它基本上接收到一个指针，指向与书相关的所有数据的树根。如果根为NULL，则它将函数中输入的所有值初始化一个节点，并将内存方向指定为NULL节点。问题是，它在本地做，最终它没有分配它。谁能帮我纠正那个具体的功能