Tree Node

function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}
// usage
const root = new Node(2);
root.left = new Node(1);
root.right = new Node(3);

Step

Initiate a queue with root in it
Remove the first item out of queue
Push the left and right children of popped item into the queue
Repeat steps 2 and 3 until the queue is empty

function walkBFS(root) {
    if (root === null) return;

    const queue = [root];
    while (queue.length) {
        const item = queue.shift();
        // do something
        console.log(item);

        if (item.left) queue.push(item.left);
        if (item.right) queue.push(item.right);
    }
}

DFS

Pre-order

递归

function DFS(root) {
    if (!root) return;
    console.log(root);
    DFS(root.left);
    DFS(root.right);
}

迭代

function DFS(root) {
    if (!root) return;
    // 栈
    const stack = [root];
    while (stack.length) {
        const item = stack.pop();
        console.log(item);
        item.right && stack.push(item.right);
        item.left && stack.push(item.left);
    }
}

In-order

递归

function DFS(root) {
    if (!root) return;
    DFS(root.left);
    console.log(root);
    DFS(root.right);
}

迭代

function DFS(root) {
    if (!root) return;
    let node = root;
    const ans = [];
    // 回溯
    const stack = [];
    while (node || stack.length) {
        while (node) {
            stack.push(node);
            node = node.left;
        }
        const last = stack.pop();
        ans.push(last.val);
        // 重点，保留 right 在下一轮 while(node) 的时候入栈
        node = last.right;
    }
    return ans;
}

Post-order

递归

function DFS(root) {
    if (!root) return;
    console.log(root);
    DFS(root.left);
    DFS(root.right);
}

迭代

/**
 *  前序遍历 root -> left -> right
 *  后序遍历 left -> right -> root
 *
 * 可在前序遍历的时候 保存为 root -> right -> left 结构 然后reverse
 * @param {} root
 * @returns
 */

function walkPostOrder(root) {
    if (root === null) return [];

    const tempStack = [root],
        result = [];

    while (tempStack.length) {
        const last = tempStack.pop();

        result.push(last);

        if (last.left) tempStack.push(last.left);
        if (last.right) tempStack.push(last.right);
    }

    return result.reverse();
}

AVL 树

details

class AVLNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
        this.height = 0; // 初始节点高度为 0
    }
}

class AVLTree {
    constructor() {
        this.root = null;
    }

    // 获取节点高度
    getHeight(node) {
        return node ? node.height : 0;
    }

    // 更新节点高度
    updateHeight(node) {
        node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
    }

    // 获取平衡因子
    getBalanceFactor(node) {
        return node ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
    }

    // 右旋操作
    rotateRight(y) {
        const x = y.left;
        const T2 = x.right;

        // 旋转
        x.right = y;
        y.left = T2;

        // 更新高度
        this.updateHeight(y);
        this.updateHeight(x);

        return x; // 返回新的根
    }

    // 左旋操作
    rotateLeft(x) {
        const y = x.right;
        const T2 = y.left;

        // 旋转
        y.left = x;
        x.right = T2;

        // 更新高度
        this.updateHeight(x);
        this.updateHeight(y);

        return y; // 返回新的根
    }

    // 插入节点
    insert(node, value) {
        // 1. 标准的二叉搜索树插入
        if (!node) return new AVLNode(value);

        if (value < node.value) {
            node.left = this.insert(node.left, value);
        } else if (value > node.value) {
            node.right = this.insert(node.right, value);
        } else {
            // 相同的值不允许插入
            return node;
        }

        // 2. 更新当前节点的高度
        this.updateHeight(node);

        // 3. 计算平衡因子
        const balanceFactor = this.getBalanceFactor(node);

        // 4. 如果不平衡，执行旋转操作
        // LL 情况
        if (balanceFactor > 1 && value < node.left.value) {
            return this.rotateRight(node);
        }

        // RR 情况
        if (balanceFactor < -1 && value > node.right.value) {
            return this.rotateLeft(node);
        }

        // LR 情况
        if (balanceFactor > 1 && value > node.left.value) {
            node.left = this.rotateLeft(node.left);
            return this.rotateRight(node);
        }

        // RL 情况
        if (balanceFactor < -1 && value < node.right.value) {
            node.right = this.rotateRight(node.right);
            return this.rotateLeft(node);
        }

        // 返回当前节点
        return node;
    }

    // 插入入口
    insertValue(value) {
        this.root = this.insert(this.root, value);
    }

    // 中序遍历 (用于验证 AVL 树是否正确)
    inorderTraversal(node) {
        if (node) {
            this.inorderTraversal(node.left);
            console.log(node.value);
            this.inorderTraversal(node.right);
        }
    }

    inorder() {
        this.inorderTraversal(this.root);
    }
}

Refer

tree-data-structure-in-javascript