Comment créer et parcourir un arbre binaire en javascript ? (exemple de code)

Cet article vous présentera comment créer et parcourir un arbre binaire à l'aide de JavaScript. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. J'espère qu'il sera utile à tout le monde.

1. Parlons d'abord de la traversée d'arbre binaire. La méthode de traversée :

Parcours de pré-commande : parcourez d'abord le nœud racine, puis le sous-arbre gauche. , puis le sous-arbre droit.

Parcours dans l'ordre : parcourez d'abord le sous-arbre gauche, puis le nœud racine, puis le sous-arbre droit

Parcours suivant : parcourez d'abord le sous-arbre gauche, puis le sous-arbre droit, puis le nœud racine

Le code ci-dessus : utilise principalement la récursion

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());

Parcours non récursif d'arbres binaires

• Parcours en profondeur d'abord (principalement en utilisant le premier entré-dernier sorti de la pile)

• Parcours en largeur d'abord (en utilisant principalement le premier entré, premier sorti de la file d'attente)

//深度优先非递归
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);
        }
    }

}

La priorité de profondeur utilise principalement la pile, en appuyant d'abord sur le sous-arbre droit, puis sur le sous-arbre gauche

Priorité de largeur utilise principalement la file d'attente, entrant d'abord dans le sous-arbre de gauche, puis dans le sous-arbre de droite

Priorité en profondeur Le résultat du parcours est le même que le parcours de pré-ordre ABDGHCEIF, et le résultat du parcours en largeur en premier est ABCDEFGHI

2. Créer un arbre binaire

La façon de créer un arbre binaire en 1 est trop maladroite, et elle est fausse pour nous Construisez votre propre arbre binaire basé sur l'arbre binaire complet modèle. Les données vides sont représentées par #. Comme le montre la figure ci-dessous, nous l'appelons un arbre binaire étendu. Nous prenons la séquence AB#D##C## du parcours de pré-ordre.

Le code ci-dessus : utilise également la récursion

//前序遍历得到的字符串
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)

Vous pouvez également utiliser le parcours dans l'ordre ou le parcours post-ordre pour créer un arbre binaire Le code. génère un nœud et échange simplement l'ordre des codes pour construire les sous-arbres gauche et droit

Tutoriel recommandé : "Tutoriel vidéo JavaScript"

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!