关于 AJVisual 数据结构可视化网站的开发

前言：由于和以前的开发日志一样，以下只展示部分代码，功能展示使用二叉树作为案例讲解。由于本项目只是一个学校作业，由于项目逻辑比较简单，核心功能会进行具体讲解，其他一些有的没的可以后台留言，或者自行百度。

项目介绍：这是一个基于 SpringBoot + Ajax + D3.js 实现的一个数据结构在线展示的项目。后端使用了 SpringBoot ， Ajax 提供网络请求和数据刷新，前端使用了 Thymleaf 模板引擎，BootStarp 提供 UI 样式支持

核心技术栈：
​ SpringBoot 后端服务实现
​ BootStarp 前端 ui
​ D3.js 驱动 DOM 操作
​ jQuery js 库
​ Thymleaf 模板引擎
​ Ajax 提供网络请求和异步刷新
​ log4j 日志打印
​ Maven 项目构建工具

一. 准备工作和项目搭建

1.1 新建 SpringBoot 项目

这个还是不用多说了，这个你都不会的话，可以埋了。

1.2 确定项目结构

基础项目结构

1.3 依赖导入及配置文件编写

pom.xml

    <dependencies>
        <!-- thymeleaf 模板引擎 -->
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-thymeleaf</artifactId>
        </dependency>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-web</artifactId>
        </dependency>
        <!-- SpringBoot 开发工具集 -->
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-devtools</artifactId>
            <scope>runtime</scope>
            <optional>true</optional>
        </dependency>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-test</artifactId>
            <scope>test</scope>
            <exclusions>
                <exclusion>
                    <groupId>org.junit.vintage</groupId>
                    <artifactId>junit-vintage-engine</artifactId>
                </exclusion>
            </exclusions>
        </dependency>
        <!-- lombok 插件 -->
        <dependency>
            <groupId>org.projectlombok</groupId>
            <artifactId>lombok</artifactId>
            <optional>true</optional>
        </dependency>
    </dependencies>

    <build>
        <plugins>
            <plugin>
                <groupId>org.springframework.boot</groupId>
                <artifactId>spring-boot-maven-plugin</artifactId>
                <configuration>
                    <fork>true</fork>
                </configuration>
            </plugin>
        </plugins>
    </build>

application.properties

spring.thymeleaf.cache=false

spring.devtools.restart.enabled= true

spring.devtools.restart.additional-paths= src/main/java

spring.devtools.restart.exclude= test/**

spring.mvc.view.prefix=/templates/

spring.mvc.view.suffix=.html

二. 项目骨架搭建

2.1 开发项目逻辑结构

完整的项目结构

图接上图

三. 基础代码编写

3.1 定义颜色以及大小

以下是可视化图形的颜色及其大小定义，例如二叉树里面的球，重点是类中的 id ，属于 CSS 属性，方便 d3 select 某个 circle

constant 下的 Color（类）

public class Color {
    public static final int RED = 1;
    public static final int ORANGE = 2;
    public static final int YELLOW = 3;
    public static final int GREEN = 4;
    public static final int BLUE = 5;
    public static final int BLACK = 6;
    public static final int WHITE = 7;
    public static final int GRAY = 8;
}

domain 下的 Circle（类）

@Data
public class Circle {
    private int cx;
    private int cy;
    private int r;
    private int fill;
    private int stroke;
    private String id;

    public Circle(int cx, int cy, int r, int fill, int stroke, String id) {
        this.cx = cx;
        this.cy = cy;
        this.r = r;
        this.fill = fill;
        this.stroke = stroke;
        this.id = id;
    }
}

domain 下的 Tree（类）

@Data
public class Tree {
    private List<Line> edgeGroup;
    private List<Circle> vertexGroup;
    private List<Text> vertexTextGroup;

    public Tree(){}

    // 深拷贝!!!
    public Tree(Tree tree) {
        this.edgeGroup = new ArrayList<>();
        this.vertexGroup = new ArrayList<>();
        this.vertexTextGroup = new ArrayList<>();
        for (Line l :
                tree.getEdgeGroup()) {
            edgeGroup.add(new Line(l.getX1(), l.getY1(), l.getX2(), l.getY2(), l.getStroke(), l.getId()));
        }
        for (Circle c :
                tree.getVertexGroup()) {
            vertexGroup.add(new Circle(c.getCx(), c.getCy(), c.getR(), c.getFill(), c.getStroke(), c.getId()));
        }
        for (Text t :
                tree.getVertexTextGroup()) {
            vertexTextGroup.add(new Text(t.getX(), t.getY(), t.getStroke(), t.getText(), t.getId()));
        }
    }
}

domain 下的 TreeFrame（类）

@Data
public class TreeFrame {
    private List<Tree> frames;
}

以下是公共操作的可复用代码（例如颜色尺寸等等)

static 下的 common.js

const Color = {
    1: 'red',
    2: 'orange',
    3: 'yellow',
    4: 'green',
    5: 'blue',
    6: 'black',
    7: 'white',
    8: '#999'
};
const Width = 1000;
const Height = 570;
const svg = d3.select('svg');
svg.attr('width', Width)
    .attr('height', Height);

let frames;   // 动画帧
let idx = 0;  // 第几帧
let state;    // 当前运行的算法

// 操控面板
let isPause = false;
document.querySelector('#pause').onclick = () => {
    isPause = true;
};

document.querySelector('#play').onclick = () => {
    if (isPause) {
        isPause = false;
        drawFrames();
    }
};
document.querySelector('#preFrame').onclick = () => {
    // pause时 且不为0
    if (isPause && idx > 0) {
        idx =  idx - 1;
        drawOneFrame();
    }
};
document.querySelector('#nextFrame').onclick = () => {
    // pause时
    if (isPause && idx < frames.length-1) {
        idx = idx + 1;
        drawOneFrame();
    }
};
document.querySelector('#clearing').onclick = () => {
    if (idx !== 0) {
        idx = 0;
        // 清除此函数
        clearInterval(intervalID);
        state = States.create;
        drawOneFrame();
    }
};

// timeout = durationT
const timePerFrame = 1000;  // 1 second/frame
let durationT = timePerFrame;
let rate = 1;
document.querySelector('#speed2').onclick = () => {
    // 变速要重新创建动画
    clearInterval(intervalID);
    rate = 1.5;
    durationT = rate * timePerFrame;
    drawFrames();
};
document.querySelector('#speed3').onclick = () => {
    clearInterval(intervalID);
    rate = 1;
    durationT = rate * timePerFrame;
    drawFrames();
};
document.querySelector('#speed4').onclick = () => {
    clearInterval(intervalID);
    rate = 0.5;
    durationT = rate * timePerFrame;
    drawFrames();
};
document.querySelector('#speed5').onclick = () => {
    clearInterval(intervalID);
    rate = 0.25;
    durationT = rate * timePerFrame;
    drawFrames();
};

// 异步动画
let intervalID;
function drawFrames() {
    intervalID = setInterval(() => {
        if (idx >= frames.length || isPause) {
            console.log('clear', idx);
            // 当前帧为idx-1 注意溢出
            if (isPause && idx > 0) {
                idx = idx - 1;
            }
            clearInterval(intervalID);
        } else {
            drawOneFrame();
            idx = idx + 1;
        }
    }, durationT);
}

四. 核心代码编写

通过 ajax 请求对数据进行处理

static 下的 btree.js（js 文件）

let tree;
// 操作状态
const States = {
    create: 1,
    inorder: 2,
    search: 3,
    preOrder: 4
};
document.querySelector("#create").onclick = () => {
    // console.log('按');
    clearInterval(intervalID);
    let input = document.querySelector("#input").value;
    input = input.split(",").map(i => parseInt(i));

    let formData = {
        array: input
    };

    $.ajax({
        type : "POST",
        contentType : "application/json",  // 必需
        url : "api/btree/create",
        data : JSON.stringify(formData),
        dataType : 'json',
        success : function(response) {
            // console.log(response);
            frames = response.frames;
            idx = 0;
            state = States.create;
            creatDraw();
        },
        error : function(e) {
            alert("Error!");
            console.log("ERROR: ", e);
        }
    });
};
document.querySelector("#inorder").onclick = () => {
    clearInterval(intervalID);
    $.ajax({
        type : "GET",
        url : "api/btree/inOrder",
        success : function(response) {
            // changes = response.changes;
            // inOrderDraw();
            frames = response.frames;
            idx = 0;
            state = States.inorder;
            drawFrames();
        },
        error : function(e) {
            alert("Error!");
            console.log("ERROR: ", e);
        }
    });
};
document.querySelector("#search").onclick = () => {
    clearInterval(intervalID);
    let num = document.querySelector("#num").value;
    num = parseInt(num);
    $.ajax({
        type : "GET",
        url : "api/btree/search",
        data: {num: num},
        success : function(response) {
            frames = response.frames;
            // console.log(frames);
            idx = 0;
            state = States.search;
            drawFrames();
        },
        error : function(e) {
            alert("Error!");
            console.log("ERROR: ", e);
        }
    });
};
document.querySelector("#preorder").onclick = () => {
    clearInterval(intervalID);
    $.ajax({
        type : "GET",
        url : "api/btree/preOrder",
        success : function(response) {
            frames = response.frames;
            // console.log(frames);
            idx = 0;
            state = States.preOrder;
            drawFrames();
        },
        error : function(e) {
            alert("Error!");
            console.log("ERROR: ", e);
        }
    });
};


let vertexGroup ;
let edgeGroup;
let vertexTextGroup ;
function creatDraw() {
    tree = frames[idx];
    // console.log(tree);
    d3.selectAll('g').remove();
    vertexGroup = svg.append('g').attr('id', 'v');
    edgeGroup = svg.append('g').attr('id', 'e');
    vertexTextGroup = svg.append('g').attr('id', 't');
    let delayT = 800;
    // const r = 15;
    vertexGroup.selectAll('circle').data(tree.vertexGroup).enter().append('circle')
        .transition()
        .duration(durationT * 0.6)
        .delay((d,i) => delayT * i * rate)
        .attr('cx', d => d.cx )
        .attr('cy', d => d.cy )
        .attr('r', d => d.r )
        .attr('fill', d => Color[d.fill])
        .attr('stroke', d => Color[d.stroke] )
        .attr('id', d => d.id);
    edgeGroup.selectAll('line').data(tree.edgeGroup).enter().append('line')
        .transition()
        .duration(durationT * 0.6)
        .delay((d,i) => delayT * i * rate)
        .attr('x1', d => d.x1 )
        .attr('y1', d => d.y1 )
        .attr('x2', d => d.x2 )
        .attr('y2', d => d.y2 )
        .attr('stroke', d => Color[d.stroke] )
        .attr('stroke-width', 1)
        .attr('id', d => d.id);
    vertexTextGroup.selectAll('text').data(tree.vertexTextGroup).enter().append('text')
        .transition()
        .duration(durationT * 0.6)
        .delay((d,i) => delayT * i * rate)
        .attr('x', d => d.x - 5)
        .attr('y', d => d.y + 5)
        .attr('stroke', d => Color[d.stroke])
        .text(d => d.text)
        .attr('id', d => d.id);
}


function drawOneFrame() {
    console.log(idx);
    tree = frames[idx];
    vertexGroup.selectAll('circle').data(tree.vertexGroup)
        .transition()
        .duration(durationT)
        .attr('cx', d => d.cx )
        .attr('cy', d => d.cy )
        .attr('r', d => d.r )
        .attr('fill', d => Color[d.fill])
        .attr('stroke', d => Color[d.stroke] );
    edgeGroup.selectAll('line').data(tree.edgeGroup)
        .transition()
        .duration(durationT)
        .attr('x1', d => d.x1 )
        .attr('y1', d => d.y1 )
        .attr('x2', d => d.x2 )
        .attr('y2', d => d.y2 )
        .attr('stroke', d => Color[d.stroke] )
        .attr('stroke-width', () => state > 1? 2: 1);
    vertexTextGroup.selectAll('text').data(tree.vertexTextGroup)
        .transition()
        .duration(durationT)
        .attr('x', d => d.x - 5)
        .attr('y', d => d.y + 5)
        .attr('stroke', d => Color[d.stroke])
        .attr('font-weight', 'bold')
        .attr('font-size', 20)
        .text(d => d.text);
    
}

controller 下 TreeController（类）

@RestController
@RequestMapping(path = "/api/btree")
public class TreeController {

    private BSTService bstService;

//    private Tree initTree;

    @PostMapping("create")
    public TreeFrame create(@RequestBody Array array) {
//        Integer[] a = new Integer[]{84, 24, 57, 87, 13, 9, 56};
        // 每次响应create button都要new 对象,清除之前的树结构
        bstService = new BSTService();
        for (Integer integer : array.getArray()) {
            bstService.add(integer);
        }
        TreeFrame treeFrame = bstService.create();
//        initTree = treeFrame.getFrames().get(0);
        return treeFrame;
    }

    @GetMapping("inOrder")
    public TreeFrame inOrder() {
        return bstService.inorder();
    }

    @GetMapping("search")
    public TreeFrame search(@PathParam(value = "num") int num) {
        return bstService.search(num);
    }

    @GetMapping("preOrder")
    public TreeFrame preOrder() {
        return bstService.preorder();
    }
}

service 下的 BSTService（类）

@Service
public class BSTService {

    public static final int FullBTHei = 6;
    private Node root = null;

    private Tree initTree;
    // 邻接矩阵存边的id
//    private int[][] adjM = new int[64][64];

    // CSS id
    String circleIdTemp = "C%d";
    String lineIdTemp = "%sC%d";
    String textIdTemp = "TC%d";
    int ID = 1;     // node's id number

    // private class Node extends Circle ?
    private static class Node{
        int data;
        Circle circle;
        Node left;
        Node right;

        Node(int d) {
            data = d;
            left = null;
            right = null;
        }
    }

    public static void main(String[] args) {
//        Integer[] array = {84, 24, 57, 87, 13, 9, 56};
//        BSTService tree = new BSTService();
//        tree.create();
//
//        tree.inorder();

//        List<Circle> circles = new ArrayList<>();
//        Circle c1 = new Circle(1,2,3,4,5);
//        circles.add(c1);
//        c1 = new Circle(3,4,3,4,5);
//        circles.add(c1);
//        for (Circle c :
//                circles) {
//            System.out.println(c.getCx());  // 1 \n 3
//        }

    }

    public TreeFrame create() {

        //array = new Integer[]{84, 24, 57, 87, 13, 9, 56};
//        BSTService bst = new BSTService();
//        for (Integer integer : array) {
//            bst.add(integer);
//        }

        TreeFrame treeFrame = new TreeFrame();
        List<Tree> frames = new ArrayList<>();
        initTree = new Tree();
        List<Line> edgeGroup = new ArrayList<>();
        List<Circle> vertexGroup = new ArrayList<>();
        List<Text> vertexTextGroup = new ArrayList<>();

        int r = 15;
        // 孩子节点与其父节点高度差
        int heiDif = 80;
        // 孩子节点与其父节点水平偏移量
        int offset = (int) (r * Math.pow(2, FullBTHei - 2));
        int cx = SVG.WIDTH / 2;
        int cy = heiDif;
        int fill = Color.WHITE;
        int stroke = Color.BLACK;
        
        // 层序遍历建初始帧

        Circle node = new Circle(cx, cy, r, fill, stroke, String.format(circleIdTemp, ID));
        Text data = new Text(cx, cy, stroke, String.valueOf(root.data), String.format(textIdTemp, ID));
        ID++;
        // 让node携带更多信息
        root.circle = node;

        vertexGroup.add(node);
        vertexTextGroup.add(data);

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        int level = 0;
        int count = 1;  // 每层入队总数
        while (!queue.isEmpty()) {
            int c = count;
            level++;
            count = 0;
            while (c-- > 0) {
                Node parent = queue.poll();
//                System.out.print(parent.data + " ");

                if (parent.left != null) {
                    cx = parent.circle.getCx() - offset;
                    setGraph(edgeGroup, vertexGroup, vertexTextGroup, heiDif, cx, cy + heiDif * level,
                            r, fill, stroke, level, parent, true);
                    queue.add(parent.left);
                    count++;
                }

                if (parent.right != null) {
                    cx = parent.circle.getCx() + offset;
                    setGraph(edgeGroup, vertexGroup, vertexTextGroup, heiDif, cx, cy + heiDif * level,
                            r, fill, stroke, level, parent, false);
                    queue.add(parent.right);
                    count++;
                }
            }
            offset /= 2;
        }

        initTree.setEdgeGroup(edgeGroup);
        initTree.setVertexGroup(vertexGroup);
        initTree.setVertexTextGroup(vertexTextGroup);
//        System.out.println(initTree);
        frames.add(initTree);
        treeFrame.setFrames(frames);
        return treeFrame;
    }

    private void setGraph(List<Line> edgeGroup, List<Circle> vertexGroup, List<Text> vertexTextGroup,
                          int heiDif, int cx, int cy, int r, int fill, int stroke, int level, Node parent, boolean L) {
        Circle node;
        Text data;
        Line edge;
        node = new Circle(cx, cy, r, fill, stroke, String.format(circleIdTemp, ID));
        data = new Text(cx, cy, stroke, String.valueOf(L ? parent.left.data : parent.right.data),
                String.format(textIdTemp, ID));
        edge = new Line(parent.circle.getCx(), parent.circle.getCy(), cx, cy, stroke,
                String.format(lineIdTemp, parent.circle.getId(), ID));
        ID++;
        if (L) {
            parent.left.circle = node;
        } else {
            parent.right.circle = node;
        }
        vertexGroup.add(node);
        vertexTextGroup.add(data);
        edgeGroup.add(edge);
    }

    private boolean search(Node node, int data, List<Tree> frames) {
        String temp = "n=%d %c %s,%s";
        if (node == null) {
            return false;
        } else if (node.data == data) {
            Tree tree = new Tree(frames.get(frames.size() - 1));
            int circleId = Integer.parseInt(node.circle.getId().substring(1));
            tree.getVertexGroup().get(circleId - 1).setFill(Color.ORANGE);
            tree.getVertexTextGroup().get(circleId - 1).setStroke(Color.RED);
            tree.getVertexTextGroup().get(circleId - 1).setText(data + "找到了");
            frames.add(tree);
            return true;
        } else if (node.data > data) {
            // 复制一整颗树
            Tree tree = new Tree(frames.get(frames.size() - 1));
            int circleId = Integer.parseInt(node.circle.getId().substring(1));
            tree.getVertexGroup().get(circleId - 1).setStroke(Color.ORANGE);
            tree.getVertexTextGroup().get(circleId - 1).setText(String.format(temp, data, '<',
                    tree.getVertexTextGroup().get(circleId - 1).getText(), "找左孩子"));
            frames.add(tree);
            if (node.left != null) {
                tree = new Tree(frames.get(frames.size() - 1));
                // 叶节点id - 1 = 此节点与父相连边id
                int lineId = Integer.parseInt(node.left.circle.getId().substring(1)) - 1;
                tree.getEdgeGroup().get(lineId - 1).setStroke(Color.ORANGE);
                frames.add(tree);
            }
            return search(node.left, data, frames);
        } else {
            Tree tree = new Tree(frames.get(frames.size() - 1));
            int circleId = Integer.parseInt(node.circle.getId().substring(1));
            tree.getVertexGroup().get(circleId - 1).setStroke(Color.ORANGE);
            tree.getVertexTextGroup().get(circleId - 1).setText(String.format(temp, data, '>',
                    tree.getVertexTextGroup().get(circleId - 1).getText(), "找右孩子"));
            frames.add(tree);
            if (node.right != null) {
                tree = new Tree(frames.get(frames.size() - 1));
                // 叶节点id - 1 = 此节点与父相连边id
                int lineId = Integer.parseInt(node.right.circle.getId().substring(1)) - 1;
                tree.getEdgeGroup().get(lineId - 1).setStroke(Color.ORANGE);
                frames.add(tree);
            }
            return search(node.right, data, frames);
        }
    }

    public TreeFrame search(int data) {
        TreeFrame treeFrame = new TreeFrame();
        List<Tree> frames = new ArrayList<>();
        frames.add(initTree);
        if (!search(this.root, data, frames)) {
            System.out.println("not found " + data);
        }
        System.out.println(frames);
        treeFrame.setFrames(frames);
        return treeFrame;
    }

    // d3.select(有改变元素id) 属性变换过渡
//    private void inOrder(Node node, List<GraphChange> changes) {
//        if (node == null) {
//            return;
//        }
//        // 当前遍历到visitC节点
//        Circle visitC = node.circle;
//        visitC.setStroke(Color.YELLOW);
//        visitC.setFill(Color.WHITE);
//
//        // node与circle绑定,易找原circle,text与circle在group里的index(记录在id)相同,从而找原text
////        int idx = Integer.parseInt(visitC.getId()) - 1;  // id从1始
////        Text visitT = vertexTextGroup.get(idx);
////        visitT.setStroke(Color.YELLOW);
//
//        String textId = "T" + node.circle.getId();
//        Text visitT = new Text(0, 0, Color.YELLOW, "", textId);
//        changes.add(new GraphChange(visitC, visitT, null));
////        System.out.println(changes);
//        if (node.left != null) {
//            // 当前遍历到visitL边
//            // 通过相同id直接新建line,为需改变的属性(stroke)赋值
//            String lindId = node.circle.getId() +  node.left.circle.getId();
//            Line visitL = new Line(0, 0, 0, 0, Color.YELLOW, lindId);
//            changes.add(new GraphChange(null, null, visitL));
//
//            inOrder(node.left, changes);
//        }
//
//        // 访问此节点
//        // 必须new新circle, visitedC = node.circle 后 visitedC.setXX 会覆盖之前加入changes的visitC(两者都指向node.circle)
//        Circle visitedC = new Circle(0, 0, 0, Color.YELLOW, 0, node.circle.getId());
//        textId = "T" + node.circle.getId();
//        Text visitedT = new Text(0, 0, Color.RED, "", textId);
//        changes.add(new GraphChange(visitedC, visitedT, null));
//
//        if (node.right != null) {
//            String lindId = node.circle.getId() +  node.right.circle.getId();
//            Line line = new Line(0, 0, 0, 0, Color.YELLOW, lindId);
//            changes.add(new GraphChange(null, null, line));
//
//            inOrder(node.right, changes);
//        }
//    }

//    public GraphChanges inorder() {
//        GraphChanges graphChanges = new GraphChanges();
//        List<GraphChange> changes = new ArrayList<>();
//        inOrder(this.root, changes);
//        graphChanges.setChanges(changes);
////        System.out.println(changes);
//        return graphChanges;
//    }

    private void inOrder(Node node, List<Tree> frames) {
        if (node == null) {
            return;
        }
        // 经过
        Tree tree = new Tree(frames.get(frames.size() - 1));
        int circleId = Integer.parseInt(node.circle.getId().substring(1));
        tree.getVertexGroup().get(circleId - 1).setStroke(Color.ORANGE);
        tree.getVertexGroup().get(circleId - 1).setFill(Color.WHITE);
        tree.getVertexTextGroup().get(circleId - 1).setStroke(Color.ORANGE);
        frames.add(tree);

        if (node.left != null) {
            tree = new Tree(frames.get(frames.size() - 1));
            int lineId = Integer.parseInt(node.left.circle.getId().substring(1)) - 1;
            tree.getEdgeGroup().get(lineId - 1).setStroke(Color.ORANGE);
            frames.add(tree);

            inOrder(node.left, frames);
        }

        // 访问
        tree = new Tree(frames.get(frames.size() - 1));
        circleId = Integer.parseInt(node.circle.getId().substring(1));
        tree.getVertexGroup().get(circleId - 1).setFill(Color.ORANGE);
        tree.getVertexTextGroup().get(circleId - 1).setStroke(Color.WHITE);
        frames.add(tree);

        if (node.right != null) {
            tree = new Tree(frames.get(frames.size() - 1));
            int lineId = Integer.parseInt(node.right.circle.getId().substring(1)) - 1;
            tree.getEdgeGroup().get(lineId - 1).setStroke(Color.ORANGE);
            frames.add(tree);

            inOrder(node.right, frames);
        }
    }

    public TreeFrame inorder() {
        TreeFrame treeFrame = new TreeFrame();
        List<Tree> frames = new ArrayList<>();
        frames.add(initTree);
        inOrder(this.root, frames);
        System.out.println(frames);
        treeFrame.setFrames(frames);
        return treeFrame;
    }

    private void preOrder(Node node, List<Tree> frames) {
        if (node == null) {
            return;
        }
        Tree tree = new Tree(frames.get(frames.size() - 1));
        int circleId = Integer.parseInt(node.circle.getId().substring(1));
        tree.getVertexGroup().get(circleId - 1).setFill(Color.ORANGE);
        tree.getVertexTextGroup().get(circleId - 1).setStroke(Color.RED);
        frames.add(tree);

        if (node.left != null) {
            tree = new Tree(frames.get(frames.size() - 1));
            // 叶节点id - 1 = 此节点与父相连边id
            int lineId = Integer.parseInt(node.left.circle.getId().substring(1)) - 1;
            tree.getEdgeGroup().get(lineId - 1).setStroke(Color.ORANGE);
            frames.add(tree);

            preOrder(node.left, frames);
        }
        if (node.right != null) {
            tree = new Tree(frames.get(frames.size() - 1));
            // 叶节点id - 1 = 此节点与父相连边id
            int lineId = Integer.parseInt(node.right.circle.getId().substring(1)) - 1;
            tree.getEdgeGroup().get(lineId - 1).setStroke(Color.ORANGE);
            frames.add(tree);

            preOrder(node.right, frames);
        }
        tree = new Tree(frames.get(frames.size() - 1));
        circleId = Integer.parseInt(node.circle.getId().substring(1));
//        tree.getVertexGroup().get(circleId - 1).setStroke(Color.BLUE);
        tree.getVertexTextGroup().get(circleId - 1).setStroke(Color.BLACK);
        tree.getVertexTextGroup().get(circleId - 1).setText(
                tree.getVertexTextGroup().get(circleId - 1).getText() + " 回溯"
        );
        frames.add(tree);

    }

    public TreeFrame preorder() {
        TreeFrame treeFrame = new TreeFrame();
        List<Tree> frames = new ArrayList<>();
        frames.add(initTree);
        preOrder(this.root, frames);
        System.out.println(frames);
        treeFrame.setFrames(frames);
        return treeFrame;
    }

    private Node delete(Node node, int data) {
        if (node == null) {
            System.out.println("No such data present in BST.");
        } else if (node.data > data) {
            node.left = delete(node.left, data);
        } else if (node.data < data) {
            node.right = delete(node.right, data);
        } else {
            if (node.right == null && node.left == null) { // If it is leaf node
                node = null;
            } else if (node.left == null) { // If only right node is present
                Node temp = node.right;
                node.right = null;
                node = temp;
            } else if (node.right == null) { // Only left node is present
                Node temp = node.left;
                node.left = null;
                node = temp;
            } else { // both child are present
                Node temp = node.right;
                // Find leftmost child of right subtree
                while (temp.left != null) {
                    temp = temp.left;
                }
                node.data = temp.data;
                node.right = delete(node.right, temp.data);
            }
        }
        return node;
    }


    private Node insert(Node node, int data) {
        if (node == null) {
            node = new Node(data);
        } else if (node.data > data) {
            node.left = insert(node.left, data);
        } else if (node.data < data) {
            node.right = insert(node.right, data);
        }
        return node;
    }

    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        if (node.left != null) {
            postOrder(node.left);
        }
        if (node.right != null) {
            postOrder(node.right);
        }
        System.out.print(node.data + " ");
    }

    public void add(int data) {
        this.root = insert(this.root, data);
    }

    public void remove(int data) {
        this.root = delete(this.root, data);
    }

    public void postorder() {
        System.out.println("Postorder traversal of this tree is:");
        postOrder(this.root);
        System.out.println(); // for next li
    }

    public boolean find(int data) {
        if (search(this.root, data, null)) {
            System.out.println(data + " is present in given BST.");
            return true;
        }
        System.out.println(data + " not found.");
        Node nn;
        return false;
    }
}

五. 可视化核心逻辑实现

3.1 D3.js

D3 (或D3.js) 是一个用来使用Web标准做数据可视化的JavaScript库。 D3帮助我们使用SVG, Canvas 和 HTML技术让数据生动有趣。 D3将强大的可视化，动态交互和数据驱动的DOM操作方法完美结合，让我们可以充分发挥现代浏览器的功能，自由的设计正确的可视化界面。

D3 的全称是（Data-Driven Documents），顾名思义可以知道是一个被数据驱动的文档。听名字有点抽象，说简单一点，其实就是一个 JavaScript 的函数库，使用它主要是用来做数据可视化的。可以帮助你使用 HTML, CSS, SVG 以及 Canvas 来展示数据。D3 遵循现有的 Web 标准，可以不需要其他任何框架独立运行在现代浏览器中，它结合强大的可视化组件来驱动 DOM 操作。

JavaScript 文件的后缀名通常为 .js，故 D3 也常使用 D3.js 称呼。D3 提供了各种简单易用的函数，大大简化了 JavaScript 操作数据的难度。由于它本质上是 JavaScript ，所以用 JavaScript 也是可以实现所有功能的，但它能大大减小你的工作量，尤其是在数据可视化方面，D3 已经将生成可视化的复杂步骤精简到了几个简单的函数，你只需要输入几个简单的数据，就能够转换为各种绚丽的图形。有过 JavaScript 基础的朋友一定很容易理解它。

首先通过 D3.js 将数据绑定到 DOM 上，根据数据计算对应的 DOM 的属性值。
其次借助于现有的 Web 元素: HTML, CSS, SVG 等。使用 D3 创建 SVG 元素，并使用外部样式表进行样式化。

3.2 DOM 的相关操作（这里使用选择排序作为示例）

1. DOM 操作思路

   

2. DOM 的单帧分解

下面来设想一下排序过程中所涉及到的每一帧是以什么样的样式出现。可以回看上面的几个视频，思考过程是这样，把整个排序过程分解，每一步也就对应了我们后来的每一帧。

想象我需要实现的效果：

arr[0] 高亮
arr[1] 高亮
if (arr[min] > arr[1])
true : arr[1] 标记为最小值
false : arr[1] 取消高亮
arr[2] 高亮
……循环

上面的过程中，为了区分不同类型的数，思考一下有哪些状态：

select: 待交换，每轮外循环所选定的值

on: 正在比较中，即每轮内循环依次遍历的值

min: 内循环的目的是找到此轮的最小值，所以每次比较都会产生当前的最小值，需要区分

sorted: 已完成排序，每轮内循环结束并完成交换后，当前外循环选定的值已完成排序

将以上几种状态对应到不同的 CSS 样式，之后渲染的时候只需要通过操作样式表即可实现不同状态的标识：

function renderSelectionDiv(main, div, state, on){
   var onDiv = document.getElementById(div.toString());
   if(on == 1){
      if (state == ""){
         var outerDiv = document.getElementById(main.toString());
         swap(outerDiv, onDiv);
      }else{
         onDiv.classList.add(state);
      }
   }else {
      onDiv.classList.remove(state);
   }
}

对 Array 进行排序分解

之所以先写上面的部分，是为了便于理解。实际过程中，我是先从排序时的循环过程开始尝试，然后思考每帧需要的数据，之后再回过头来修正这一部分中的数据格式。

考虑排序过程中的两层循环，重点注意下标的变化过程：

外循环是从 0 → 数组倒数第二位

内循环是从 此轮外循环的值 → 数组最后一位。

理解循环的过程不难，较为繁琐的是理清每一步所需的操作是什么，将上一部分中所设想的样式变换插入到排序的循环中，下面是我的代码：

function getMin(outerId, innerQueue, timerQueue){
   var outerDiv = data[outerId];
   var minId = outerId;
   timerQueue.push([outerId, outerId, "select", 1]);

   while(innerQueue.length > 0){
      var innerId = innerQueue.shift();
      var minDiv = data[minId];
      var innerDiv = data[innerId];
      timerQueue.push([outerId, innerId, "on", 1]);
      if(minDiv > innerDiv){
         timerQueue.push([outerId, minId, "min", 0]);
         timerQueue.push([outerId, minId, "on", 0]);

         minId = innerId;

         timerQueue.push([outerId, minId, "min", 1]);

      }else {
         timerQueue.push([outerId, innerId, "on", 0]);
      }
   }

   timerQueue.push([outerId, minId, "", 1]);
   swapData(outerId, minId);

   timerQueue.push([outerId, minId, "min", 0]);
   timerQueue.push([outerId, minId, "on", 0]);
   timerQueue.push([outerId, outerId, "sort", 1]);
   timerQueue.push([outerId, outerId, "select", 0]);
   timerQueue.push([outerId, outerId, "min", 0]);

   return timerQueue;
}

总结：

这里很简单，但忍不住想要打一个比喻。

想象我们在为电影写剧本，需要提前写好每个镜头所涉及到的演员和表演场景，演员安排即是 Array 操作部分进行管理，而具体的场景则是 DOM 操作部分。

写好剧本之后，交给 D3.js ，它将按照剧本的要求，召集人员进行拍摄，然后提供给浏览器播放出来。

六. 数据测试

6.1 二叉树生成测试

6.2 中序遍历测试

6.3 查找 N 测试

七. UI 设计

由于这只是学校一个作业，直接使用了 BootStrap 的 UI 模板，界面使用了 SpringBoot 原生的 Thymleaf 模板引擎，按理来说本来应该用 Vue 或者 Rect 啥的，但是太麻烦了我懒得弄，由于只是做一个展示，开源到 github 上，并不会部署上线，所以做的也就比较随意。

index.html（首页）

<!doctype html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <meta name="description" content="">
    <meta name="author" content="">
    <!-- Logo 图标设置 -->
    <link rel="icon" href="https://fastly.jsdelivr.net/npm/@bootcss/v3.bootcss.com@1.0.36/favicon.ico">
    <link rel="canonical" href="https://getbootstrap.com/docs/3.4/examples/carousel/">

    <title>AJVisual 一个算法可视化网站</title>
    <link href="https://fastly.jsdelivr.net/npm/@bootcss/v3.bootcss.com@1.0.36/dist/css/bootstrap.min.css" rel="stylesheet">
    <link href="https://fastly.jsdelivr.net/npm/@bootcss/v3.bootcss.com@1.0.36/assets/css/ie10-viewport-bug-workaround.css" rel="stylesheet">
    <script src="https://fastly.jsdelivr.net/npm/@bootcss/v3.bootcss.com@1.0.36/assets/js/ie8-responsive-file-warning.js"></script><![endif]-->
    <script src="https://fastly.jsdelivr.net/npm/@bootcss/v3.bootcss.com@1.0.36/assets/js/ie-emulation-modes-warning.js"></script>
    <script src="https://oss.maxcdn.com/html5shiv/3.7.3/html5shiv.min.js"></script>
    <script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
    <link href="https://fastly.jsdelivr.net/npm/@bootcss/v3.bootcss.com@1.0.36/examples/carousel/carousel.css" rel="stylesheet">
</head>
<!-- NAVBAR
================================================== -->
<body>
<div class="navbar-wrapper">
    <div class="container">
        <nav class="navbar navbar-inverse navbar-static-top">
            <div class="container">
                <div class="navbar-header">
                    <button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target="#navbar" aria-expanded="false" aria-controls="navbar">
                        <span class="sr-only">Toggle navigation</span>
                        <span class="icon-bar"></span>
                        <span class="icon-bar"></span>
                        <span class="icon-bar"></span>
                    </button>
                    <a class="navbar-brand" href="http://localhost:8080/">AJVisual</a>
                </div>
                <div id="navbar" class="navbar-collapse collapse">
                    <ul class="nav navbar-nav">
                        <li class="active"><a href="http://localhost:8080/">主页</a></li>
                        <li><a href="http://alexjoker.top/about/">关于我</a></li>
                        <li class="dropdown">
                            <a href="#" class="dropdown-toggle" data-toggle="dropdown" role="button" aria-haspopup="true" aria-expanded="false">可视化<span class="caret"></span></a>
                            <ul class="dropdown-menu">
                                <li><a href="http://localhost:8080/sort">选择排序</a></li>
                                <li><a href="http://localhost:8080/btree">二叉树</a></li>
                                <li><a href="http://localhost:8080/graph">迷宫BFS/DFS搜索</a></li>
                            </ul>
                        </li>
                    </ul>
                </div>
            </div>
        </nav>
    </div>
</div>


<!-- Carousel
================================================== -->
<div id="myCarousel" class="carousel slide" data-ride="carousel">
    <ol class="carousel-indicators">
        <li data-target="#myCarousel" data-slide-to="0" class="active"></li>
        <li data-target="#myCarousel" data-slide-to="1"></li>
        <li data-target="#myCarousel" data-slide-to="2"></li>
    </ol>
    <div class="carousel-inner" role="listbox">
        <div class="item active">
            <a href="">
            <img class="first-slide" src="https://alexjoker-blog.oss-cn-guangzhou.aliyuncs.com/AJVisual/C03.png" alt="First slide">
            </a>
            <div class="container">
                <div class="carousel-caption">
                </div>
            </div>
        </div>
        <div class="item">
            <img class="second-slide" src="https://alexjoker-blog.oss-cn-guangzhou.aliyuncs.com/AJVisual/C01.png" alt="Second slide">
            <div class="container">
                <div class="carousel-caption">
                </div>
            </div>
        </div>
        <div class="item">
            <img class="third-slide" src="https://alexjoker-blog.oss-cn-guangzhou.aliyuncs.com/AJVisual/C02.png" alt="Third slide">
            <div class="container">
                <div class="carousel-caption">
                </div>
            </div>
        </div>
    </div>
    <a class="left carousel-control" href="#myCarousel" role="button" data-slide="prev">
        <span class="glyphicon glyphicon-chevron-left" aria-hidden="true"></span>
        <span class="sr-only">Previous</span>
    </a>
    <a class="right carousel-control" href="#myCarousel" role="button" data-slide="next">
        <span class="glyphicon glyphicon-chevron-right" aria-hidden="true"></span>
        <span class="sr-only">Next</span>
    </a>
</div><!-- /.carousel -->


<!-- Marketing messaging and featurettes
================================================== -->
<!-- Wrap the rest of the page in another container to center all the content. -->

<div class="container marketing">

    <!-- START THE FEATURETTES -->
    <hr class="featurette-divider">
    <div class="row featurette">
        <div class="col-md-7">
            <h2 class="featurette-heading">选择排序<span class="text-muted">（Selection sort）</span></h2>
            <p class="lead">选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。</p>
        </div>
        <div class="col-md-5">
            <a href="http://localhost:8080/sort">
                <img class="featurette-image img-responsive center-block" data-src="holder.js/500x500/auto" alt="Generic placeholder image" src="https://alexjoker-blog.oss-cn-guangzhou.aliyuncs.com/AJVisual/index01.png">
            </a>
        </div>
    </div>

    <hr class="featurette-divider">

    <div class="row featurette">
        <div class="col-md-7 col-md-push-5">
            <h2 class="featurette-heading">二叉树<span class="text-muted">（Binary tree）</span></h2>
            <p class="lead">二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分</p>
        </div>
        <div class="col-md-5 col-md-pull-7">
            <a href="http://localhost:8080/btree">
            <img class="featurette-image img-responsive center-block" data-src="holder.js/500x500/auto" alt="Generic placeholder image" src="https://alexjoker-blog.oss-cn-guangzhou.aliyuncs.com/AJVisual/index02.png">
            </a>
        </div>
    </div>

    <hr class="featurette-divider">

    <div class="row featurette">
        <div class="col-md-7">
            <h2 class="featurette-heading">图<span class="text-muted">（map）</span></h2>
            <p class="lead">图算法指利用特制的线条算图求得答案的一种简便算法。无向图、有向图和网络能运用很多常用的图算法，这些算法包括：各种遍历算法（这些遍历类似于树的遍历），寻找最短路径的算法，寻找网络中最低代价路径的算法，回答一些简单相关问题（例如，图是否是连通的，图中两个顶点间的最短路径是什么，等等）的算法。图算法可应用到多种场合，例如：优化管道、路由表、快递服务、通信网站等。</p>
        </div>
        <div class="col-md-5">
            <a href="http://localhost:8080/graph">
            <img class="featurette-image img-responsive center-block" data-src="holder.js/500x500/auto" alt="Generic placeholder image" src="https://alexjoker-blog.oss-cn-guangzhou.aliyuncs.com/AJVisual/index03.png">
            </a>
        </div>
    </div>

    <hr class="featurette-divider">

    <!-- /END THE FEATURETTES -->


    <!-- FOOTER -->
    <footer>
        <p class="pull-right"><a href="#">返回顶部</a></p>
        <p>&copy; 2022 Power By &middot; <a href="http://alexjoker.top/">清风摇翠</a></p>
    </footer>

</div>
<script src="https://fastly.jsdelivr.net/npm/jquery@1.12.4/dist/jquery.min.js" integrity="sha384-nvAa0+6Qg9clwYCGGPpDQLVpLNn0fRaROjHqs13t4Ggj3Ez50XnGQqc/r8MhnRDZ" crossorigin="anonymous"></script>
<script>window.jQuery || document.write('<script src="https://fastly.jsdelivr.net/npm/@bootcss/v3.bootcss.com@1.0.36/assets/js/vendor/jquery.min.js"><\/script>')</script>
<script src="https://fastly.jsdelivr.net/npm/@bootcss/v3.bootcss.com@1.0.36/dist/js/bootstrap.min.js"></script>
<!-- Just to make our placeholder images work. Don't actually copy the next line! -->
<script src="https://fastly.jsdelivr.net/npm/@bootcss/v3.bootcss.com@1.0.36/assets/js/vendor/holder.min.js"></script>
<!-- IE10 viewport hack for Surface/desktop Windows 8 bug -->
<script src="https://fastly.jsdelivr.net/npm/@bootcss/v3.bootcss.com@1.0.36/assets/js/ie10-viewport-bug-workaround.js"></script>
</body>
</html>

btree.html（二叉树展示界面）

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <script src="/js/3rdPart/d3.js"></script>
    <script src="/js/3rdPart/jquery-3.5.0.min.js"></script>
    <link rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.3.1/css/bootstrap.min.css">
    <style>
        div{
            margin-bottom: 5px;
        }
        #alg-sel{
            float: right;
        }
    </style>
</head>
<body>
    <div class="container">
        <header>
            <!-- Fixed navbar -->
            <nav class="navbar navbar-expand-md navbar-dark fixed-top bg-dark">
                <a class="navbar-brand" href="http://localhost:8080/">AJVisual</a>
                <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbarCollapse" aria-controls="navbarCollapse" aria-expanded="false" aria-label="Toggle navigation">
                    <span class="navbar-toggler-icon"></span>
                </button>
                <div class="collapse navbar-collapse" id="navbarCollapse">
                    <ul class="navbar-nav mr-auto">
                        <li class="nav-item">
                            <a class="nav-link" href="http://localhost:8080/">主页<span class="sr-only">(current)</span></a>
                        </li>
                        <li class="nav-item">
                            <a class="nav-link" href="http://localhost:8080/sort">选择排序</a>
                        </li>
                        <li class="nav-item">
                            <a class="nav-link active" href="http://localhost:8080/btree">二叉树</a>
                        </li>
                        <li class="nav-item">
                            <a class="nav-link" href="http://localhost:8080/graph">迷宫BFS/DFS搜索</a>
                        </li>
                    </ul>
                    <form class="form-inline mt-2 mt-md-0">
                        <input class="form-control mr-sm-2" type="text" placeholder="Search" aria-label="Search">
                        <button class="btn btn-outline-success my-2 my-sm-0" type="submit">搜索</button>
                    </form>
                </div>
            </nav>
        </header>

        <div id="set" style="margin-top: 80px">
            <span class="badge badge-info">在此输入你想要测试的数据</span>
            <input id="input" type="text" class="form-control" value="84, 24, 57, 87, 13, 9, 56" size="30">
            <button id="create" type="button" class="btn btn-secondary btn-sm" style="margin-top: 15px; margin-left: 340px">创建二叉排序树</button>
            <button id="inorder" type="button" class="btn btn-secondary btn-sm" style="margin-top: 15px">中序遍历</button>
            <button id="preorder" type="button" class="btn btn-secondary btn-sm" style="margin-top: 15px">前序遍历</button>

            <div class="form-group">
            <button id="search" type="button" class="btn btn-info btn-sm">查找N</button>
            <input id="num" type="number" class="form-control">
            </div>
        </div>
    </div>
    <div class="show" style="text-align: center">
    <svg></svg>
    </div>

    <div id="control" class="btn-group" role="group" aria-label="Basic outlined example">
        <button id="preFrame" class="btn btn-primary btn-sm" style="margin-left: 660px"> Back </button>
        <button id="pause" class="btn btn btn-success btn-sm"> 暂停 </button>
        <button id="play" class="btn btn btn-success btn-sm"> 继续 </button>
        <button id="nextFrame" class="btn btn btn-success btn-sm"> continue </button>
        <button id="clearing" class="btn btn btn-success btn-sm"> 复原 </button>
        <button class="btn btn-primary disabled">x</button>
        <button id="speed2" class="btn btn-info btn-sm">0.5</button>
        <button id="speed3" class="btn btn-info btn-sm">1</button>
        <button id="speed4" class="btn btn-info btn-sm">2</button>
        <button id="speed5" class="btn btn-info btn-sm">4</button>
    </div>
    

    <script src="/js/common.js"></script>
    <script src="/js/btree.js"></script>
</body>
</html>

网站展示

首页:

二叉树界面展示：