我们将把你的代码放在重症监护室。。。
In
节点
我们删除
钥匙
属性,以及实例化
left儿童
和
right孩子
因为它们是多余的。
class Node {
int data;
Node leftChild;
Node rightChild;
Node( int data ) {
this.data = data;
}
}
public Node insertNode( Node node, int data ) {
// we declare the new "Node"
Node aux;
if( node == null ) {
aux = new Node( data );
root = aux;
}
else if( data <= node.data ) {
// if the left node does not exist, we assign "aux" to it
if( node.leftChild == null ) {
// we create
aux = new Node( data );
node.leftChild = aux;
}
// if exist, we recursion, passing it as a parameter
else
insertNode( node.leftChild, data );
}
else if( data > node.data ) {
if( node.rightChild == null ) {
aux = new Node( data );
node.rightChild = aux;
}
else
insertNode( node.rightChild, data );
}
return aux;
}
// We move the "main" code here, so we avoid declaring static attributes and methods...
// and ugly ones :)
void init() {
int[] treeNodes = { 5, 2, 12, -4, 3, 9, 21, 19, 25 };
// we create the "root" node
Node root = new Node( treeNodes[ 0 ]);
// we create the others nodes
for( int i = 1; i < treeNodes.length; i ++ ) {
insertNode( root, treeNodes[ i ] );
}
System.out.println();
for( int value : treeNodes )
System.out.println( findHeir( root, value ));
int key = 12;
delete( root, key );
}
public static void main( String[] args ) {
new Main().init();
}
所有的代码在一起。。。
public class Main {
class Node {
int data;
Node leftChild;
Node rightChild;
Node( int data ) {
this.data = data;
}
}
Node root;
public Node insertNode( Node node, int data ) {
Node aux;
if( node == null ) {
aux = new Node( data );
root = aux;
}
else if( data <= node.data ) {
if( node.leftChild == null ) {
aux = new Node( data );
node.leftChild = aux;
}
else {
insertNode( node.leftChild, data );
}
}
else if( data > node.data ) {
if( node.rightChild == null ) {
aux = new Node( data );
node.rightChild = aux;
}
else {
insertNode( node.rightChild, data );
}
}
return aux;
}
//Method that returns 0 instead of 19
public int findHeir( Node node, int heir ) {
System.out.println( "Loop" );
if( node.rightChild != null && node.leftChild != null ) {
heir = node.leftChild.data;
System.out.print( "Current node: " + node.rightChild.data );
System.out.println( " Current heir: " + heir );
return findHeir( node.rightChild, heir );
}
else if( node.rightChild == null ) {
System.out.println( "Heir value before return: " + heir );
return heir;
}
return heir;
}
//Deletes the node
public Node delete( Node node, int data ) {
//Checks if the node exists
if( node == null ) {
System.out.println( "The node you entered does not exist." );
return node;
}
//Looks for the correct node
else if( data < node.data ) {
System.out.println( " es menor que " + node.data );
node.leftChild = delete( node.leftChild, data );
}
else if( data > node.data ) {
System.out.println( " es mayor que " + node.data );
//node.rightChild =
System.out.println( " derche = " + node.rightChild.data );
delete( node.rightChild, data );
}
//Found the correct node
else {
//Delete node if it has 2 children
if( node.leftChild != null && node.rightChild != null ) {
int heir = 0;
findHeir( node, heir );
System.out.println( "Final node value: " + node.data );
System.out.println( "Final heir value: " + heir + " (should be 19)" );
//TODO add code to switch heir and node.data and delete node
}
}
return node;
}
void init() {
int[] treeNodes = { 5, 2, 12, -4, 3, 9, 21, 19, 25 };
Node root = new Node( treeNodes[ 0 ] );
for( int i = 1; i < treeNodes.length; i ++ ) {
insertNode( root, treeNodes[ i ] );
}
System.out.println();
for( int value : treeNodes ) {
System.out.println( findHeir( root, value ) );
}
int key = 12;
delete( root, key );
}
public static void main( String[] args ) {
new Main().init();
}
}