将二叉树转换为双链表

I am trying to write a function in java to convert a binary tree to DLL. The function executes without error but the DLL is not being made. Following is the function. root is pointer to the root of the tree and head points to the starting node of the DLL.

我试图在java中编写一个函数来将二叉树转换为DLL。该函数执行时没有错误,但没有生成DLL。以下是该功能。 root是指向树根的指针,head指向DLL的起始节点。

public void dll(Node x)
    {

        if(x==null)
        {
            return;
        }
        else
        {
            if(x==root)
            {
                Node temp=root;
                while(temp.left!=null)
                {
                    temp=temp.left;
                }
                head=temp;
            }

            if(x.left!=null)
            {
                System.out.println(x.data);

                Node lchild=x.left;
                Node rightmost=lchild;
                while(rightmost.right!=null)
                {
                    rightmost=rightmost.right;
                }
                x.left=rightmost;
                rightmost.right=x;
                dll(lchild);

            }
            if(x.right!=null)
            {
                System.out.println(x.data);

                Node rchild=x.right;
                Node leftmost=rchild;

                while(leftmost.left!=null)
                {
                    leftmost=leftmost.left;
                }

                x.right=leftmost;
                leftmost.left=x;
                dll(rchild);
            }




        }

    }
}

The logic is as follows: Find the rightmost in left subtree and make is previous node of root and find leftmost in right sub tree and make it next of the root. Recursive apply for subtrees.

逻辑如下:在左子树中找到最右边的,并且make是根的前一个节点,在右子树中找到最左边的,然后在根的下一个。递归申请子树。

When I try to print head.right, it gives me Null pointer exception.

当我尝试打印head.right时,它给了我Null指针异常。

Exception in thread "main" java.lang.NullPointerException
        at BTtoDll.main(BTtoDll.java:153)

Line 153 is -

第153行是 -

 System.out.println(t.head.right.data);

3 个解决方案

#1

The pure recursive function in fact does the same: the right-most of the left subtree connected to x and x connected to the left-most of the right subtree. I thought you might be interested to see the congruity.

实际上,纯递归函数也是如此:左边的子树最右边连接到x,x连接到右边子树的最左边。我想你可能有兴趣看到一致性。

public DLL dll(Node x) {
    return dll(null, x, null);
}

public DLL dll(DLL before, Node x, DDL after) {
    if (x == null) {
        return;
    }
    if (x.left != null) {
        before = dll(before, x.left, null);
    }
    if (x.right != null) {
        after = dll(null, x.left, after);
    }
    DLL result = new DLL();
    result.insert(x.value);
    result.insertBefore(before); // null being a no-op.
    result.insertAfter(after); // null being a no-op.
    return result;
}

As one can see, there are several variations thinkable.

可以看出,有几种可以想象的变化。

#2

Here you assign x.left and x.right to x:

在这里,您将x.left和x.right分配给x:

if(x.left!=null)
{
    ...
    rightmost=x;
    x.left=rightmost;
    ...
}
if(x.right!=null)
{
    ...
    leftmost=x;
    x.right=leftmost;
    ...
}

I can't tell what it's supposed to be to say what to change it to but that's probably your bug. The list won't be relinked.

我不知道该说什么改变它应该是什么,但这可能是你的错误。该列表不会重新链接。

#3

As for your NullPointerException, I think that

至于你的NullPointerException,我认为

          while(leftmost!=null)

should be

          while(leftmost.left!=null)