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

lindroid 发布于2019-08-23 12:15 / 2006人阅读

摘要：树是计算机科学中经常用到的一种数据结构数是一种非线性的数据结构以分层的方式存储数据数被用来存储具有层级关系的数据比如文件系统中的文件树还被用来存储有序列表本章将研究一种特殊的树二叉树选择树而不是那些基本的数据结构是因为在二叉树上进行查找非常

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

树的定义

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

二叉树和二叉查找树

正如前面提到的那样, 二叉树 每一个节点的子节点不允许超过两个. 通过将子节点的个数限定为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

云服务器 GPU云服务器 c语言二叉树输入数据二叉树遍历二叉树创建二叉树算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/98181.html

一篇文章学会二叉树和二叉查找树

摘要：二叉树和二叉查找树一个父节点的两个子节点分别称为左节点和右节点。下图展示了一颗二叉树当考虑某种特殊的二叉树，比如二叉查找树时，确定子节点非常重要。实现二叉查找树定义对象。现在可以创建一个类来表示二叉查找树。因此二叉查找树也被叫做二叉排序树。树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构，以分层的方式存储数据。树被用来存储具有层级关系的数据，比如文件系统中的文件。 ...

BaronZhang 2019-08-26 13:46 评论0 收藏0
JavaScript数据结构与算法（九）二叉树和二叉搜索树

摘要：二叉树和二叉搜索树二叉树的节点最多只能有两个节点，而二叉搜索树只允许在左侧的节点处存储比父节点小的值，在右侧节点存储比父节点大的值。接收回调函数作为参数先序遍历先序遍历是以优先于后代节点的顺序访问没和节点的。树是一种非顺序数据结构，对于存储需要快速查找的数据非常有用。树是一种分层数据的抽象模型，现实生活中最常见的例子就是家谱，或者是公司的组织架构图。树树的相关术语 showImg...

zhaofeihao 2019-08-26 14:06 评论0 收藏0
每周一练之 数据结构与算法（Tree）

摘要：假设一个二叉搜索树具有如下特征节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。代码实现二叉树节点定义来源验证二叉搜索树解析 showImg(https://segmentfault.com/img/remote/1460000019005270); 这是第六周的练习题，最近加班比较多，上周主要完成一篇 GraphQL入门教程，有兴趣的小伙伴可以看下哈。 ...

zhonghanwen 2019-08-26 13:51 评论0 收藏0
每周一练之 数据结构与算法（Tree）

摘要：假设一个二叉搜索树具有如下特征节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。代码实现二叉树节点定义来源验证二叉搜索树解析这是第六周的练习题，最近加班比较多，上周主要完成一篇 GraphQL入门教程，有兴趣的小伙伴可以看下哈。下面是之前分享的链接： 1.每周一练之数据结构与算法（Stack） 2.每周一练之数据结构与算法（LinkedList） 3...

fizz 2019-05-22 11:25 评论0 收藏0