JavaScript에서 두 갈래 트리 그리기

컴퓨터 과학의 트리는 컴퓨터 과학 분야에서 광범위하게 응용되는 데이터 구조로 뿌리, 하위 트리와 부모 노드가 있어 하나의 연결 노드를 나타낸다.이러한 데이터 구조는 광범위한 용례를 가진다. 트리는 다른 데이터 구조(예를 들어 지도와 집합)의 기초이다. 그 밖에 트리의 사용은 데이터베이스에서 HTML DOM 차원 구조를 신속하게 검색하고 표시하는 뚜렷한 예가 있다.서로 다른 유형의 트리가 있지만 본고에서 우리는 캔버스와 자바스크립트를 사용하여 두 갈래 트리를 실현하고 그릴 것이다.

무엇이 두 갈래 나무입니까?

두 갈래 나무는 일종의 데이터 구조로 뿌리라고 불리는 꼭대기 노드에서 시작하여 그 자수(자수)와 분지되어 마지막에 잎이라고 불리는 노드에서 끝난다.각 노드는 최대 두 개의 하위 노드, 왼쪽과 오른쪽이 있을 수 있다.이 노드가 아무런 인용도 없는 상황에서 이것은 하위 노드가 없다는 것을 의미하며 잎이나 외부 노드라고 부른다.

두 갈래 트리 데이터 구조를 실현하다

이전 블로그에서 두 갈래 트리는 데이터 구조라는 것을 깨달았습니다. 그 중에서 각 노드는 하나의 값과 두 개의 자나 자대를 가리키는 바늘(링크)이 있고 다음은 하나의 노드의 실현입니다.
주: 독자가 트리 데이터 구조를 이해한다고 가정하면 그 실현에 대한 해석은 더 이상 깊이 들어가지 않을 것이다.

const LEFT = 0
const RIGHT = 1

class Node {
    constructor(value) {
        this.value = value
        this.children = []
        this.parent = null
        this.pos = { x: 0 , y: 0}
        this.r = 20
    }

    get left() { return this.children[LEFT] }

    set left(value) {
        value.parent = this
        this.children[LEFT] = value
    }

    get right() { return this.children[RIGHT]}

    set right(value) {
        value.parent = this
        this.children[RIGHT] = value
    }

    set position(position){ this.pos = position }

    get position(){ return this.pos }

    get radius() { return this.r }
}

이제 노드 클래스가 생겼습니다. 트리 클래스를 실현할 것입니다. 하위 노드, 그것들의 값과 위치를 삽입할 수 있습니다.

class Tree{

    constructor(){
        this.root = null
        this.startPosition = {x: 800, y: 44}
        this.axisX = 350
        this.axisY = 80
    }

    getPosition({x , y}, isLeft = false){
        return { x: isLeft ? x - this.axisX + y : x + this.axisX - y, y: y + this.axisY }
    }

    add(value){
        const newNode = new Node(value)
        if(this.root == null){
            newNode.position = this.startPosition
            this.root = newNode
        } else {
            let node = this.root
                while(node){
                    if(node.value == value)
                        break
                    if(value > node.value){
                        if(node.right == null){
                            newNode.position = this.getPosition(node.position) //get current position of new node
                            node.right = newNode 
                            break
                         }
                         node = node.right
                     } else {
                         if(node.left == null){
                             newNode.position = this.getPosition(node.position,true) //get current position of new node
                             node.left = newNode
                             break
                         }
                         node = node.left
                     }
               }
        }
    }

    // bfs(){ ... } it will be implemented later
}

트리 클래스에서 구조 함수에는 다음과 같은 네 가지 속성이 초기화됩니다.

루트 속성은 트리의 루트 노드를 가리킨다.

startPosition은 루트 노드가 가로 또는 X 축과 세로 또는 Y 축에 있는 위치를 결정하는 속성입니다.

axisX와 axisY는 평면에서 도형으로 노드를 이동할 수 있는 수치 상수입니다.

트리류의add 방법은 트리에 새 노드를 삽입할 수 있으며 노드의 위치는 왼쪽 노드인지 오른쪽 노드인지에 따라 달라진다.

getPosition 방법은 X와 Y 위치를 매개 변수로 수신합니다. isLeft 로고는 기본적으로false입니다. 이 방법은 새 노드 평면의 새 위치를 계산할 수 있습니다.상수 축 X는 Y축의 위치와 함께 X축에서 추가 또는 제거됩니다. 이 축에서는 노드 사이의 이동 거리가 점점 줄어들고 나무의 깊이가 더 커지기 때문입니다.한편, Y 축은 항상 동일한 거리에 있기 때문에 고정 축만 추가합니다.

광범위한 우선 순위 검색

평면에 두 갈래 나무를 그리려면 나무의 각 노드를 훑어보아야 한다. 이를 위해 두 가지 가능성이 있다.

첫 번째는 Depth First Search - DFS입니다. 뿌리에서 시작하여 각 노드를 말단 노드로 확장하거나 각 지점에 대해 창고를 사용하여 이동할 때 임시 저장 노드를 사용합니다.

두 번째 옵션은 Breadth First Search - BFS 루트에서 시작하여 각 노드를 분기가 아닌 등급으로 훑어보고 대기열을 사용하여 임시로 노드를 저장합니다.

트리를 그리기 위해 나는 BFS를 사용하기로 결정했다. 왜냐하면 나는 단계별로 노드를 그리는 것을 더 좋아하기 때문이다. 확실히 트리의 모든 노드에 접근해야 할 때 DFS를 사용하는 것이 가장 좋다. 너비로 검색하면 가장 짧은 경로를 효과적으로 찾을 수 있기 때문이다. 그러나 이런 상황에서 입맛과 기본 설정은 기술적이지 않다.

이제 BFS 구현을 통해 트리를 그릴 때입니다.

var c = document.getElementById("myCanvas")
var ctx = c.getContext("2d")
...
bfs() {
    const queue = []
    const black = "#000"
    queue.push(this.root)

    while (queue.length !== 0) {
        const node = queue.shift()
        const {x, y} = node.position
        const color = "#" + ( (1<<24) * Math.random() | 0 ).toString(16)

        ctx.beginPath()
        ctx.strokeStyle = black
        ctx.fillStyle = color
        ctx.fill()
        ctx.stroke()
        ctx.strokeStyle = black
        ctx.strokeText(node.value, x, y)

        node.children.forEach(child => {
            const {x: x1, y: y1} = child.position
            ctx.beginPath();
            ctx.moveTo(x, y + child.radius)
            ctx.lineTo(x1, y1 - child.radius)
            ctx.stroke()
            queue.push(child)
        });
    }
}

위의 알고리즘은 다음과 같습니다.

대기열 변수를 만듭니다.javascript에서 수조는 이 목적에 사용됩니다.constqueue=[].

트리의 루트, 대기열을 삽입합니다.(this.root)를 대기열에 밀어넣습니다.

대기열에 노드가 있으면 다음과 같이 한다.

대기열에서 첫 번째 항목을 삭제하고 삭제된 항목const node=queue를 되돌려줍니다.shift().

노드를 삭제할 위치const {x, y}= node를 가져옵니다.위치 (아래 줄) 는 무작위로 색을 계산합니다.

빈 루트 목록을 통해 새 루트를 시작합니다. 새 루트를 만들어서 둘레ctx를 그려야 하기 때문입니다.beginPath().

선의 색깔을 결정합니다. 이 예에서 검은색, 즉ctx입니다.strokeStyle = 검은색, 채움 색상 ctx를 결정합니다.fillStyle = 색상.

원을 그리려면 360도의 호를 그려야 한다. 즉, 2π호도를 그려야 한다. 이를 위해 우리는 방법ctx를 사용한다.원호(x, y, node.radius, 0, 2*Math.PI), 그 중에서 x와 y는 원주의 중심이고 다음 매개 변수는 반경이며 0은 시작 각도를 대표하고 마지막 것은 호도로 표시하는 최종 각도를 대표한다.

이전에 정의된 선ctx를 그립니다.stroke (), 흑선ctx를 다시 지정합니다.스트로크 스타일=블랙.

노드 ctx의 값을 기록합니다.strokeText(node.value, x, y), 원주에서 같은 위치입니다.

부모 노드가 있는 각 하위 노드(node.children.forEach)에 대해 다음을 수행합니다.

하위 노드 const {x:x1, y:y1}=child의 위치를 가져옵니다.위치

부모 노드(ctx.moveTo(x, y+자 반경)에서 각 원주 가장자리를 연결하는 자 노드(ctx.lineTo(x1, y1-자 반경)까지 선을 그립니다.

하위 노드를 대기열에 추가합니다.밀다.

준비했어나무를 그리는 방법을 실현했으니 이제 나무류의 삽입과 그리는 방법을 실행에 옮길 때가 되었다.

const t = new Tree()
t.add(10)
t.add(5)
t.add(15)
t.add(3)
t.add(14)
t.add(16)
t.add(4)
t.add(6)
t.add(2)
t.bfs()

앞의 코드를 실행한 결과는 다음과 같다.

이 소스 코드는 GitHub 에서 찾을 수 있습니다.
그것은 쓸모가 있습니까?당신의 지지나 공유를 표현합니다!
정말 감사합니다.