Ts实现二叉树的增删查

@(code)[typescript]

前言

二叉树是个很有趣的东西：一个二叉树是由叫做节点的东西组成，一个节点同时有一个左节点和右节点。可能指向其他节点，也可能指向null。而一个二叉树必然存在一个根节点。然后根节点下面有其他节点。。。当二叉树里面的data存数字，并数字按照一定顺序排列的时候。就会拥有很有趣的性质：二叉树查找值很快，因为是按照二分法进行查找，复杂度只有O(logn)，所以是很快的。二叉树添加值也很快，只需要找到合适的节点，然后将新节点挂在下面即可。但二叉树删除节点很复杂。下面我们会进行说明。

算法

下面的算法我们暂时用伪代码来完成

add的算法

定义函数add（参数：传入的数据data, 参照节点）：
    若 参照节点的值 小于 data：
        若 参照节点有左节点：
            递归调用add（data，参照节点的左节点）
        否则：
            参照节点的左节点 设为 新节点data
    否则若 参照节点的值 大于 data：
        若 参照节点有右节点：
            递归调用add（data， 参照节点的右节点）
        否则：
            参照节点的由节点 设为 新节点data
结束定义

核心在于递归执行，一直到自己应该放在节点某侧，并某侧没有东西位置。

toArray的算法

我们想把这个二叉树变为一个number[]怎么办？应该遍历所有二叉树，把值放到一个array中。核心在于怎么遍历？

定义函数toArray（参数：传入的参照节点）：
    定义变量 result 为空数组
    若 参照节点有左节点：
        将 递归调用自身toArray（参照节点的左节点）的结果 加入 result
    将参照节点自身的值 加入 result
    若 参照节点有右节点：
        将 递归调用自身toArray(参照节点的右节点)的结果加入 result
    返回 result
结束定义

delete的算法

删除情况比较麻烦。大概分为一下三种情况：

被删除的节点没有子节点，左右都没有
被删除的节点只有一个子节点
被删除的节点同时有左、右两个子节点

对于第一种情况：很简单，直接将被删除的节点的父节点，指向他的位置，设为空就好第二中情况也很简单，将被删除节点的父节点，指向的位置，变为被删除节点的单个子节点。自然链条就接上了。但第三种情况，我们不肯同时将左、右两个子节点挂在父节点下。不合二叉的规则。所以怎么办呢？再思考一下二叉树的规则： 一个节点的两个子节点，左节点中全部子节点中，最大的值必然小于右节点全部子节点中最小的值。 那么，有一种办法，我们将被删除的右节点先拿到一边。现在被删除节点只有左边的子节点了。按照上面delete的规则第二条，我们把被删除节点的左节点接到被删除节点父节点的指向上。然后，将原来的右子节点，接到左子节点的最右端末端！大概是这样：

        4
    2        6
 1    3    5    7
 移除节点2，临时拿走2的右节点3，将左节点1直接接到4的左节点上，变为：
        4
    1        6
           5    7
 将被拿走的节点3，接到原来左节点1的最右侧：
         4
    1        6
      3    5    7
 于是这样就成功达到我们的目的了！

伪代码：

定义 delete（目标节点）：
    找到目标节点的父节点
    找到目标节点是父节点的左节点还是右节点

    若 目标节点没有左节点和右节点：
        目标节点父节点的指向设为空
    否则 若 目标节点没有左节点：
        目标节点父节点的指向设为目标节点的右节点
    否则 若 目标节点没有右节点：
        目标节点父节点的指向设为目标节点的左节点
    否则：
        定义变量 temp 赋值为 目标节点的右节点
        目标节点父节点的指向设为目标节点的左节点
        找到目标节点的左节点的最大子节点，该节点的右子节点指向temp
结束定义

ts代码

有一些方法有出入，因为代码是几天前写的，上文伪代码是刚刚回忆的。具体实现方式可能稍微有些不同，但思想是一样的。

代码

namespace BST { 

class Node {
    public left: Node = null;
    public right: Node = null;
    constructor (
        public data: number
    ) { }
}

enum Order {
    MIDDLE,
    LEFT,
    RIGHT
}

class BST {
    constructor (
        public root: Node
    ) { }

    getAll (node: Node = this.root, arr: number[] = []): number[] {
        if (node.left) {
            this.getAll(node.left, arr);
        }
        arr.push(node.data);
        if (node.right) {
            this.getAll(node.right, arr);
        }
        return arr;
    }

    map (callback: Function, type: number = Order.LEFT, node: Node = this.root): void {
        switch (type) {
            case Order.MIDDLE:
                callback(node.data);
                node.left && this.map(callback, type, node.left);
                node.right && this.map(callback, type, node.right);
                break;
            case Order.RIGHT:
                node.right && this.map(callback, type, node.right);
                callback(node.data);
                node.left && this.map(callback, type, node.left);
                break;
            default:
                node.left && this.map(callback, type, node.left);
                callback(node.data);
                node.right && this.map(callback, type, node.right);
        }
    }

    findMin (node: Node = this.root): Node {
        while (node.left) {
            node = node.left;
        }
        return node;
    }

    findMax (node: Node = this.root): Node {
        while (node.right) {
            node = node.right;
        }
        return node;
    }

    find (condition: (node: Node) => boolean, node: Node = this.root): Node {
        // set found as null
        let found: Node = null;
        // if node is the target, return node
        if (condition(node)) {
            found = node;
        } else {
            // else, if node has left node, check the left node
            if (node.left) {
                found = this.find(condition, node.left);
            }
            // if left node not match, check the right node
            if (!found && node.right) {
                found = this.find(condition, node.right);
            }
        }
        // return the result: found node or null
        return found;
    }

    add (value: number, node: Node = this.root): void {
        if (node.data > value) {
            if (node.left) {
                this.add(value, node.left);
            } else {
                node.left = new Node(value);
            }
        } else {
            if (node.right) {
                this.add(value, node.right);
            } else {
                node.right = new Node(value);
            }
        }
    }

    delete (data): void {
        let position = '';
        let targetNode = this.find((node: Node) => node.data === data);
        if (targetNode === this.root) {
            throw new Error('You can\'t delete the root node in BST!');
        }
        if (targetNode) {
            let parentNode = this.find((node: Node) => {
                if (node.left === targetNode) {
                    position = 'left';
                    return true;
                } else if (node.right === targetNode) {
                    position = 'right';
                    return true;
                } else {
                    return false;
                }
            });

            // no sub node
            if (!targetNode.left && !targetNode.right) {
                parentNode[position] = null;
            // one sub node
            } else if (!targetNode.right) {
                parentNode[position] = targetNode.left;
            } else if (!targetNode.left) {
                parentNode[position] = targetNode.right;
            // two subs node
            } else {
                // right node append to max node of sub left 
                parentNode[position] = targetNode.left;
                this.findMax(targetNode.left).right = targetNode.right;

                // left node append to min node of sub right
                // parentNode[position] = targetNode.right;
                // this.findMin(targetNode.right).left = targetNode.left;
            }
        }
    }
}

const run = () => {
    let root = new Node(50);

    let bst = new BST(root)
    bst.add(49);
    bst.add(45);
    bst.add(39);
    bst.add(43);
    bst.add(48);

    bst.add(110);
    bst.add(150);
    bst.add(64);
    bst.add(72);
    bst.add(59);

    let result = bst.find((node: Node) => {
        return node.right && node.right.data > 110;
    })
    console.log(result);

    bst.delete(50);
    console.log(bst);
}

run();

}

大家可以自行试试。

Cuuube / blog

[数据结构]Ts实现二叉树的增删查 #76

Ts实现二叉树的增删查

前言

算法

add的算法

toArray的算法

delete的算法

ts代码

代码