我对树的问题有问题。 代码中没有错误; 这只是一个错误的输出。 问题是当我插入“ 100 ” 时, 它给出了错误的叶子和高度, 并且不按 Traversal 顺序是错的。 下面是二进制树类 :
public class BinaryTree {
//Definition of the node
protected class BinaryTreeNode {
Object info;
BinaryTreeNode llink;
BinaryTreeNode rlink;
}
protected BinaryTreeNode root;
//default constructor
//Postcondition: root = null;
public BinaryTree() {
root = null;
}
//copy constructor
public BinaryTree(BinaryTree otherTree) {
if (otherTree.root == null) //otherTree is empty
{
root = null;
} else {
root = copy(otherTree.root);
}
}
//Method to determine whether the binary tree is empty.
//Postcondition: Returns true if the binary tree is empty;
// otherwise, returns false.
public boolean isEmpty() {
return (root == null);
}
//Method to do an inorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are output
// in the inorder sequence.
public void inorderTraversal() {
inorder(root);
}
//Method to do a preorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are output
// in the preorder sequence.
public void preorderTraversal() {
preorder(root);
}
//Method to do a postorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are output
// in the postorder sequence.
public void postorderTraversal() {
postorder(root);
}
//Method to determine the height of the binary tree.
//Postcondition: The height of the binary tree is returned.
public int treeHeight() {
return height(root);
}
//Method to determine the number of nodes in the
//binary tree.
//Postcondition: The number of nodes in the binary tree
// is returned.
public int treeNodeCount() {
return nodeCount(root);
}
//Method to determine the number of nodes in the binary
//tree to which p points.
//Postcondition: The number of nodes in the binary tree
// to which p points is returned.
private int nodeCount(BinaryTreeNode p) {
if (p == null) {
return 0;
} else {
return (1 + nodeCount(p.llink) + nodeCount(p.rlink));
}
}
//Method to determine the number of leaves in the
//binary tree.
//Postcondition: The number of leaves in the binary tree
// is returned.
public int treeLeavesCount() {
return leavesCount(root);
}
//Method to determine the number of leaves in the binary
//tree to which p points.
//Postcondition: The number of leaves in the binary tree
// to which p points is returned.
private int leavesCount(BinaryTreeNode p) {
if (p == null) {
return 0;
}
if (p.llink == null && p.rlink == null) {
return 1;
}
return (leavesCount(p.rlink) + leavesCount(p.llink));
}
//Method to destroy the binary tree.
//Postcondition: root = null
public void destroyTree() {
root = null;
}
//Method to make a copy of the binary tree
//specified by otherTree points.
//Postcondition: A copy of otherTree is assigned to
// this binary tree.
public void copyTree(BinaryTree otherTree) {
if (this != otherTree) //avoid self-copy
{
root = null;
if (otherTree.root != null) //otherTree is nonempty
{
root = copy(otherTree.root);
}
}
}
//Method to make a copy of the binary tree to
//which otherTreeRoot points.
//Postcondition: A copy of the binary tree to which
// otherTreeRoot is created and the reference of
// the root node of the copied binary tree
// is returned.
private BinaryTreeNode copy(BinaryTreeNode otherTreeRoot) {
BinaryTreeNode temp;
if (otherTreeRoot == null) {
temp = null;
} else {
temp = new BinaryTreeNode();
temp.info = (((String) otherTreeRoot.info));
temp.llink = copy(otherTreeRoot.llink);
temp.rlink = copy(otherTreeRoot.rlink);
}
return temp;
}//end copy
//Method to do an inorder traversal of the binary
//tree to which p points.
//Postcondition: The nodes of the binary tree to which p
// points are output in the inorder sequence.
private void inorder(BinaryTreeNode p) {
if (p != null) {
inorder(p.llink);
System.out.print(p.info + " ");
inorder(p.rlink);
}
}
//Method to do a preorder traversal of the binary
//tree to which p points.
//Postcondition: The nodes of the binary tree to which p
// points are output in the preorder sequence.
private void preorder(BinaryTreeNode p) {
if (p != null) {
System.out.print(p.info + " ");
preorder(p.llink);
preorder(p.rlink);
}
}
//Method to do a postorder traversal of the binary
//tree to which p points.
//Postcondition: The nodes of the binary tree to which p
// points are output in the postorder sequence.
private void postorder(BinaryTreeNode p) {
if (p != null) {
postorder(p.llink);
postorder(p.rlink);
System.out.print(p.info + " ");
}
}
public void insert(String x) {
BinaryTreeNode c1, c2, nn;
nn = new BinaryTreeNode();
nn.info = x;
nn.llink = null;
nn.rlink = null;
if (isEmpty()) {
root = nn;
} else {
c2 = root;
c1=null;
while (c2 != null) {
c1 = c2;
if (c2.info.equals(x)) {
System.out.println("Error");
return;
} else {
if (((String) c2.info).compareTo(x) > 0) {
c2 = c2.llink;
} else {
c2 = c2.rlink;
}
}
}
if (((String) c1.info).compareTo(x) > 0) {
c1.llink = nn;
} else {
c1.rlink = nn;
}
}
}
public boolean search(String x) {
boolean found = false;
BinaryTreeNode c1;
BinaryTreeNode c2 = root;
while (c2 != null && !found) {
c1 = c2;
if (c2.info.equals(x)) {
found = true;
} else {
if (((String) c2.info).compareTo(x) > 0) {
c2 = c2.llink;
} else {
c2 = c2.rlink;
}
}
}
return found;
}
//Method to determine the height of the binary tree
//to which p points.
//Postcondition: The height of the binary tree to which p
// points is returned.
private int height(BinaryTreeNode p) {
if (p == null) {
return 0;
} else {
return 1 + max(height(p.llink), height(p.rlink));
}
}
//Method to determine the larger of x and y.
//Postcondition: The larger of x and y is returned.
private int max(int x, int y) {
if (x >= y) {
return x;
} else {
return y;
}
}
public void deleteNode(String deleteItem) {
BinaryTreeNode current; //reference variable to
//traverse the tree
BinaryTreeNode trailCurrent; //reference variable
//behind current
boolean found = false;
if (root == null) {
System.out.println("Cannot delete from the empty tree.");
} else {
current = root;
trailCurrent = root;
while (current != null && !found) {
if (current.info.equals(deleteItem)) {
found = true;
} else {
trailCurrent = current;
if (((String) current.info).compareTo(deleteItem) > 0) {
current = current.llink;
} else {
current = current.rlink;
}
}
}//end while
if (current == null) {
System.out.println("The delete item is not in "
+ "the list.");
} else if (found) {
if (current == root) {
root = deleteFromTree(root);
} else if (((String) trailCurrent.info).compareTo(deleteItem) > 0) {
trailCurrent.llink = deleteFromTree(trailCurrent.llink);
} else {
trailCurrent.rlink = deleteFromTree(trailCurrent.rlink);
}
}//end if
}
}//end deleteNode
//Method to delete the node, to which p points, from the
//binary search tree.
//Postcondition: The node to which p points is deleted
// from the binary search tree. The reference
// of the root node of the binary search tree
// after deletion is returned.
private BinaryTreeNode deleteFromTree(BinaryTreeNode p) {
BinaryTreeNode current; //reference variable to
//traverse the tree
BinaryTreeNode trailCurrent; //reference variable
//behind current
if (p == null) {
System.out.println("Error: The node to be deleted "
+ "is null.");
} else if (p.llink == null && p.rlink == null) {
p = null;
} else if (p.llink == null) {
p = p.rlink;
} else if (p.rlink == null) {
p = p.llink;
} else {
current = p.llink;
trailCurrent = null;
while (current.rlink != null) {
trailCurrent = current;
current = current.rlink;
}//end while
p.info = current.info;
if (trailCurrent == null) //current did not move;
//current == p.llink; adjust p
{
p.llink = current.llink;
} else {
trailCurrent.rlink = current.llink;
}
}//end else
return p;
}//end deleteFromTree
}
这里是主类 :
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Evil Weevil
*/
public class Run {
public static void main(String[] args) {
BinaryTree a=new BinaryTree();
a.insert("88");
a.insert("75");
a.insert("100");
a.insert("70");
a.insert("20");
a.insert("70");
a.insert("14");
System.out.println("InorderTraversal Tree:");
a.inorderTraversal();
System.out.print("
");
System.out.println("PreorderTraversal Tree:");
a.preorderTraversal();
System.out.print("
");
System.out.println("PostorderTraversal Tree:");
a.postorderTraversal();
System.out.print("
");
System.out.println(" Tree Node Count:");
System.out.println(a.treeNodeCount());
System.out.println(" Tree Leaves Count:");
System.out.println(a.treeLeavesCount());
System.out.println(" is the Tree Empty :");
System.out.println(a.isEmpty());
System.out.println(" Tree Height(longest chain of nodes ):");
System.out.println(a.treeHeight());
}
}