JS二叉树|极客笔记

JS二叉树

二叉树是一种常用的数据结构，它由节点组成，每个节点最多有两个子节点：左子节点和右子节点。在JavaScript中，我们可以很容易地实现二叉树，并对二叉树进行各种操作。

二叉树的表示方法

在JS中，可以通过对象来表示二叉树。每个节点就是一个对象，包含值以及左右子节点的引用。例如，以下是一个简单的二叉树结构表示：

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// 创建一个二叉树
const rootNode = new Node(1);
rootNode.left = new Node(2);
rootNode.right = new Node(3);

rootNode.left.left = new Node(4);
rootNode.left.right = new Node(5);

rootNode.right.left = new Node(6);
rootNode.right.right = new Node(7);

// 二叉树结构如下所示
//       1
//     /   \
//    2     3
//   / \   / \
//  4   5 6   7

二叉树的遍历

二叉树的遍历是指按照一定顺序访问二叉树的所有节点。常见的遍历方式包括前序遍历、中序遍历和后序遍历。下面分别介绍这三种遍历方式的实现。

前序遍历

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。实现前序遍历的代码如下：

function preorderTraversal(root) {
    if (root === null) {
        return;
    }

    console.log(root.value); // 先访问根节点
    preorderTraversal(root.left); // 遍历左子树
    preorderTraversal(root.right); // 遍历右子树
}

// 调用前序遍历函数
preorderTraversal(rootNode);

运行上述代码，将会按照前序遍历的顺序输出二叉树的所有节点值：

1 2 4 5 3 6 7

中序遍历

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。实现中序遍历的代码如下：

function inorderTraversal(root) {
    if (root === null) {
        return;
    }

    inorderTraversal(root.left); // 遍历左子树
    console.log(root.value); // 访问根节点
    inorderTraversal(root.right); // 遍历右子树
}

// 调用中序遍历函数
inorderTraversal(rootNode);

运行上述代码，将会按照中序遍历的顺序输出二叉树的所有节点值：

4 2 5 1 6 3 7

后序遍历

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。实现后序遍历的代码如下：

function postorderTraversal(root) {
    if (root === null) {
        return;
    }

    postorderTraversal(root.left); // 遍历左子树
    postorderTraversal(root.right); // 遍历右子树
    console.log(root.value); // 访问根节点
}

// 调用后序遍历函数
postorderTraversal(rootNode);

运行上述代码，将会按照后序遍历的顺序输出二叉树的所有节点值：

4 5 2 6 7 3 1

二叉树的常见操作

除了遍历，二叉树还支持一些其他常见的操作，如查找、插入和删除等。

查找操作

在二叉树中查找一个特定值的节点可以使用递归的方式实现。代码如下：

function search(root, value) {
    if (root === null || root.value === value) {
        return root;
    }

    if (value < root.value) {
        return search(root.left, value);
    } else {
        return search(root.right, value);
    }
}

// 在二叉树中查找值为5的节点
const node = search(rootNode, 5);
console.log(node); // 输出找到的节点对象

插入操作

向二叉树中插入一个新节点也是一个常见的操作，可以使用递归的方式实现。代码如下：

function insert(root, value) {
    if (root === null) {
        return new Node(value);
    }

    if (value < root.value) {
        root.left = insert(root.left, value);
    } else {
        root.right = insert(root.right, value);
    }

    return root;
}

// 向二叉树中插入值为8的新节点
rootNode = insert(rootNode, 8);

删除操作

删除二叉树中的某个节点稍微复杂一些，需要考虑被删除节点的子节点情况，可以分为三种情况来处理：无子节点、有一个子节点、有两个子节点。这里给出一个简单的删除操作示例：

function deleteNode(root, value) {
    if (root === null) {
        return root;
    }

    if (value < root.value) {
        root.left = deleteNode(root.left, value);
    } else if (value > root.value) {
        root.right = deleteNode(root.right, value);
    } else {
        if (root.left === null) {
            return root.right;
        } else if (root.right === null) {
            return root.left;
        }

        root.value = findMinValue(root.right);
        root.right = deleteNode(root.right, root.value);
    }

    return root;
}

function findMinValue(root) {
    let minValue = root.value;
    while (root.left !== null) {
        minValue = root.left.value;
        root = root.left;
    }
    return minValue;
}

// 删除值为3的节点
rootNode = deleteNode(rootNode, 3);