// BinaryNode class; stores a node in a tree. // // CONSTRUCTION: with (a) no parameters, or (b) an Object, // or (c) an Object, left child, and right child. // // *******************PUBLIC OPERATIONS********************** // int size( ) --> Return size of subtree at node // int height( ) --> Return height of subtree at node // void printPostOrder( ) --> Print a postorder tree traversal // void printInOrder( ) --> Print an inorder tree traversal // void printPreOrder( ) --> Print a preorder tree traversal // BinaryNode duplicate( )--> Return a duplicate tree/** * Binary node class with recursive routines to * compute size and height. */ final class BinaryNode { public BinaryNode( ) { this( null, null, null ); }public BinaryNode( Object theElement, BinaryNode lt, BinaryNode rt ) { element = theElement; left = lt; right = rt; }/** * Return the size of the binary tree rooted at t. */ public static int size( BinaryNode t ) { if( t == null ) return 0; else return 1 + size( t.left ) + size( t.right ); }/** * Return the height of the binary tree rooted at t. */ public static int height( BinaryNode t ) { if( t == null ) return -1; else return 1 + Math.max( height( t.left ), height( t.right ) ); }// Print tree rooted at current node using preorder traversal. public void printPreOrder( ) { System.out.println( element ); // Node if( left != null ) left.printPreOrder( ); // Left if( right != null ) right.printPreOrder( ); // Right } // Print tree rooted at current node using postorder traversal. public void printPostOrder( ) { if( left != null ) left.printPostOrder( ); // Left if( right != null ) right.printPostOrder( ); // Right System.out.println( element ); // Node }// Print tree rooted at current node using inorder traversal. public void printInOrder( ) { if( left != null ) left.printInOrder( ); // Left System.out.println( element ); // Node if( right != null ) right.printInOrder( ); // Right } /** * Return a reference to a node that is the root of a * duplicate of the binary tree rooted at the current node. */ public BinaryNode duplicate( ) { BinaryNode root = new BinaryNode( element, null, null );if( left != null ) // If there's a left subtree root.left = left.duplicate( ); // Duplicate; attach if( right != null ) // If there's a right subtree root.right = right.duplicate( ); // Duplicate; attach return root; // Return resulting tree }public Object getElement( ) { return element; }public BinaryNode getLeft( ) { return left; }public BinaryNode getRight( ) { return right; }public void setElement( Object x ) { element = x; }public void setLeft( BinaryNode t ) { left = t; }public void setRight( BinaryNode t ) { right = t; }private Object element; private BinaryNode left; private BinaryNode right; } // BinaryTree class; stores a binary tree. // // CONSTRUCTION: with (a) no parameters or (b) an object to // be placed in the root of a one-element tree. // // *******************PUBLIC OPERATIONS********************** // Various tree traversals, size, height, isEmpty, makeEmpty. // Also, the following tricky method: // void merge( Object root, BinaryTree t1, BinaryTree t2 ) // --> Construct a new tree // *******************ERRORS********************************* // Error message printed for illegal merges./** * BinaryTree class that illustrates the calling of * BinaryNode recursive routines and merge. */ public class BinaryTree { public BinaryTree( ) { root = null; }public BinaryTree( Object rootItem ) { root = new BinaryNode( rootItem, null, null ); }public void printPreOrder( ) { if( root != null ) root.printPreOrder( ); }public void printInOrder( ) { if( root != null ) root.printInOrder( ); }public void printPostOrder( ) { if( root != null ) root.printPostOrder( ); }public void makeEmpty( ) { root = null; }public boolean isEmpty( ) { return root == null; }/** * Merge routine for BinaryTree class. * Forms a new tree from rootItem, t1 and t2. * Does not allow t1 and t2 to be the same. * Correctly handles other aliasing conditions. */ public void merge( Object rootItem, BinaryTree t1, BinaryTree t2 ) { if( t1.root == t2.root && t1.root != null ) { System.err.println( "leftTree==rightTree; merge aborted" ); return; }// Allocate new node root = new BinaryNode( rootItem, t1.root, t2.root );// Ensure that every node is in one treeif( this != t1 ) t1.root = null; if( this != t2 ) t2.root = null;}public int size( ) { return BinaryNode.size( root ); }public int height( ) { return BinaryNode.height( root ); }public BinaryNode getRoot( ) { return root; }private BinaryNode root;static public void main( String [ ] args ) { BinaryTree t1 = new BinaryTree( "1" ); BinaryTree t3 = new BinaryTree( "3" ); BinaryTree t5 = new BinaryTree( "5" ); BinaryTree t7 = new BinaryTree( "7" ); BinaryTree t2 = new BinaryTree( ); BinaryTree t4 = new BinaryTree( ); BinaryTree t6 = new BinaryTree( );t2.merge( "2", t1, t3 ); t6.merge( "6", t5, t7 ); t4.merge( "4", t2, t6 );System.out.println( "t4 should be perfect 1-7; t2 empty" ); t6.printInOrder(); System.out.println( "----------------" ); System.out.println( "t4" ); t4.printInOrder( ); System.out.println( "----------------" ); System.out.println( "t2" ); System.out.println(t2); t2.printInOrder( ); System.out.println( "----------------" ); System.out.println( "t4 size: " + t4.size( ) ); System.out.println( "t4 height: " + t4.height( ) ); System.out.println( "----------------" ); } } 前几天我刚问过这个问题,是别人给我的代码。与你共享下~~~
//
// CONSTRUCTION: with (a) no parameters, or (b) an Object,
// or (c) an Object, left child, and right child.
//
// *******************PUBLIC OPERATIONS**********************
// int size( ) --> Return size of subtree at node
// int height( ) --> Return height of subtree at node
// void printPostOrder( ) --> Print a postorder tree traversal
// void printInOrder( ) --> Print an inorder tree traversal
// void printPreOrder( ) --> Print a preorder tree traversal
// BinaryNode duplicate( )--> Return a duplicate tree/**
* Binary node class with recursive routines to
* compute size and height.
*/
final class BinaryNode
{
public BinaryNode( )
{
this( null, null, null );
}public BinaryNode( Object theElement, BinaryNode lt, BinaryNode rt )
{
element = theElement;
left = lt;
right = rt;
}/**
* Return the size of the binary tree rooted at t.
*/
public static int size( BinaryNode t )
{
if( t == null )
return 0;
else
return 1 + size( t.left ) + size( t.right );
}/**
* Return the height of the binary tree rooted at t.
*/
public static int height( BinaryNode t )
{
if( t == null )
return -1;
else
return 1 + Math.max( height( t.left ), height( t.right ) );
}// Print tree rooted at current node using preorder traversal.
public void printPreOrder( )
{
System.out.println( element ); // Node
if( left != null )
left.printPreOrder( ); // Left
if( right != null )
right.printPreOrder( ); // Right
}
// Print tree rooted at current node using postorder traversal.
public void printPostOrder( )
{
if( left != null )
left.printPostOrder( ); // Left
if( right != null )
right.printPostOrder( ); // Right
System.out.println( element ); // Node
}// Print tree rooted at current node using inorder traversal.
public void printInOrder( )
{
if( left != null )
left.printInOrder( ); // Left
System.out.println( element ); // Node
if( right != null )
right.printInOrder( ); // Right
}
/**
* Return a reference to a node that is the root of a
* duplicate of the binary tree rooted at the current node.
*/
public BinaryNode duplicate( )
{
BinaryNode root = new BinaryNode( element, null, null );if( left != null ) // If there's a left subtree
root.left = left.duplicate( ); // Duplicate; attach
if( right != null ) // If there's a right subtree
root.right = right.duplicate( ); // Duplicate; attach
return root; // Return resulting tree
}public Object getElement( )
{
return element;
}public BinaryNode getLeft( )
{
return left;
}public BinaryNode getRight( )
{
return right;
}public void setElement( Object x )
{
element = x;
}public void setLeft( BinaryNode t )
{
left = t;
}public void setRight( BinaryNode t )
{
right = t;
}private Object element;
private BinaryNode left;
private BinaryNode right;
}
// BinaryTree class; stores a binary tree.
//
// CONSTRUCTION: with (a) no parameters or (b) an object to
// be placed in the root of a one-element tree.
//
// *******************PUBLIC OPERATIONS**********************
// Various tree traversals, size, height, isEmpty, makeEmpty.
// Also, the following tricky method:
// void merge( Object root, BinaryTree t1, BinaryTree t2 )
// --> Construct a new tree
// *******************ERRORS*********************************
// Error message printed for illegal merges./**
* BinaryTree class that illustrates the calling of
* BinaryNode recursive routines and merge.
*/
public class BinaryTree
{
public BinaryTree( )
{
root = null;
}public BinaryTree( Object rootItem )
{
root = new BinaryNode( rootItem, null, null );
}public void printPreOrder( )
{
if( root != null )
root.printPreOrder( );
}public void printInOrder( )
{
if( root != null )
root.printInOrder( );
}public void printPostOrder( )
{
if( root != null )
root.printPostOrder( );
}public void makeEmpty( )
{
root = null;
}public boolean isEmpty( )
{
return root == null;
}/**
* Merge routine for BinaryTree class.
* Forms a new tree from rootItem, t1 and t2.
* Does not allow t1 and t2 to be the same.
* Correctly handles other aliasing conditions.
*/
public void merge( Object rootItem, BinaryTree t1, BinaryTree t2 )
{
if( t1.root == t2.root && t1.root != null )
{
System.err.println( "leftTree==rightTree; merge aborted" );
return;
}// Allocate new node
root = new BinaryNode( rootItem, t1.root, t2.root );// Ensure that every node is in one treeif( this != t1 )
t1.root = null;
if( this != t2 )
t2.root = null;}public int size( )
{
return BinaryNode.size( root );
}public int height( )
{
return BinaryNode.height( root );
}public BinaryNode getRoot( )
{
return root;
}private BinaryNode root;static public void main( String [ ] args )
{
BinaryTree t1 = new BinaryTree( "1" );
BinaryTree t3 = new BinaryTree( "3" );
BinaryTree t5 = new BinaryTree( "5" );
BinaryTree t7 = new BinaryTree( "7" );
BinaryTree t2 = new BinaryTree( );
BinaryTree t4 = new BinaryTree( );
BinaryTree t6 = new BinaryTree( );t2.merge( "2", t1, t3 );
t6.merge( "6", t5, t7 );
t4.merge( "4", t2, t6 );System.out.println( "t4 should be perfect 1-7; t2 empty" );
t6.printInOrder();
System.out.println( "----------------" );
System.out.println( "t4" );
t4.printInOrder( );
System.out.println( "----------------" );
System.out.println( "t2" );
System.out.println(t2);
t2.printInOrder( );
System.out.println( "----------------" );
System.out.println( "t4 size: " + t4.size( ) );
System.out.println( "t4 height: " + t4.height( ) );
System.out.println( "----------------" );
}
}
前几天我刚问过这个问题,是别人给我的代码。与你共享下~~~