代码之家  ›  专栏  ›  技术社区  ›  user29759326

如何返回递归函数中的最后一个值?

  •  1
  • user29759326  · 技术社区  · 2 月前

    我是一名初学者,目前正在学习Java中的BST。对于这个项目,我试图删除一个有2个子节点的节点,但我很难让递归方法返回正确的值。该方法应该在与节点12相关的最右侧子树(后继树)中找到最左侧的值。它确实找到了正确的值(19),但返回了初始值(0)。

    //Method that returns 0 instead of 19
        public static 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;
        }
    

    我需要findHeir返回19,这样在delete方法中,我就可以用heir(19)切换节点的值(12),并删除重复的节点。为什么它总是返回初始值?我该怎么做才能使它返回最后一个值?

    完整可复制代码:

    import java.util.Scanner;
    
    public class Main {
        
        static class Node {
            int data;
            int key;
            Node leftChild;
            Node rightChild;
            
            Node (int data) {
                this.data = data;
                leftChild = rightChild = null;
            }
        }
        
        static Node root;
        
        public Main() {
            root = null;
        }
        
        //Inserts the node in the right spot
        public static void insert(int key) {
            root = insertNode(root, key);
        }
        
        public static Node insertNode(Node node, int key) {
            if (node == null) {
                node = new Node(key);
                return node;
            }
            
            else if (key <= node.data) {
                node.leftChild = insertNode(node.leftChild, key);
            }
            
            else if (key > node.data) {
                node.rightChild = insertNode(node.rightChild, key);
            }
            return node;
        }
        
        //Method that returns 0 instead of 19
        public static 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 static Node delete(Node node, int key) {
            //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 (key < node.data) {
                node.leftChild = delete(node.leftChild, key);
            }
            
            else if (key > node.data) {
                node.rightChild = delete(node.rightChild, key);
            }
            
            //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;
        }
        
        public static void main(String [] args) {
            int[] treeNodes = {5, 2, 12, -4, 3, 9, 21, 19, 25};
            Main binaryTree = new Main();
                    
            for (int i = 0; i < treeNodes.length; i++) {
                binaryTree.insert(treeNodes[i]);
                System.out.print(treeNodes[i] + " ");
            }
            System.out.println();
            
            int key = 12;
                    
            delete(root, key);
        }
    }
    

    这棵树看起来像这样:

           5
         /   \
       2       12
      / \     /  \
    -4   3   9    21
                 /  \
                19  25
    
    1 回复  |  直到 2 月前
        1
  •  0
  •   Janani Kannan    2 月前

    您没有更新的值 heir 变量,用于存储函数调用的返回值 findHeir(node, heir) 。您需要一个简单的调整:

    if (node.leftChild != null && node.rightChild != null) {
                    int heir = 0;
                    heir = 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
                }
        2
  •  0
  •   Marce Puente    2 月前

    我们将把你的代码放在重症监护室。。。

    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();
       }
    }