基于TypeScriptX+node.js+Html的二叉树、社会关系网络实现

红太狼 2024-03-27 11:29 7阅读 0赞

第一部分 算法实现设计说明 4  
1.1题目 4  
1.2软件功能 4  
1.3设计思想 5  
1.4逻辑结构与物理结构 6  
1.5开发平台 6  
1.5.1代码编写与测试 6  
1.5.2代码托管、流水线构建与部署 6  
1.6系统的运行结果分析说明 7  
1.6.1开发与调试过程 7  
1.6.2代码管理与流水线部署 7  
1.6.3运行结果分析 8  
1.7操作说明 10  
第二部分 综合应用设计说明 12  
2.1 题目 12  
2.2软件功能 13  
2.3设计思想 14  
2.4逻辑结构与物理结构 15  
2.5开发平台 15  
2.5.1代码编写与测试 15  
2.5.2代码托管、流水线构建与部署 16  
2.6系统的运行结果分析说明 16  
2.6.1开发与调试过程 16  
2.6.2代码管理与流水线部署 17  
2.6.3运行结果分析 17  
2.7操作说明 20  
第三部分 实践总结 24  
3.1所做的工作 24  
3.2总结与收获 24  
第四部分 参考文献 24

软件中心拥有一个画板，用于展示二叉树节点、线索，及播放遍历动画。该画板基于  
HTML Canvas 制作完成，封装成 React 节点模块。

同时，软件界面包含多个功能按钮，供用户选择线索化方式，或选择不进行线索化。允许用户主动要求统计叶节点，展示叶节点位置，以及播放以自选遍历方式进行的二叉树

遍历过程动画。该部分基于 Ant Design 制作，内嵌画板模块，封装成 React 节点模块，并作为程序主页呈现。  
软件构建目标为 web 应用，理论上可以运行于任何带有浏览器的环境（已在  
Chromium、Gecko 和 WebKit 环境完成测试，不保证在 Trident 和 EdgeHTML 等其他环境的效果）。界面采用中国风配色 2，清新舒适。  
1.3设计思想

树结构由多个节点链接形成。节点结构包含父节点指针、左孩子指针、右孩子指针、前驱指针、后继指针 1。其中，前驱指针仅当左孩子为空时启用。后继指针同理。以该方式取代经典的标签模式，可以在不添加额外内存空间的情况下增强结构的可读性。为简化点击检测，为每个节点加入单独的 data 对象，本质为映射，供调用者存储需要的内容。  
为满足与用户交互，程序需要有一个主页面，由“主页控制器”模块完成。该模块负责 接收用户的按钮事件等，做出相应处理。  
为展示树，采用“绘画画板”模块完成树的绘制与动画演示。该模块基于 HTML Canvas  
制作，具有很高的渲染效率。同时，该模块登记树根节点的指针（语言层面体现为引用），由根节点可以访问到树上的所有节点。  
用户在页面上的操作或由主页模块直接处理，或由绘画模块直接处理，也有多个模块共同处理。处理过程带有较强的容错机制，对危险操作带有锁机制做保护，防止用户的部分操作对系统结构带来破坏。  
画板绘制二叉树前，先从根节点出发，构建一个辅助结构，称为“平树”。平树是一个 节点指针数组的数组，每个子数组表示树上的一层。根据平树的高度以及最大子数组的元素大小，结合画板宽高尺寸，即可动态得到一个适宜的节点半径，令节点在画面上看起来更加舒适。同时，此结构可以帮助快速计算每个节点在画板上的位置，更轻松地完成图像绘制。绘制时，在节点内的 data 对象中记录该节点在画板上的坐标。鼠标点击事件到来时，根据勾股定理寻找鼠标所处的节点对象。同时，每次点击会和上次鼠标事件的位置做综合计算，使得鼠标按下后可能出现的短距离误滑动不会干扰节点识别。  
动画播放启动后，会设定“动画锁”。每次可能造成二叉树重绘的人为操作到来时，会 对锁进行检查。如果处于锁定状态，则打断动画，并弹出警告提示信息。为有效打断处于协程内的动画过程，设置“动画编号”信息。动画开始时，将当前编号存储。动画播放时， 若检测到存储的编号与全局编号有差异，则立即停止动画。如此，只需改变动画编号，就能实现打断协程内的动画，不与当前操作产生冲突。

通过节点高亮和停顿实现动画效果。高亮与解除高亮即为重新绘制 4。延迟使用标准的 setTimeout 函数，配合协程的 async 和 await 实现。

import React, {
         CSSProperties } from 'react'
    import * as echarts from 'echarts'
    import {
         NodeBase, NodeTag } from '../data-structure/NodeBase'
    import {
         FreeKeyObject } from '../data-structure/FreeKeyObject'
    
    export interface RelationChartProps {
        
        style?: CSSProperties
    }
    
    export class RelationChart extends React.Component<RelationChartProps> {
        
        /** 指向自己（React 节点对象）的引用。 */
        private selfRef: React.RefObject<HTMLDivElement>
    
        /** echarts 配置对象。 */
        private chart!: echarts.ECharts
    
    
        /**
         * 构造。
         */
        constructor(props: any) {
        
            super(props)
            this.selfRef = React.createRef()
    
            // 绑定函数。
            this.showGlobalRelationGraph = this.showGlobalRelationGraph.bind(this)
            this.showPersonRelationGraph = this.showPersonRelationGraph.bind(this)
        }
    
        /**
         * 渲染。
         */
        override render() {
         // public
            return <div 
                ref={
        this.selfRef}
                style={
        this.props.style}
            />
        }
    
        override componentDidMount() {
        
            this.chart = echarts.init(this.selfRef.current!)
        }
    
        private nodeTagToHumanReadableString(tag: NodeTag) {
        
            switch (tag) {
        
                case NodeTag.GROUP:
                    return '群组'
                case NodeTag.PERSON:
                    return '个人'
                case NodeTag.NUL:
                    return '未知'
                case NodeTag.PRIMARY_SCHOOL:
                    return '小学'
                case NodeTag.JUNIOR_HIGH:
                    return '初中'
                case NodeTag.SENIOR_HIGH:
                    return '高中'
                case NodeTag.UNIVERSITY:
                    return '大学'
            }
        }
    
        /**
         * 展示全局关系图。
         */
        showGlobalRelationGraph(nodes: Array<NodeBase>) {
        
            this.setState({
        
                visibility: 'visible'
            })
    
            // 生成图表参数。
    
            let data = new Array<FreeKeyObject>()
            let links = new Array<FreeKeyObject>()
            let chartIdMap = new Map<NodeBase, number>()
            let nodeCount = 0
    
            // 添加点。
            nodes.forEach(node => {
        
                chartIdMap.set(node, nodeCount++)
                data.push({
        
                    name: nodeCount - 1,
                    value: node.name,
                    id: nodeCount - 1,
                    category: this.nodeTagToHumanReadableString(node.tag),
                    draggable: true,
                })
            })
    
            // 添加关联关系。
            nodes.forEach(first => {
        
                let firstChartId = chartIdMap.get(first)
                first.relations.forEach(second => {
        
                    if (first.id < second.id) {
        
                        links.push({
        
                            source: firstChartId,
                            target: chartIdMap.get(second)
                        })
                    }
                })
            })
            
            this.chart.clear()
            this.chart.setOption({
        
    
                // 标题。
                title: {
        
                    text: '全局关系图',
                    top: 'bottom',
                    left: 'right'
                },
    
                // 鼠标覆盖显示内容。
                tooltip: {
        
                    trigger: 'item',
                    formatter: '{
        c}'
                },
    
                legend: {
        
                    x: 'center',
                    show: 'true',
                },
            
                series: [{
        
                    type: 'graph',
                    layout: 'force',
                    symbolSize: 45,
                    focusNodeAdjacency: true,
                    roam: true,
    
                    // 配色表。
                    categories: [{
        
                        name: this.nodeTagToHumanReadableString(NodeTag.PERSON),
                        itemStyle: {
        
                            color: "#894276",
                            
                        }
                    },{
        
                        name: this.nodeTagToHumanReadableString(NodeTag.GROUP),
                        itemStyle: {
        
                            color: "#66a9c9",
                        }
                    }, {
        
                        name: this.nodeTagToHumanReadableString(NodeTag.PRIMARY_SCHOOL),
                        itemStyle: {
        
                            color: "#20a162",
                        }
                    },{
        
                        name: this.nodeTagToHumanReadableString(NodeTag.JUNIOR_HIGH),
                        itemStyle: {
        
                            color: "#bec936",
                            
                        }
                    },{
        
                        name: this.nodeTagToHumanReadableString(NodeTag.SENIOR_HIGH),
                        itemStyle: {
        
                            color: "#fca104",
                        }
                    },{
        
                        name: this.nodeTagToHumanReadableString(NodeTag.UNIVERSITY),
                        itemStyle: {
        
                            color: "#cf4813",
                        }
                    },],
                    force: {
        
                        repulsion: 1400
                    },
    
                    data: data,
    
                    label: {
        
                        show: true,
                        position: 'right',
                        formatter: '{
        c}'
                    },
    
                    links: links,
    
                    lineStyle: {
        
                        opacity: 0.9,
                        width: 1,
                        curveness: 0
                    },
    
    
                }]
            })
        }
    
    
        /**
         * 展示单人社交网络图。
         */
        showPersonRelationGraph(node: NodeBase = new NodeBase('')) {
        
            this.setState({
        
                visibility: 'visible'
            })
    
            // 生成图表参数。
    
            let data = new Array<FreeKeyObject>()
            let links = new Array<FreeKeyObject>()
            let chartIdMap = new Map<NodeBase, number>()
            let nodeCount = 0
    
            // 中心点。
            chartIdMap.set(node, nodeCount++)
            data.push({
        
                name: 0,
                id: 0,
                value: node.name,
                category: '中心',
                draggable: true,
            })
    
            let firstClassRelationList = new Array<NodeBase>()
    
            // 一级关系。
            node.relations.forEach(next => {
        
                data.push({
        
                    name: nodeCount,
                    id: nodeCount,
                    value: next.name,
                    category: next.tag == NodeTag.PERSON ? '一级好友' : '一级组织',
                    draggable: true
                })
                
                chartIdMap.set(next, nodeCount++)
                links.push({
        
                    source: 0,
                    target: nodeCount - 1
                })
    
                firstClassRelationList.push(next)
            })
    
            // 二级关系。
            firstClassRelationList.forEach(firstClassNode => {
        
                let firstNodeChartId = chartIdMap.get(firstClassNode)
                firstClassNode.relations.forEach(secondClassNode => {
        
                    if (!chartIdMap.has(secondClassNode)) {
        
                        chartIdMap.set(secondClassNode, nodeCount++)
    
                        data.push({
        
                            id: nodeCount - 1,
                            name: nodeCount - 1,
                            value: secondClassNode.name,
                            category: secondClassNode.tag == NodeTag.PERSON ? 
                                '二级好友' : '二级组织',
                            draggable: true
                        })
                        
                        links.push({
        
                            source: firstNodeChartId,
                            target: nodeCount - 1
                        })
                    }
                })
            })
    
            this.chart.clear()
            this.chart.setOption({
        
    
                // 标题。
                title: {
        
                    text: node.name + '的关系放射',
                    top: 'bottom',
                    left: 'right'
                },
    
                // 鼠标覆盖显示内容。
                tooltip: {
        
                    trigger: 'item',
                    formatter: '{
        c}'
                },
    
                legend: {
        
                    x: 'center',
                    show: true
                },
    
                series: [{
        
                    type: 'graph',
                    layout: 'force',
                    symbolSize: 45,
                    focusNodeAdjacency: true,
                    roam: true,
    
                    // 配色表。
                    categories: [{
        
                        name: '中心',
                        itemStyle: {
        
                            color: "#c21f30",
                            
                        }
                    },{
        
                        name: '一级组织',
                        itemStyle: {
        
                            color: "#2f90b9",
                            
                        }
                    }, {
        
                        name: '二级组织',
                        itemStyle: {
        
                            color: "#9a8878",
                            
                        }
                    }, {
        
                        name: '一级好友',
                        itemStyle: {
        
                            color: "#813c85",
                            
                        }
                    }, {
        
                        name: '二级好友',
                        itemStyle: {
        
                            color: "#bacf65",
                            
                        }
                    }],
                    force: {
        
                        repulsion: 1400
                    },
    
                    data: data,
    
                    label: {
        
                        show: true,
                        position: 'right',
                        formatter: '{
        c}'
                    },
    
                    links: links,
    
                    lineStyle: {
        
                        opacity: 0.9,
                        width: 1,
                        curveness: 0
                        
                    },
    
    
                }]
    
    
            })
    
        }
    }

![在这里插入图片描述][82cfb31baaea4ce4808f90dddc3f82cb.png_pic_center]  
![在这里插入图片描述][a2e14f328e8345a086ed7218ccc1d9ad.png_pic_center]  
![在这里插入图片描述][11d78560e1af47b3a33f7ca0ec824cf9.png_pic_center]  
![在这里插入图片描述][d9ddf0b5bb05476498b097b0ae12ea2e.png_pic_center]  
![在这里插入图片描述][58ce86a811814913bb4983ceb40f1fa6.png_pic_center]  
![在这里插入图片描述][f34a2582001b4ea09039649d27b0ab6d.png_pic_center]  
![在这里插入图片描述][d37775a877ca43659f0a46c0f3f992db.png_pic_center]  
![在这里插入图片描述][2985c4e2e0d7466b93dd7213a009d783.png_pic_center]  
![在这里插入图片描述][8fdaca98ff3b4f688d8f7d759fa12758.png_pic_center]  
![在这里插入图片描述][8bf4a8be82fc4c92a3fa6548c1fc2897.png_pic_center]  
![在这里插入图片描述][56526b209f5c4ca198fb17f89972fefc.png_pic_center]  
![在这里插入图片描述][ae17414a01244d1797fe21da4e80bfc3.png_pic_center]  
![在这里插入图片描述][993f511833654626a34ec8a342ef91cd.png_pic_center]  
![在这里插入图片描述][d1eb7a05cd474a489cb8f227da2c37a3.png_pic_center]  
![在这里插入图片描述][9e4e39c71ae54b86a4601ee0579f5610.png_pic_center]  
![在这里插入图片描述][c4a96852f4b44e4ebdb30618dfdebead.png_pic_center]  
![在这里插入图片描述][76d59fb418014667a1b9d9bea2f95735.png_pic_center]  
![在这里插入图片描述][627a00be21fe426f99def11f152d5e41.png_pic_center]  
![在这里插入图片描述][0bc5257e57a04afaa6fcb032d92cd3ac.png_pic_center]  
![在这里插入图片描述][235b0238ef0d4a8794a788123b6a2859.png_pic_center]  
![在这里插入图片描述][17c0495d84644c23a316f6fb0c351750.png_pic_center]  
![在这里插入图片描述][cc7a7d8d2a9446488cf71aee164f3edd.png_pic_center]  
![在这里插入图片描述][f5346612523a4f6fab1d860f94ba8b69.png_pic_center]  
![在这里插入图片描述][04e30ae21f884e59bbcb45a7423f5dd7.png_pic_center]  
![在这里插入图片描述][866e07839a304355a7ff79552a6bc90a.png_pic_center]  
![在这里插入图片描述][7fed2bb07acd48a6bb107ba416bc2112.png_pic_center]  
![在这里插入图片描述][34d0b5013b4b427197303f9f57cc169e.png_pic_center]  
![在这里插入图片描述][b9a001d9b003440da768b78511a4210e.png_pic_center]

[82cfb31baaea4ce4808f90dddc3f82cb.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/790d186a52d94721a3ecb1d1bc63f3b8.png
[a2e14f328e8345a086ed7218ccc1d9ad.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/7ab0743176b445538b0e8e9607e9a75d.png
[11d78560e1af47b3a33f7ca0ec824cf9.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/59462056c0334acfa6c879b61b5466b4.png
[d9ddf0b5bb05476498b097b0ae12ea2e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/4e373fff4e9745d59f6a7ee2d4cafa46.png
[58ce86a811814913bb4983ceb40f1fa6.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/13d5a0795af845ef95e28b2b23331a86.png
[f34a2582001b4ea09039649d27b0ab6d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/9dbc8e97063b4d979c8f459aabd1f7e1.png
[d37775a877ca43659f0a46c0f3f992db.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/220eed93f8bc4299b600523fd9056706.png
[2985c4e2e0d7466b93dd7213a009d783.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/4af735f022224d0fa00db7b0001d60da.png
[8fdaca98ff3b4f688d8f7d759fa12758.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/5aafd8bd45f44b77ad7d5d31240c3b2b.png
[8bf4a8be82fc4c92a3fa6548c1fc2897.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/f2ddebbd2bc54280868a3884b44531e4.png
[56526b209f5c4ca198fb17f89972fefc.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e728ba638b824627b73306e314dae8ba.png
[ae17414a01244d1797fe21da4e80bfc3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/17ec3f2c3069449e8f84b20dd3a9d0fe.png
[993f511833654626a34ec8a342ef91cd.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/9db0a49806b243cc9d22eaebf8418859.png
[d1eb7a05cd474a489cb8f227da2c37a3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/da93dd51c6df47a982a41309f55f8951.png
[9e4e39c71ae54b86a4601ee0579f5610.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/63a48d4d635e448bb6833a56a4989bf6.png
[c4a96852f4b44e4ebdb30618dfdebead.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ca6855d2e869447791609dbe30590243.png
[76d59fb418014667a1b9d9bea2f95735.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/d478849b6108438283808c6bb004e5a0.png
[627a00be21fe426f99def11f152d5e41.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/55da62a8f9844ac38d66e79c38878455.png
[0bc5257e57a04afaa6fcb032d92cd3ac.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/6548c1a4af914179b40eb05fb1b35150.png
[235b0238ef0d4a8794a788123b6a2859.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/da7f150f8db946eeaf8f18e34f659f74.png
[17c0495d84644c23a316f6fb0c351750.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/3480c8b7e3b24c948298ef7506254861.png
[cc7a7d8d2a9446488cf71aee164f3edd.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/3d1471eb92c94c498fd7c9e615b67ec6.png
[f5346612523a4f6fab1d860f94ba8b69.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/55052662bbdd4e6a89972d2a5577e0aa.png
[04e30ae21f884e59bbcb45a7423f5dd7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/376311b676314b1ba52659f1812cb1de.png
[866e07839a304355a7ff79552a6bc90a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/a5d620edb7884e3cab12cab68ffd9503.png
[7fed2bb07acd48a6bb107ba416bc2112.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/0bbff507463c434ca8bd7dd4e6c8104e.png
[34d0b5013b4b427197303f9f57cc169e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/4751ee5275d749019dbfa1358d1a38cf.png
[b9a001d9b003440da768b78511a4210e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/744189e7a566422eae2aeaf0cd459421.png