How to create and traverse a binary tree in javascript? (code example)

This article will introduce to you how to use JavaScript to create and traverse a binary tree. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to everyone.

1. Let’s talk about binary tree traversal first. The traversal method:

Pre-order traversal: first traverse the root node, then the left subtree, and then the right subtree. Tree

In-order traversal: first traverse the left subtree, then the root node, and then the right subtree

Subsequent traversal: first traverse the left subtree, then the right subtree, and then the root node

The above code: mainly uses recursion

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

Non-recursive traversal of binary trees

• Depth-first traversal (mainly using the first-in-last-out of the stack)

• Breadth-first traversal (mainly using the first-in-first-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);
        }
    }

}

Depth priority mainly uses the stack, pressing the right subtree first, then the left subtree

Breadth priority mainly uses the queue, entering the left subtree first, then the right subtree

Depth priority The traversal result is the same as the preorder traversal ABDGHCEIF. The breadth-first traversal result is ABCDEFGHI

2. Creating a binary tree. The way to create a binary tree in

1 is too clumsy. It is false to us. Build your own binary tree based on the complete binary tree model. The empty data is represented by #. As shown in the figure below, we call it an extended binary tree. We take the sequence AB#D##C## of the preorder traversal.

The above code: also uses recursion

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

You can also use in-order traversal or post-order traversal to create a binary tree. The code generates node and Just exchange the order of codes for building the left and right subtrees

Recommended tutorial: "JavaScript Video Tutorial"

The above is the detailed content of How to create and traverse a binary tree in javascript? (code example). For more information, please follow other related articles on the PHP Chinese website!