没心情写程序,简单跟你说一点东西吧。树型结构的实现——这个实在不想讲了,去看看《数据结构》吧。
但是为了配置第2点的要求,你可以在结点的数据上多设计一些东西,比如用一个level字段保存当前节点所在的层,并在增加节点和跨层移动节点的时候改变level值。
至于每层节点几位编号,可以保存在一个array中,实际赋编号值的时候查array来检验。
但是为了配置第2点的要求,你可以在结点的数据上多设计一些东西,比如用一个level字段保存当前节点所在的层,并在增加节点和跨层移动节点的时候改变level值。
至于每层节点几位编号,可以保存在一个array中,实际赋编号值的时候查array来检验。
public class BinaryTree
{ //Definition of the node
protected class BinaryTreeNode
{
DataElement 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 leaves in the
//binary tree.
//Postcondition: The number of leaves in the binary tree
// is returned.
public int treeLeavesCount()
{
return leavesCount(root);
} //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 = otherTreeRoot.info.getCopy();
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 + " ");
}
} //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;
} //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)
{
System.out.println("See Programming Exercise 1.");
return 0;
}
//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)
{
System.out.println("See Programming Exercise 2.");
return 0;
}
}
public abstract class DataElement
{
public abstract boolean equals(DataElement otherElement);
//Method to determine whether two objects contain the
//same data.
//Postcondition: Returns true if this object contains the
// same data as the object otherElement;
// otherwise, it returns false.
public abstract int compareTo(DataElement otherElement);
//Method to compare two objects.
//Postcondition: Returns a value < 0 if this object is
// less than the object otherElement;
// Returns 0 if this object is the same as
// the object otherElement.
// Returns a value > 0 if this object is
// greater than the object otherElement.
public abstract void makeCopy(DataElement otherElement);
//Method to copy otherElement into this object.
//Postcondition: The data of otherElement is copied into
// this object.
public abstract DataElement getCopy();
//Method to return a copy of this object.
//Postcondition: A copy of this object is created and
// a reference of the copy is returned.
}
{
protected int num; //default constructor
public IntElement()
{
num = 0;
} //constructor with parameters
public IntElement(int x)
{
num = x;
} //copy constructor
public IntElement(IntElement otherElement)
{
num = otherElement.num;
} //Method to set the value of the instance variable num
//Postcondition: num = x;
public void setNum(int x)
{
num = x;
} //Method to return the value of the instance variable num
//Postcondition: The value of num is returned
public int getNum()
{
return num;
}
public boolean equals(DataElement otherElement)
{
IntElement temp = (IntElement) otherElement; return (num == temp.num);
} public int compareTo(DataElement otherElement)
{
IntElement temp = (IntElement) otherElement; return (num - temp.num);
} public void makeCopy(DataElement otherElement)
{
IntElement temp = (IntElement) otherElement; num = temp.num;
} public DataElement getCopy()
{
IntElement temp = new IntElement(num);
return temp;
} public String toString()
{
return String.valueOf(num);
}
}