자바스크립트에서 이진 트리를 만들고 탐색하는 방법은 무엇입니까? (코드 예)

이 기사에서는 JavaScript를 사용하여 이진 트리를 만들고 탐색하는 방법을 소개합니다. 도움이 필요한 친구들이 모두 참고할 수 있기를 바랍니다.

1 먼저 이진 트리 탐색에 대해 이야기해 보겠습니다. 탐색 방법:

선순서 탐색: 먼저 루트 노드를 탐색한 다음 왼쪽 하위 트리, 오른쪽 하위 트리를 탐색합니다.

순서 탐색: 먼저 왼쪽 하위 트리, 루트 노드, 오른쪽 하위 트리

순차 순회: 먼저 왼쪽 하위 트리, 오른쪽 하위 트리, 루트 노드 순회

위 코드: 주로 재귀를 사용합니다.

function TreeCode() {
    let BiTree = function (ele) {
        this.data = ele;
        this.lChild = null;
        this.rChild = null;
    }

    this.createTree = function () {
        let biTree = new BiTree('A');
        biTree.lChild = new BiTree('B');
        biTree.rChild = new BiTree('C');
        biTree.lChild.lChild = new BiTree('D');
        biTree.lChild.lChild.lChild = new BiTree('G');
        biTree.lChild.lChild.rChild = new BiTree('H');
        biTree.rChild.lChild = new BiTree('E');
        biTree.rChild.rChild = new BiTree('F');
        biTree.rChild.lChild.rChild = new BiTree('I');
        return biTree;
    }
}

//前序遍历
function ProOrderTraverse(biTree) {
    if (biTree == null) return;
    console.log(biTree.data);
    ProOrderTraverse(biTree.lChild);
    ProOrderTraverse(biTree.rChild);
}

//中序遍历
function InOrderTraverse(biTree) {
    if (biTree == null) return;
    InOrderTraverse(biTree.lChild);
    console.log(biTree.data);
    InOrderTraverse(biTree.rChild);
}

//后续遍历
function PostOrderTraverse(biTree) {
    if (biTree == null) return;
    PostOrderTraverse(biTree.lChild);
    PostOrderTraverse(biTree.rChild);
    console.log(biTree.data);
}

let myTree = new TreeCode();
console.log(myTree.createTree());
console.log('前序遍历')
ProOrderTraverse(myTree.createTree());
console.log('中序遍历')
InOrderTraverse(myTree.createTree());
console.log('后续遍历')
PostOrderTraverse(myTree.createTree());

이진 트리의 비재귀 순회

• 깊이 우선 순회(주로 스택의 선입선출 방식 사용)

• 폭 우선 순회(주로 선입선 방식 사용) out of the queue)

//深度优先非递归
function DepthFirstSearch(biTree) {
    let stack = [];
    stack.push(biTree);

    while (stack.length != 0) {
        let node = stack.pop();
        console.log(node.data);
        if (node.rChild) {
            stack.push(node.rChild);
        }
        if (node.lChild) {
            stack.push(node.lChild);
        }

    }

}


//广度优先非递归
function BreadthFirstSearch(biTree) {
    let queue = [];
    queue.push(biTree);
    while (queue.length != 0) {
        let node = queue.shift();
        console.log(node.data);
        if (node.lChild) {
            queue.push(node.lChild);
        }
        if (node.rChild) {
            queue.push(node.rChild);
        }
    }

}

깊이 우선은 주로 스택을 사용하며 오른쪽 하위 트리를 먼저 누른 다음 왼쪽 하위 트리를 누릅니다

Breadth는 먼저 주로 큐를 사용하고 왼쪽 하위 트리를 먼저 입력한 다음 오른쪽 하위 트리를 입력합니다

깊이 우선 순회 결과는 선주문 순회 ABDGHCEIF와 동일하고 너비 우선 순회 결과는 ABCDEFGHI

2입니다. 생성 Binary Tree

1에서 이진 트리를 생성하는 방법이 너무 서투릅니다. 완전한 이진 트리 모델을 기반으로 자체 이진 트리를 구축한다고 가정합니다. 아래 그림과 같이 빈 데이터는 #으로 표시되며 순회된 시퀀스 AB#D#을 사용합니다. #기음##.

위 코드는 재귀도 사용합니다

//前序遍历得到的字符串
let strArr = 'AB#D##C##'.split('');

function BiTree(ele) {
    this.data = ele;
    this.lChild = null;
    this.rChild = null;
}
var newTree = new BiTree('#');

function createBiTree(biTree) {
    if (strArr.length == 0) return;
    let str = strArr.shift();
    if (str == '#') return;
    biTree.data = str;
    if (strArr[0] != '#') {
        biTree.lChild = new BiTree('#')
    }
    createBiTree(biTree.lChild);
    if (strArr[0] != '#') {
        biTree.rChild = new BiTree('#')
    }
    createBiTree(biTree.rChild);
}
createBiTree(newTree);
console.log(newTree);
ProOrderTraverse(newTree)

순차 순회 또는 후순 순회를 사용하여 이진 트리를 생성할 수도 있습니다. 노드 생성 순서와 왼쪽 및 오른쪽 하위 트리 구성 순서를 바꾸면 됩니다. code

추천 튜토리얼: "JavaScript 비디오 튜토리얼"

위 내용은 자바스크립트에서 이진 트리를 만들고 탐색하는 방법은 무엇입니까? (코드 예)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!