logo标签列表

如何使用Jackson将JSON对象反序列化为二叉树

jackson
3

在之前的问题如何将JSON数组反序列化为单链表中，我学会了如何将JSON数组反序列化为单链表。

现在我想在Java中将JSON对象反序列化为二叉树。

二叉树节点的定义如下：

public class BinaryTreeNode<E> {
    public E value;
    public BinaryTreeNode left;
    public BinaryTreeNode right;
    public BinaryTreeNode(final E value) {
        this.value = value;
    }
}

如何反序列化JSON字符串，例如：
{
  "value": 2,
  "left": {
    "value": 1,
    "left": null,
    "right": null
  },
  "right": {
    "value": 10,
    "left": {
      "value": 5,
      "left": null,
      "right": null
    },
    "right": null
  }
}

如何将一个数据结构转化为二叉树？

  2 
 / \ 
1   10 
   / 
  5

以下是单元测试示例代码：

@Test public void binaryTreeNodeTest() throws IOException {
    ObjectMapper objectMapper = new ObjectMapper();

    final ArrayList<Integer> intArray = objectMapper.readValue("[1,2,3,4,5]",
        new TypeReference<ArrayList<Integer>>() {});
    System.out.println(intArray);

    /* How to achieve this?
         2
        / \
       1   10
          /
         5
     {
       "value": 2,
       "left": {
        "value": 1,
        "left": null,
        "right": null
      },
      "right": {
        "value": 10,
        "left": {
          "value": 5,
          "left": null,
          "right": null
        },
        "right": null
      }
    }
    */
    final String jsonStr = "{\n"
        + "  \"value\": 2,\n"
        + "  \"left\": {\n"
        + "    \"value\": 1,\n"
        + "    \"left\": null,\n"
        + "    \"right\": null\n"
        + "  },\n" + "  \"right\": {\n"
        + "    \"value\": 10,\n"
        + "    \"left\": {\n"
        + "      \"value\": 5,\n"
        + "      \"left\": null,\n"
        + "      \"right\": null\n"
        + "    },\n"
        + "    \"right\": null\n"
        + "  }\n"
        + "}";
    System.out.println(jsonStr);
    final BinaryTreeNode<Integer> intTree = objectMapper.readValue(jsonStr,
        new TypeReference<BinaryTreeNode<Integer>>() {});
    System.out.println(intTree);
}

换句话说，我希望BinaryTreeNode和ArrayList一样成为一等公民，可以在各种组合中使用，例如HashSet<BinaryTreeNode<Integer>>，BinaryTreeNode<HashMap<String, Integer>>等。
1个回答
3
解决方案很简单，由于JSON可以自然地表达树形结构，因此Jackson可以直接处理递归树。只需用JsonCreator注释一个构造函数即可：
public static class BinaryTreeNode<E> 
{
    public E value;
    public BinaryTreeNode left;
    public BinaryTreeNode right;

    @JsonCreator
    public BinaryTreeNode(@JsonProperty("value") final E value) {
        this.value = value;
    }
}

让我们编写一个单元测试来尝试它：

package me.soulmachine.customized_collection;

import com.fasterxml.jackson.annotation.JsonCreator;
import com.fasterxml.jackson.annotation.JsonProperty;
import com.fasterxml.jackson.core.type.TypeReference;
import com.fasterxml.jackson.databind.ObjectMapper;
import org.junit.Test;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static org.junit.Assert.assertEquals;


public class BinaryTreeNodeTest {
    public static class BinaryTreeNode<E> {
        public E value;
        public BinaryTreeNode left;
        public BinaryTreeNode right;

        @JsonCreator
        public BinaryTreeNode(@JsonProperty("value") final E value) {
            this.value = value;
        }

        ArrayList<E> preOrder() {
            final ArrayList<E> result = new ArrayList<>();
            if (this.value == null) {
                return result;
            }
            preOrder(this, result);
            return result;
        }

        private static <E> void preOrder(BinaryTreeNode<E> root, ArrayList<E> result) {
            if (root == null)
                return;

            result.add(root.value);
            if (root.left != null)
                preOrder(root.left, result);
            if (root.right != null)
                preOrder(root.right, result);
        }
    }
    @Test public void binaryTreeNodeTest() throws IOException {
        ObjectMapper objectMapper = new ObjectMapper();
        /*
             2
            / \
           1   10
              /
             5
        */
        final String jsonStr = "{\n"
            + "  \"value\": 2,\n"
            + "  \"left\": {\n"
            + "    \"value\": 1,\n"
            + "    \"left\": null,\n"
            + "    \"right\": null\n"
            + "  },\n" + "  \"right\": {\n"
            + "    \"value\": 10,\n"
            + "    \"left\": {\n"
            + "      \"value\": 5,\n"
            + "      \"left\": null,\n"
            + "      \"right\": null\n"
            + "    },\n"
            + "    \"right\": null\n"
            + "  }\n"
            + "}";
        System.out.println(jsonStr);
        final BinaryTreeNode<Integer> intTree = objectMapper.readValue(jsonStr,
            new TypeReference<BinaryTreeNode<Integer>>() {});
        final List<Integer> listExpected = Arrays.asList(2, 1, 10, 5);
        assertEquals(listExpected, intTree.preOrder());
    }
}

一种紧凑的序列化格式

嗯，这里有一个小问题，上面的JSON字符串非常冗长。让我们使用另一种序列化格式，即按层次遍历序列化二叉树。例如，上面的二叉树可以序列化为以下JSON字符串:

[2,1,10,null,null,5]

现在如何将这个JSON字符串反序列化为二叉树？
这个想法与我之前的文章将JSON数组反序列化为单向链表非常相似。只需让BinaryTreeNode实现java.util.list，假装它是一个列表，编写我们自己的反序列化代码，以便Jackson可以将二叉树视为列表。 BinaryTreeNode的完整代码如下：
package me.soulmachine.customized_collection;


import java.util.*;

public class BinaryTreeNode<E> extends AbstractSequentialList<E>
    implements Cloneable, java.io.Serializable {
    public E value;
    public BinaryTreeNode<E> left;
    public BinaryTreeNode<E> right;

    /** has a left child, but it's a null node. */
    private transient boolean leftIsNull;
    /** has a right child, but it's a null node. */
    private transient boolean rightIsNull;

    /**
     * Constructs an empty binary tree.
     */
    public BinaryTreeNode() {
        value = null;
        left = null;
        right = null;
    }

    /**
     * Constructs an binary tree with one element.
     */
    public BinaryTreeNode(final E value) {
        if (value == null) throw new IllegalArgumentException("null value");
        this.value = value;
        left = null;
        right = null;
    }

    /**
     * Constructs a binary tree containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this binary tree
     * @throws NullPointerException if the specified collection is null
     */
    public BinaryTreeNode(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    /**
     * @inheritDoc
     *
     * <p>Note: null in the middle counts, so that each father in the binary tree has a
     * one-to-one mapping with the JSON array.</p>
     */
    public int size() {
        if (value == null) return 0;

        Queue<BinaryTreeNode<E>> queue = new LinkedList<>();
        queue.add(this);

        int count = 0;
        while (!queue.isEmpty()) {
            final BinaryTreeNode<E> node = queue.remove();
            ++count;
            if (node.left != null) {
                queue.add(node.left);
            } else {
                if (node.leftIsNull) ++count;
            }
            if (node.right != null) {
                queue.add(node.right);
            } else {
                if (node.rightIsNull) ++count;
            }
        }
        return count;
    }

    /**
     * Tells if the argument is the index of a valid position for an
     * iterator or an add operation.
     */
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size();
    }

    /**
     * Constructs an IndexOutOfBoundsException detail message.
     * Of the many possible refactorings of the error handling code,
     * this "outlining" performs best with both server and client VMs.
     */
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+ size();
    }

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private class NodeAndFather {
        private BinaryTreeNode<E> node;
        private BinaryTreeNode<E> father;
        private boolean isRight;  // the father is the right child of the father

        private NodeAndFather(BinaryTreeNode<E> node, BinaryTreeNode<E> father, boolean isRight) {
            this.node = node;
            this.father = father;
            this.isRight = isRight;
        }
    }

    /**
     * Returns the (may be null) Node at the specified element index.
     */
    NodeAndFather node(int index) {
        checkPositionIndex(index);
        if (value == null) return null;

        Queue<NodeAndFather> queue = new LinkedList<>();
        queue.add(new NodeAndFather(this, null, false));

        for (int i = 0; !queue.isEmpty(); ++i) {
            final NodeAndFather nodeAndFather = queue.remove();
            if ( i == index) {
                return nodeAndFather;
            }

            if (nodeAndFather.node != null) {
                queue.add(new NodeAndFather(nodeAndFather.node.left, nodeAndFather.node, false));
                queue.add(new NodeAndFather(nodeAndFather.node.right, nodeAndFather.node, true));
            }
        }
        throw new IllegalArgumentException("Illegal index: " + index);
    }

    /**
     * @inheritDoc
     */
    public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }

    private class ListItr implements ListIterator<E> {
        private NodeAndFather next;
        private int nextIndex;
        private int expectedModCount = modCount;

        ListItr(int index) {
            assert isPositionIndex(index);
            next = node(index);
            nextIndex = index;
        }

        public boolean hasNext() {
            final BinaryTreeNode<E> cur = next.node;
            return cur != null || (next.father.leftIsNull || next.father.rightIsNull);
        }

        //O(n)
        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            final E result = next.node != null ? next.node.value : null;
            next = node(nextIndex+1);
            nextIndex++;
            return result;
        }

        public boolean hasPrevious() {
            throw new UnsupportedOperationException();
        }

        public E previous() {
            throw new UnsupportedOperationException();
        }

        public int nextIndex() {
            throw new UnsupportedOperationException();
        }

        public int previousIndex() {
            throw new UnsupportedOperationException();
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public void set(E e) {
            throw new UnsupportedOperationException();
        }

        public void add(E e) {  // always append at the tail
            checkForComodification();

            if (next == null) { // empty list
                BinaryTreeNode.this.value = e;
                BinaryTreeNode.this.left = null;
                BinaryTreeNode.this.right = null;
            } else {
                final BinaryTreeNode<E> newNode = e != null ? new BinaryTreeNode<>(e) : null;
                if (next.father == null) { // root
                    BinaryTreeNode<E> cur = next.node;
                    cur.left = newNode;
                    assert cur.right == null;
                    throw new UnsupportedOperationException();
                } else {
                    if (next.isRight) {
                        if (next.father.right != null) throw new IllegalStateException();
                        next.father.right = newNode;
                        if (newNode == null) {
                            next.father.rightIsNull = true;
                        }
                    } else {
                        if (next.father.left != null) throw new IllegalStateException();
                        next.father.left = newNode;
                        if (newNode == null) {
                            next.father.leftIsNull = true;
                        }

                    }
                }
            }
            modCount++;
            expectedModCount++;
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

    // the following functions are just for unit tests.
    ArrayList<E> preOrder() {
        final ArrayList<E> result = new ArrayList<>();
        if (this.value == null) {
            return result;
        }
        preOrder(this, result);
        return result;
    }

    private static <E> void preOrder(BinaryTreeNode<E> root, ArrayList<E> result) {
        if (root == null)
            return;

        result.add(root.value);
        if (root.left != null)
            preOrder(root.left, result);
        if (root.right != null)
            preOrder(root.right, result);
    }

    ArrayList<E> inOrder() {
        final ArrayList<E> result = new ArrayList<>();
        if (this.value == null) {
            return result;
        }
        inOrder(this, result);
        return result;
    }

    private static <E> void inOrder(BinaryTreeNode<E> root, ArrayList<E> result) {
        if (root == null)
            return;

        if (root.left != null)
            inOrder(root.left, result);
        result.add(root.value);
        if (root.right != null)
            inOrder(root.right, result);
    }

    ArrayList<E> postOrder() {
        final ArrayList<E> result = new ArrayList<>();
        if (this.value == null) {
            return result;
        }
        postOrder(this, result);
        return result;
    }

    private static <E> void postOrder(BinaryTreeNode<E> root, ArrayList<E> result) {
        if (root == null)
            return;

        if (root.left != null)
            postOrder(root.left, result);
        if (root.right != null)
            postOrder(root.right, result);
        result.add(root.value);
    }

    ArrayList<E> levelOrder() {
        final ArrayList<E> result = new ArrayList<>();
        if (this.value == null) {
            return result;
        }

        Queue<BinaryTreeNode<E>> queue = new LinkedList<>();
        queue.add(this);

        while (!queue.isEmpty()) {
            final BinaryTreeNode<E> node = queue.remove();
            result.add(node.value);

            if (node.left != null)
                queue.add(node.left);

            if (node.right != null)
                queue.add(node.right);
        }
        return result;
    }
}

然后进行单元测试：

java
package me.soulmachine.customized_collection;

import com.fasterxml.jackson.core.type.TypeReference;
import com.fasterxml.jackson.databind.ObjectMapper;
import org.junit.Test;

import java.io.IOException;
import java.util.Arrays;
import java.util.List;

import static org.junit.Assert.assertEquals;

public class BinaryTreeNodeTest
{
    @Test public void deserializeTest() throws IOException {
        ObjectMapper objectMapper = new ObjectMapper();
        final List<Integer> intList = Arrays.asList(2,1,10,null,null,5);

        /*
             2
            / \
           1   10
              /
             5
        */
        // TODO: the time complexity is O(n^2)
        final BinaryTreeNode<Integer> intTree = objectMapper.readValue("[2,1,10,null,null,5]",
            new TypeReference<BinaryTreeNode<Integer>>() {});
        assertEquals(intList, intTree);

        assertEquals(Arrays.asList(2, 1, 10, 5), intTree.levelOrder());
        assertEquals(Arrays.asList(2, 1, 10, 5), intTree.preOrder());
        assertEquals(Arrays.asList(1, 2, 5, 10), intTree.inOrder());
        assertEquals(Arrays.asList(1, 5, 10, 2), intTree.postOrder());
    }
}

这篇文章受到Tatu Saloranta的启发，参考自this post，在此特别感谢他！
这是我的原始博客，将JSON字符串反序列化为二叉树。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接