数据结构-二叉树和二叉查找树

lickylin

2019-06-28

树是计算机科学中经常用到的一种数据结构. 数是一种非线性的数据结构, 以分层的方式存储数据. 数被用来存储具有层级关系的数据, 比如文件系统中的文件; 树还被用来存储有序列表. 本章将研究一种特殊的树: 二叉树 . 选择树而不是那些基本的数据结构, 是因为在二叉树上进行查找非常快(而在链表中查找则不是这样), 为二叉树添加或删除元素也非常快(而对数组执行添加或删除则不是这样).

树的定义

树是一组以边连接的节点组成. 这里不做过多赘述. 深入了解点这里)
二叉树 是一种特殊的树, 它的子节点个数不超过两个. 二叉树具有一些特殊的计算性质, 使得它们之上的一些操作异常高效.

二叉树和二叉查找树

正如前面提到的那样, 二叉树 每一个节点的子节点不允许超过两个. 通过将子节点的个数限定为2, 可以写出高效的程序在树中插入、查找和删除数据.

在使用JS构建二叉树之前, 需要给我们关于树的词典里再加两个新名词.

左节点: 一组特定的值.
右节点: 另一组特定的值.

当考虑某种特殊的二叉树, 比如 二叉查找树 时, 确定子节点非常重要.
二叉查找树是一种特殊的二叉树.

相对较小的值保存在左节点中.
较大的值保存在右节点中.

这一特性使得查找效率很高, 对于数值型和非数值型的数据, 比如单词和字符串, 都是如此.

实现二叉查找树

二叉查找树由节点组成, 所以我们要定义的第一个对象就是Node, 该对象和前面介绍链表时的对象类似.
Node对象及保存数据, 也保存和其它节点的链接(left和right), show()方法用来显示保存在节点中的数据.

创建BST类用来表示二叉查找树. 我们让类只包含一个数据成员: 一个表示二叉查找树根节点的Node对象. 该类的构造函数将根节点初始化为null, 以此创建一个空节点.

BST先要有一个insert()方法, 用来向树中加入新节点. 这个方法有点复杂, 需要着重讲解. 首先要创建一个Node对象, 将数据传入该对象保存.

其次检查BST是否有根节点, 如果没有, 那么这是棵新树, 该节点就是根节点, 这个方法到此也就完成了; 否则进入下一步.

如果待插入节点不是根节点, 那么就需要准备遍历BST, 找到插入的适当位置. 该过程类似于遍历链表. 用一个变量存储当前节点, 一层层地遍历BST.

进入BST以后, 下一步就决定将节点放在哪个地方. 找到正确的插入点时, 会跳出循环. 查找正确插入点的算法如下:

设根节点为当前节点.
如果待插入节点保存的数据小于当前节点, 则设新的当前节点为原节点的左节点; 反之, 执行第4步.
如果当前节点的左节点为null, 就将新的节点插入这个位置, 退出循环; 反之, 继续执行下一次循环.
设新的当前节点为源节点的右节点.
如果当前节点的右节点为null, 就将新的节点插入这个位置, 退出循环; 反之, 继续执行下一次循环.

有了上面的算法, 就可以开始实现BST类了.

window.log = console.log.bind(console)

class Node {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
    show() {
        return this.data;
    }
};

class BST {
    constructor() {
        this.root = null;
    }
    insert(data) {
        const n = new Node(data);
        
        if(this.root === null) {
            this.root = n;
        } else {
            let current = this.root;
            let parent;
            while(true) {
                parent = current;
                if(data < current.data) {
                    current = current.left;
                    if(current === null) {
                        parent.left = n;
                        break;
                    }
                } else {
                    current = current.right;
                    if(current === null) {
                        parent.right = n;
                        break
                    }
                }
            }
        }
    }
    
};

遍历二叉查找树

现在BST类已经初步成型, 但是操作上还只能插入节点, 我们需要有能力遍历BST, 这样就可以按照不同顺序, 比如按照数字大小或字母先后, 显示节点上的数据.

有三种遍历BST的方式:

中序: 按照节点上的键值, 以升序访问BST上的所有节点.
先序: 先访问根节点, 然后以同样方式访问左子树和右子树.
后序: 先访问叶子节点, 从左子树到右子树, 再到根节点.

需要中序遍历的原因显而易见, 但为什么需要先序遍历和后序遍历就不是那么明显了. 我们先来实现这三种遍历方式, 在后序再解释它们的用途.

中序遍历使用递归方式最容易实现. 该方法需要以升序访问树中所有节点, 先访问左子树, 再访问根节点, 最后访问右子树.

function inOrder(node) {
    if (node !== null) {
        inOrder(node.left);
        log(node.show() + ' ')
        inOrder(node.right)
    }
};

const bst = new BST();
bst.insert(4);
bst.insert(34);
bst.insert(43);
bst.insert(98);
bst.insert(71);
bst.insert(1);
inOrder(bst.root);

先序遍历(preOrder())和中序遍历(inOrder())方法的唯一区别, 就是if语句中代码的顺序.
在inOrder()方法中, show()函数像三明治一样夹在两个递归调用之间;
在preOrder()方法中, show()函数放在两个递归调用之前.

function preOrder(node) {
    if (node !== null) {
        log(node.show() + ' ');
        preOrder(node.left);
        preOrder(node.right);
    }
};

后序遍历postOrder():

function postOrder(node) {
    if (node !== null) {
        postOrder(node.left);
        postOrder(node.right);
        log(node.show() + ' ');
    }
}

在二叉查找树上进行查找

对BST通常有下列三种类型的查找:

查找给定值.
查找最小值.
查找最大值.

查找最小值和最大值

查找BST上的最小值和最大值非常简单.
getMin()查找最小值, 因为较小的值总是在左子节点上, 只需要遍历左子树, 直到找到最后一个节点.

getMin() {
    let current = this.root;
    while (current.left !== null) {
        current = current.left;
    };

    return current.data;
}

getMax()查找最大值, 只需要遍历右子树, 直到找到最后一个节点, 该节点上保存的值即为最大值.

getMax() {
    let current = this.root;
    while (current.right !== null) {
        current = current.right;
    };

    return current.data;
}

测试:

const bst = new BST();
bst.insert(4);
bst.insert(34);
bst.insert(43);
bst.insert(98);
bst.insert(71);
bst.insert(1);
log('最小值: ' + bst.getMin());
log('最大值: ' + bst.getMax());

// 输出:
// 最小值: 1
// 最大值: 98

这两个方法返回最小值和最大值, 但有时, 我们希望方法返回存储最小值和最大值的节点. 这很好实现, 只需要修改方法, 让它返回当前节点, 而不是节点中存储的数据即可.

查找给定值

在BST上查找给定值, 需要比较该值和当前节点上的值的大小. 通过比较, 就能确定如果给定值不在当前节点时, 该向左遍历还是右遍历.

find(data) {
    let current = this.root;
    while (current !== null) {
        if (current.data === data) {
            return current;
        } else if (data < current.data) {
            current = current.left;
        } else if (data > current.data) {
            current = current.right;
        }
    };

    return null;
}

从二叉查找树上删除节点

删除节点的操作最复杂, 其复杂程度取决于删除哪个节点. 如果删除没有子节点的节点, 那么非常简单. 如果节点只有一个子节点, 不管是左子节点还是右子节点, 就变得稍微有点复杂了. 删除包含两个子节点的节点最复杂. 为了管理删除操作的复杂度, 我们使用递归操作, 同时定义两个方法: remove()和removeNode().

删除节点的第一步是判断当前节点是否包含带删除的数据.
如果包含, 则删除节点;
如果不包含, 则比较当前节点上的数据和待删除的数据

如果待删除数据小于当前节点上的数据, 则移至当前节点的左子节点继续比较;
如果待删除数据大于当前节点上的数据, 则移至当前节点的右子节点继续比较;

如果待删除节点是叶子节点(没有子节点的节点), 那么只需要将从父节点指向它的链接指向null.

如果待删除节点只包含一个子节点, 那么原本指向它的节点就得做些调整, 使其指向它的子节点.

最后, 如果待删除节点包含两个子节点, 正确的做法有两种:

查找待删除节点左子树上的最大值.
查找待删除节点右子树的最小值.

这里我们选择后一种方式

我们需要一个查找子树最小值的方法getSmallest(), 后面会用它找到最小值创建一个临时节点. 将临时节点上的值复制到待删除节点, 然后再删除临时节点.

整个删除过程由两个方法完成. remove()方法只是简单地接受待删除数据, 调用removeNode()删除它, 后者才是完成主要工作的方法.

window.log = console.log.bind(console)

class Node {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
    show() {
        return this.data;
    }
};

class BST {
    constructor() {
        this.root = null;
    }
    getMin() {
        let current = this.root;
        while (current.left !== null) {
            current = current.left;
        };

        return current.data;
    }
    getMax() {
        let current = this.root;
        while (current.right !== null) {
            current = current.right;
        };

        return current.data;
    }
    find(data) {
        let current = this.root;
        while (current !== null) {
            if (current.data === data) {
                return current;
            } else if (data < current.data) {
                current = current.left;
            } else if (data > current.data) {
                current = current.right;
            }
        };

        return null;
    }
    remove(data) {
        this.root = removeNode(this.root, data);
    }
    insert(data) {
        const n = new Node(data);
        
        if(this.root === null) {
            this.root = n;
        } else {
            let current = this.root;
            let parent;
            while(true) {
                parent = current;
                if(data < current.data) {
                    current = current.left;
                    if(current === null) {
                        parent.left = n;
                        break;
                    }
                } else {
                    current = current.right;
                    if(current === null) {
                        parent.right = n;
                        break
                    }
                }
            }
        }
    }
    
};

function inOrder(node) {
    if (node !== null) {
        inOrder(node.left);
        log(node.show() + ' ')
        inOrder(node.right)
    }
};
function preOrder(node) {
    if (node !== null) {
        log(node.show() + ' ');
        preOrder(node.left);
        preOrder(node.right);
    }
};
function postOrder(node) {
    if (node !== null) {
        postOrder(node.left);
        postOrder(node.right);
        log(node.show() + ' ');
    }
};
function removeNode(node, data) {
    if (node === null) {
        return null;
    };
    if (data === node.data) {
        // 没有子节点的节点
        if (node.left === null && node.right === null) {
            return null;
        };
        // 没有左子节点的节点
        if (node.left === null) {
            return node.right;
        };
        // 没有右子节点的节点
        if (node.right === null) {
            return node.left;
        };
        // 有两个子节点的节点
        const tempNode = getSmallest(node.right);
        node.data = tempNode.data;
        node.right = removeNode(node.right, tempNode.data);
        return node;
    } else if (data < node.data) {
        node.left = removeNode(node.left, data);
        return node;
    } else {
        node.right = removeNode(node.right, data);
        return node;
    }
}

计数

BST的一个用途是记录一组数据集中数据出现的次数. 比如, 可以使用BST记录考试成绩的分布. 给定一组考试成绩, 可以写一段程序将它们加入一个BST, 如果某成绩尚未在BST中出现, 就将其加入BST; 如果已经出现, 就将出现的次数加1;

为了解决该问题, 我们来修改Node对象, 为其增加一个记录成绩出现频次的成员, 同时我们还需要一个方法, 当在BST中发现某成绩时, 需要将出现的次数加1, 并且更新该节点.

先修改Node对象的定义, 为其增加记录成绩出现次数的成员:

class Node {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.count = 1;
        this.left = left;
        this.right = right;
    }
    show() {
        return this.data;
    }
};

当向BST插入一条成绩(Node对象)时, 将出现频次设为1. 此时BST的insert()方法还能正常工作, 但是, 当次数增加时, 我们就需要一个新方法来更新BST中的节点. 这个方法就是update().

完整程序:

window.log = console.log.bind(console)

class Node {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.count = 1;
        this.left = left;
        this.right = right;
    }
    show() {
        return this.data;
    }
};

class BST {
    constructor() {
        this.root = null;
    }
    getMin() {
        let current = this.root;
        while (current.left !== null) {
            current = current.left;
        };

        return current.data;
    }
    getMax() {
        let current = this.root;
        while (current.right !== null) {
            current = current.right;
        };

        return current.data;
    }
    find(data) {
        let current = this.root;
        while (current !== null) {
            if (current.data === data) {
                return current;
            } else if (data < current.data) {
                current = current.left;
            } else if (data > current.data) {
                current = current.right;
            }
        };

        return null;
    }
    update(data) {
        const grade = this.find(data);
        grade.count++;

        return grade;
    }
    remove(data) {
        this.root = removeNode(this.root, data);
    }
    insert(data) {
        const n = new Node(data);
        
        if(this.root === null) {
            this.root = n;
        } else {
            let current = this.root;
            let parent;
            while(true) {
                parent = current;
                if(data < current.data) {
                    current = current.left;
                    if(current === null) {
                        parent.left = n;
                        break;
                    }
                } else {
                    current = current.right;
                    if(current === null) {
                        parent.right = n;
                        break
                    }
                }
            }
        }
    }
    
};

function inOrder(node) {
    if (node !== null) {
        inOrder(node.left);
        log(node.show() + ' ')
        inOrder(node.right)
    }
};
function preOrder(node) {
    if (node !== null) {
        log(node.show() + ' ');
        preOrder(node.left);
        preOrder(node.right);
    }
};
function postOrder(node) {
    if (node !== null) {
        postOrder(node.left);
        postOrder(node.right);
        log(node.show() + ' ');
    }
};
function removeNode(node, data) {
    if (node === null) {
        return null;
    };
    if (data === node.data) {
        // 没有子节点的节点
        if (node.left === null && node.right === null) {
            return null;
        };
        // 没有左子节点的节点
        if (node.left === null) {
            return node.right;
        };
        // 没有右子节点的节点
        if (node.right === null) {
            return node.left;
        };
        // 有两个子节点的节点
        const tempNode = getSmallest(node.right);
        node.data = tempNode.data;
        node.right = removeNode(node.right, tempNode.data);
        return node;
    } else if (data < node.data) {
        node.left = removeNode(node.left, data);
        return node;
    } else {
        node.right = removeNode(node.right, data);
        return node;
    }
};

// 产生随机成绩
function genArray(length) {
    const arr = [];
    for(let i = 0; i < length; i++) {
        arr[i] = Math.floor(Math.random() * 101);
    };
    return arr;
};

const grades = genArray(100);
log(grades);

const bst = new BST();
grades.forEach(i => {
    const grade = bst.find(i);
    if (grade) {
        bst.update(i)
    } else {
        bst.insert(i)
    }
});

const aGrade = bst.find(33);
if (aGrade) {
    log(`33出现的次数为: ${aGrade.count}`)
} else {
    log(`未出现33`)
}

输出:

(100) [19, 85, 71, 52, 80, 3, 84, 13, 32, 20, 35, 10, 61, 54, 11, 49, 17, 6, 52, 66, 28, 7, 83, 71, 69, 84, 3, 2, 61, 12, 38, 97, 94, 10, 44, 14, 4, 69, 17, 10, 0, 28, 46, 74, 74, 18, 69, 70, 33, 32, 75, 81, 75, 52, 51, 34, 74, 75, 74, 0, 89, 71, 21, 28, 71, 42, 37, 92, 24, 39, 64, 75, 87, 46, 66, 37, 85, 55, 85, 21, 44, 16, 8, 81, 92, 72, 16, 4, 69, 32, 37, 48, 54, 91, 80, 57, 70, 88, 55, 32]
33出现的次数为: 1

数据结构二叉查找树查找算法 em

安科网

数据结构-二叉树和二叉查找树

lickylin

树的定义

二叉树和二叉查找树

实现二叉查找树

遍历二叉查找树

在二叉查找树上进行查找

查找最小值和最大值

查找给定值

从二叉查找树上删除节点

计数

lickylin

相关推荐

详解Redis数据结构之跳跃表

数据结构第7章小结

数据结构之利用PHP实现二分搜索树

泛型和元编程的模型：Java, Go, Rust, Swift, D等

万能Python的秘诀：操纵数据的内置工具

Java实现单链表、栈、队列三种数据结构

Map和Set两种数据结构在ES6的作用

「算法与数据结构」带你看回溯算法之美

比较JavaScript中的数据结构（数组与对象）

学c++需要先学c语言吗？

动图演示：手撸堆栈的两种实现方法！

技术人员思维和认知升级

python的链表基础知识点

数据结构 4

HBase/TiDB都在用的数据结构：LSM Tree，不得了解一下？

编写更简洁的Python代码的5个技巧

盘点 Python 10 大常用数据结构（下篇）

盘点 Python 10 大常用数据结构（上篇）

图解！24张图彻底弄懂九大常见数据结构！原创 Amazing10 业余码农 5月24日

什么是hash?

lickylin