二叉搜索树到双向链表

Question

我正在使用递归从二叉搜索树创建双向链表，当 BST 已经填充时它工作得很好，即 >=2 个节点。但是，我尝试运行它用于动态填充的 BST，一旦我将子节点插入 BST 的根节点，它就会给我一个 WhosebugError。这是我写的代码（在 Java 中）

public class BSTtoDLL {
/* Binary Search Tree to Doubly Linked List conversion*/

     // head --> Pointer to head node of created doubly linked list
     static BTNode head;

     // Initialize previously visited node as NULL. This is
     // static so that the same value is accessible in all recursive
     // calls
     static BTNode prev = null;

    /* BSTtoDLL Construtor */
    public BSTtoDLL(){
        head = null;
        prev = null;
    }

     // A simple recursive function to convert a given Binary tree 
     // to Doubly Linked List
     // root --> Root of Binary Tree
     void BinaryTree2DoubleLinkedList(BTNode root)
     {
         // Base case
         if (root == null)
             return;

         // Recursively convert left subtree
         if(root.left!=null)
            BinaryTree2DoubleLinkedList(root.left);

         // Now convert this node
         if (prev == null){
             head = root;
         }
         else
         {
             prev.right = root;
             root.left = prev;
         }
         prev = root;

         // Finally convert right subtree
         BinaryTree2DoubleLinkedList(root.right);
     }

控制台响应：

Binary Tree Test
Converting to a DLL
Data--34--Left is Null----Right is Null---
Binary Tree Test Converting to a DLL Exception in thread "main" java.lang.WhosebugError
at com.techwealth.BSTtoDLL.BinaryTree2DoubleLinkedList(BSTtoDLL.java:32)
at com.techwealth.BSTtoDLL.BinaryTree2DoubleLinkedList(BSTtoDLL.java:32)
at com.techwealth.BSTtoDLL.BinaryTree2DoubleLinkedList(BSTtoDLL.java:32)
at com.techwealth.BSTtoDLL.BinaryTree2DoubleLinkedList(BSTtoDLL.java:32)
at com.techwealth.BSTtoDLL.BinaryTree2DoubleLinkedList(BSTtoDLL.java:32)

Answer 1

显然，您缺少终止条件（基本情况无效，因为您使用的是静态变量）。这就是您看到 Whosebug 错误的原因。通过此 link 了解有关此错误的更多信息：What is a WhosebugError?

二叉搜索树到双向链表

Binary Search Tree to Doubly Linked List

binary-search-tree

doubly-linked-list