一维数组转二叉树、注解回滚、eclipse配置代码自动补全

最近对红黑树产生了兴趣,想研究一波,找了篇文章说需要具备二叉查找树和完美平衡二叉树的知识,我慌了... ...

怎么办呢?学一手吧,找了一篇二叉树教学文章,然而它告诉我要先学递归算法,递归这东西我知道,就是没怎么用过,理论懂点,实操手生。

先简单回顾了一下递归,然后找了道经典习题热热身,再然后开始着手重学二叉树,早知如此当初接触这东西的时候就应该学好。

当我学习到二叉树的存储结构中的顺序存储时,产生了一个疑问,如何将一维数组存储为二叉树结构?

通常学习进度到了这个地方我会选择查一手百度,但是今天就是想用自己的思路硬怼一波。

我希望将数组的第一个数据存储在根节点,第二个数据存储在根节点的左子节点,以此类推。

首先,搞一个节点类:

public class Node {
    private int nodeId; //心血来潮加了个id,没必要
    private int nodeNum;
    private Node leftNode;
    private Node rightNode;

    public Node(int nodeId, int nodeNum) {
        this.nodeId = nodeId;
        this.nodeNum = nodeNum;
    }

    public Node getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }

    @Override
    public String toString() { //最后打印看效果
        return "Node{" +
                "nodeId=" + nodeId +
                ", nodeNum=" + nodeNum +
                '}';
    }
}

然后,搞了个数组转二叉树的构建类,名字半天想不出来,就先用builder吧,反正是练习起名随意点吧。

public class NodeBuilder {

public Node rootNode = null;
public AtomicInteger adder = new AtomicInteger(1);
public static Queue<Node> queue = new ArrayDeque<>();

public NodeBuilder(int[] arr) {

if (arr.length == 0 || arr == null)
throw new RuntimeException("are you kidding?");

rootNode = new Node(adder.getAndAdd(1), arr[0]);
queue.add(rootNode);
for (int i = 1; i < arr.length; i++) {
Node node = queue.peek();
Node nextNode = new Node(adder.getAndAdd(1), arr[i]);

if (node.getLeftNode() != null && node.getRightNode() != null) {
queue.poll();
node = queue.peek();
}

if (node.getLeftNode() == null) {
node.setLeftNode(nextNode);
} else if (node.getRightNode() == null) {
node.setRightNode(nextNode);
}

queue.add(nextNode);
}
}
}

rootNode是根节点,AtomicInteger用于生成节点序号,队列用于记录节点引用。

我自己的思路就是维护一个队列用于存放节点,首先创建根节点存储数组第一位数据,然后入队。

后续的数组数据开始遍历,获取队列头的节点但不出队,判断左节点是否有对象,没有的话直接创建节点存进去。

左节点有对象的话,就继续判断右节点,关键在于每创建一个新节点都要入队,因为后续还要往这些子节点中继续存入节点。

当根节点存满后,就会被出队,然后获取到的队列头节点就是根节点的左节点,因为入队时是按照先左后右的顺序。

最终搞了一个类测试一下:

public class Boot {
    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3,4,5,6,7,8,9,0};
        NodeBuilder nodeBuilder = new NodeBuilder(arr);
        System.out.println(nodeBuilder.rootNode);
        print(nodeBuilder.rootNode);
    }

    static void print(Node node) {
        if (node == null) {
            return;
        }
        if (node.getLeftNode() != null)
            System.out.println(node.getLeftNode());
        if (node.getRightNode() != null)
            System.out.println(node.getRightNode());

        print(node.getLeftNode());
        print(node.getRightNode());
    }
}

首先创建了一个朴实无华的整型数组,然后转为二叉树,打印根节点,递归打印剩余节点。

我这种递归好像叫深度优先搜索吧,不太记得了,反正最终发现节点序号和数组对的上,应该是没啥问题,打印结果如下:

Node{nodeId=1, nodeNum=1}
Node{nodeId=2, nodeNum=2}
Node{nodeId=3, nodeNum=3}
Node{nodeId=4, nodeNum=4}
Node{nodeId=5, nodeNum=5}
Node{nodeId=8, nodeNum=8}
Node{nodeId=9, nodeNum=9}
Node{nodeId=10, nodeNum=0}
Node{nodeId=6, nodeNum=6}
Node{nodeId=7, nodeNum=7}

今天领导让修改了一下项目中的@Transactional,改为@Transactional(rollbackFor=Exception.class),查了一下,就是抛出异常后数据回滚,但是,我怎么记得不加括号的内容它也回滚呢?

这个改天研究吧 ... ...

最后,记录一个eclipse小技巧,配置代码补全:

进入eclipse——>点击window——>点击preferences——>点击java——>点击editor——>点击content assist——>修改如图所示的内容:

一维数组转二叉树、注解回滚、eclipse配置代码自动补全

 

.AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz

 改好后apply一下什么的,就可以了。

上一篇:mysql order by操作性能问题


下一篇:网关的简介