java - 我在创建扫描整个二叉树的方法时遇到问题，你能帮我吗？（仍然需要帮助）

Question

import java.io.*;
import java.util.*;              

import javax.swing.JOptionPane;
////////////////////////////////////////////////////////////////
class Node
   {
   public char iData;              // data item (key)
   public Node leftChild;         // this node's left child
   public Node rightChild;        // this node's right child


   public void displayNode()      // display ourself
      {
      System.out.print('{');
      System.out.print(iData);
      System.out.print("} ");
      }
   }  // end class Node
////////////////////////////////////////////////////////////////
class Tree
   {
   private Node root;             // first node of tree

// -------------------------------------------------------------
   public Tree()                  // constructor
      { root = null; }            // no nodes in tree yet
// -------------------------------------------------------------
   public Node find(char key)      // find node with given key
      {                           // (assumes non-empty tree)
      Node current = root;               // start at root
      while(current.iData != key)        // while no match,
         {
         if(key < current.iData)         // go left?
            current = current.leftChild;
         else                            // or go right?
            current = current.rightChild;
         if(current == null)             // if no child,
            return null;                 // didn't find it
         }
      return current;                    // found it
      }  // end find()
// -------------------------------------------------------------
   // If (current.leftChild != '+' && current.rightChild != '+')
   //  if ( current.leftChild != '+')                         if(current.rightChild != '+')
   // 
   //       



   public void insert(char id)
      {
      Node newNode = new Node();
      Node plusNode = new Node();
      // make new node
      newNode.iData = id;
      plusNode.iData = '+';         // insert data
      if(root==null)                // no node in root
         root = newNode;
      else                          // root occupied
         {
         Node current = root;       // start at root
         Node parent;
         while(true)                // (exits internally)
            {
            parent = current;
            if(id < current.iData)  // go left?
               {
               current = current.leftChild;               
               if(current == null)  // if end of the line,
                  {                 // insert on left
                  parent.leftChild = newNode;
                  if(parent != root);
                  {parent.rightChild= plusNode;}
                  return;
                  }
               }  // end if go left
            else                    // or go right?
               {
               current = current.rightChild;
               if(current == null)  // if end of the line
                  {                 // insert on right
                  parent.rightChild = newNode;
                  if(parent != root);
                  {parent.leftChild = plusNode;}
                  return;
                  }
               }  // end else go right
            }  // end while
         }  // end else not root
      }  // end insert()
// -------------------------------------------------------------
   public boolean delete(char key) // delete node with given key
      {                           // (assumes non-empty list)
      Node current = root;
      Node parent = root;
      boolean isLeftChild = true;

      while(current.iData != key)        // search for node
         {
         parent = current;
         if(key < current.iData)         // go left?
            {
            isLeftChild = true;
            current = current.leftChild;
            }
         else                            // or go right?
            {
            isLeftChild = false;
            current = current.rightChild;
            }
         if(current == null)             // end of the line,
            return false;                // didn't find it
         }  // end while
      // found node to delete

      // if no children, simply delete it
      if(current.leftChild==null&& current.rightChild==null)
      {
          if(current == root)
              root = null;
          else if(isLeftChild)
              parent.leftChild = null;
          else 
              parent.rightChild = null;
      }



      // if no right child, replace with left subtree
      //put your code here

      else if(current.rightChild==null)
          if(current == root)
              root = current.leftChild;
          else if (isLeftChild)
              parent.leftChild = current.leftChild;
          else
              parent.rightChild = current.leftChild;


      // if no left child, replace with right subtree
      //put your code here

      else if(current.leftChild==null)
          if(current == root)
              root = current.rightChild;
          else if(isLeftChild)
          parent.leftChild=current.rightChild;
          else
              parent.rightChild = current.rightChild;


      else  // two children, so replace with in order successor
         //put your code here
      {
          Node successor = getSuccessor(current);

          // if connect parent of current to successor instead
          if(current == root)
              root = successor;
          else if (isLeftChild)
              parent.leftChild = successor;
          else
              parent.rightChild = successor;
          // connect successor to current's left child
          successor.leftChild = current.leftChild;
      }



      // (successor cannot have a left child)
      return true;                                // success
      }  // end delete()
// -------------------------------------------------------------
   // returns node with next-highest value after delNode
   // goes to right child, then right child's left descendants
   private Node getSuccessor(Node delNode)
      {
      Node successorParent = delNode;
      Node successor = delNode;
      Node current = delNode.rightChild;   // go to right child
      while(current != null)               // until no more
         {                                 // left children,
         successorParent = successor;
         successor = current;
         current = current.leftChild;      // go to left child
         }
                                           // if successor not
      if(successor != delNode.rightChild)  // right child,
         {                                 // make connections
         successorParent.leftChild = successor.rightChild;
         successor.rightChild = delNode.rightChild;
         }
      return successor;
      }
// -------------------------------------------------------------
   public void traverse(int traverseType)
      {
      switch(traverseType)
         {
         case 1: System.out.print("\nPreorder traversal: ");
                 preOrder(root);
                 break;
         case 2: System.out.print("\nInorder traversal:  ");
                 inOrder(root);
                 break;
         case 3: System.out.print("\nPostorder traversal: ");
                 postOrder(root);
                 break;
         }
      System.out.println();
      }
// -------------------------------------------------------------
   private void preOrder(Node localRoot)
      {
      if(localRoot != null)
         {
         System.out.print(localRoot.iData + " ");
         preOrder(localRoot.leftChild);
         preOrder(localRoot.rightChild);
         }
      }
// -------------------------------------------------------------
   private void inOrder(Node localRoot)
      {
      if(localRoot != null)
         {
         inOrder(localRoot.leftChild);
         System.out.print(localRoot.iData + " ");
         inOrder(localRoot.rightChild);
         }
      }
// -------------------------------------------------------------
   private void postOrder(Node localRoot)
      {
      if(localRoot != null)
         {
         postOrder(localRoot.leftChild);
         postOrder(localRoot.rightChild);
         System.out.print(localRoot.iData + " ");
         }
      }
// -------------------------------------------------------------
   public void displayTree()
      {
      Stack globalStack = new Stack();
      globalStack.push(root);
      int nBlanks = 32;
      boolean isRowEmpty = false;
      System.out.println(
      "......................................................");
      while(isRowEmpty==false)
         {
         Stack localStack = new Stack();
         isRowEmpty = true;

         for(int j=0; j<nBlanks; j++)
            System.out.print(' ');

         while(globalStack.isEmpty()==false)
            {
            Node temp = (Node)globalStack.pop();
            if(temp != null)
               {
               System.out.print(temp.iData);
               localStack.push(temp.leftChild);
               localStack.push(temp.rightChild);

               if(temp.leftChild != null ||
                                   temp.rightChild != null)
                  isRowEmpty = false;
               }
            else
               {
               System.out.print("--");
               localStack.push(null);
               localStack.push(null);
               }
            for(int j=0; j<nBlanks*2-2; j++)
               System.out.print(' ');
            }  // end while globalStack not empty
         System.out.println();
         nBlanks /= 2;
         while(localStack.isEmpty()==false)
            globalStack.push( localStack.pop() );
         }  // end while isRowEmpty is false
      System.out.println(
      "......................................................");
      }  // end displayTree()


  /*  public void Play()
   {
      Scanner keyboard = new Scanner(System.in);
      int cont = 1;

      while (cont ==1)
      {
      Node newNode = new Node();
      System.out.println("Please enter a char ");
      char input = keyboard.next().charAt(0);
      newNode.iData = input;

     int response = JOptionPane.showConfirmDialog(null, "Do you want to enter another? ");

      if (response == JOptionPane.YES_OPTION)  
      {

      }

      else if (response == JOptionPane.NO_OPTION)
      {
          cont = 0;
      }


      }

   }*/


   public void fixRoot()
   {

       Node current = root;

       if(current.iData != '+')
       {
           insert(current.iData);
       }
       current.iData = '+';



   }

   public void fixTree()
   // Look at root of the binary tree
   // If the root is a char besides '+', insert it in the tree again
   // use same logic in order to rewrite the whole tree with transverse
   {   Node current = root;


      if (current.leftChild.iData != '+' && current.rightChild.iData != '+')      
      {
        if ( current.leftChild.iData != '+')
        {
            if(current.iData != '+')
           {
               insert(current.iData);
           }
           current.iData = '+';
        }
          if(current.rightChild.iData != '+')
          {
              if(current.iData != '+')
           {
               insert(current.iData);
           }
           current.iData = '+';
          }
      }


}
   public void transverseFix()
   {
       fixTree(root);
   }

  public void fixTree(Node current)
  //Transverse through the tree, node by node
  //At each location, check if leftChild or rightChild does not = '+'

   {
     if (current == null) return;

     fixTree(current.leftChild);

     if(current.iData != '+')
     {
           insert(current.iData);
           current.iData = '+';
     }
     if (current.rightChild != null)
    //{
   //    System.out.println(current.rightChild.iData);
   //    displayTree();
    // }
  //  fixTree(current.rightChild); 





   }

// -------------------------------------------------------------
   }  // end class Tree
////////////////////////////////////////////////////////////////
class TreeApp
   {
   public static void main(String[] args) throws IOException
      {
      char value;
      Tree theTree = new Tree();
      int cont = 1;

      Scanner keyboard = new Scanner(System.in);          
      do
      {
      System.out.println("Please enter a char ");
      char input = keyboard.next().charAt(0);
      theTree.insert(input);     
      System.out.println("Enter more?");
      String input2 = keyboard.next();
      if (input2.equalsIgnoreCase("n"))
      {
          cont = 2;
      }
        }while(cont == 1);

      theTree.displayTree();
      System.out.println("");
      theTree.fixRoot();
      theTree.displayTree();
      System.out.println("");
     // theTree.transverseFix();
      theTree.displayTree();








       //Testing without question
       // theTree.insert('a');
       // theTree.insert('z');
       //  theTree.insert('c');
       //   theTree.fixRoot();
       //  theTree.transverseFix();






      /*while(true)
         {
         System.out.print("Enter first letter of show, ");
         System.out.print("insert, find, delete, or traverse: ");
         int choice = getChar();
         switch(choice)
            {
            case 's':
               theTree.displayTree();
               break;
            case 'i':
               System.out.print("Enter value to insert: ");
               value = getChar();
               theTree.insert(value);
               break;
            case 'f':
               System.out.print("Enter value to find: ");
               value = getChar();
               Node found = theTree.find(value);
               if(found != null)
                  {
                  System.out.print("Found: ");
                  found.displayNode();
                  System.out.print("\n");
                  }
               else
                  System.out.print("Could not find ");
                  System.out.print(value + '\n');
               break;
            case 'd':
               System.out.print("Enter value to delete: ");
               value = getChar();
               boolean didDelete = theTree.delete(value);
               if(didDelete)
                  System.out.print("Deleted " + value + '\n');
               else
                  System.out.print("Could not delete ");
                  System.out.print(value + '\n');
               break;
            case 't':
               System.out.print("Enter type 1, 2 or 3: ");
               value = getChar();
               theTree.traverse(value);
               break;
            default:
               System.out.print("Invalid entry\n");
            }  // end switch
         }  // end while*/
      }  // end main()
// -------------------------------------------------------------
   public static String getString() throws IOException
      {
      InputStreamReader isr = new InputStreamReader(System.in);
      BufferedReader br = new BufferedReader(isr);
      String s = br.readLine();
      return s;
      }
// -------------------------------------------------------------
   public static char getChar() throws IOException
      {
      String s = getString();
      return s.charAt(0);
      }
//-------------------------------------------------------------
   public static int getInt() throws IOException
      {
      String s = getString();
      return Integer.parseInt(s);
      }
// -------------------------------------------------------------
   }  // end class TreeApp
////////////////////////////////////////////////////////////////

public class AlphabatizeLink {

}

我所做的修改发生在 insert() 中，底部的函数以 play() 开头。我想要得到的最终结果是，每个不是“+”作为叶子的字符，每个父母都有 2 个孩子，无论是字母字符还是“+”字符。

所以第一部分，用户输入输入，然后将它们作为字符放入树中。然后 fix root 方法将根重新插入到树的下方，并使根成为“+”。我对树的其余部分有同样的想法，横穿树而不是打印，修复它，但我得到了内存不足的错误。当您在 main 中去掉 theTree.Transverse() 中的 // 并在实际方法中去掉代码行时，您将看到错误。

score 3 · Accepted Answer

void f( Node current )
{
  if (current == null) return;

  f(current.left);

  // your code goes in here.

  f(current.right);

}

Call the above function with root node as the actual parameter.

score 2 · Accepted Answer

这种场景的递归函数（伪代码）的标准结构是这样的：

recurse(current)
{
    if(current is null) then return

    recurse(current.left)

    operateOnCurrentNode(current)

    recurse(current.right)
}

你得到一个空指针的原因是，在你的“fixTree(Node current)”递归方法调用中，你有这样的代码：

if (current.leftChild.iData != '+' || current.rightChild.iData != '+')

如果 current 有一个值但没有子节点（例如，一个 iData = '+' 的叶节点），那么上面的行将立即中断。您的代码假设，如果您的当前节点有一个值，那么它的左右指针也将有一个值。显然，对于叶节点，这是不正确的。'leftChild' 将为空，此时您实际上是在说：

if (current.NULL.iData != '+' || current.NULL.iData != '+')

“NULL”不能有“iData”字段。空指针异常。:)

解决这类问题的最佳方法是确保递归函数中的任何代码只查看该节点中当前的内容，而不是其每个子节点中的内容。（这不是一个硬性规定，但它是一个非常好的经验法则。）

我会给你一个可行的例子，但恐怕我不完全确定你的递归代码应该做什么。;)

score 0 · Accepted Answer

在检查它们是否为空之前，在 Tree 类中有很多地方使用变量，这显然不聪明。如果 root == null，此示例将给出 NullPointerException

public Node find(char key)
{
    Node current = root;
    while (current.iData != key)            // Exception if root == null
    {l
        if (key < current.iData) 
            current = current.leftChild;
        else
            current = current.rightChild;

        if (current == null)                // Checking for null is futile by now
            return null;
    }
    return current;
}

这也适用于这个功能：

public boolean delete(char key)
{
    Node current = root;
    Node parent = root;
    boolean isLeftChild = true;

    while (current.iData != key)        // Exception if root == null
    {

同样在 insert() 你有：

if (parent != root);
{
    parent.rightChild = plusNode;
}

if (parent != root);
{
    parent.leftChild = plusNode;
}

注意到那些分号了吗？我怀疑你想要那些。如果这对您没有帮助，您将不得不更清楚地了解您的问题。尝试将您的代码缩短到可以重现错误的最低限度。

java - 我在创建扫描整个二叉树的方法时遇到问题，你能帮我吗？（仍然需要帮助）

3 回答 3

Related

Reference