二叉树

本文引用至: 二叉树

树, 实际上是一个非常重要的数据结构, 比如,我们的进程树,文件树,HTML节点树等. 都是依赖这样的一个结构. 树,实际上是一种非线性的数据结构,但是他们是有序的. 如下图

每一个节点下面,都有本身的value,parent_node,child_node属性(除了根节点).

树的基本概念

每颗树都有根节点,叶子节点, 子节点,父节点的属性. 如果按 树组分的话, 还可分为子树等. 可以看一下下面这张图, 详细的阐述了基本的概念:

这里,我们先从简单的开始, 先了解一下 binary tree(二叉树)

二叉树基本内容

二叉树不同于基本的树: 他的基本性质如下:

  1. 每个节点只有两个子节点

  2. 每个子节点分为左子节点和右子节点

  3. 左子节点在索引顺序时优于右子节点

但是映射到数据结构中,我们怎么区分左右节点. 这里我们可以定义一个规则:

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

  2. 右节点的值,比父节点和左子节点都大(这条很重要)

基于这条规则,我们就可以创建一个二叉树. 二叉树,实际上就是有linked list组成的二维树. 但他不同于linked list , 该是一种非线性的结构。 所以, 他的插入方式,也是非线性的. 我们通常将该种方式查找树叫做,Binary search tree(BST). 我们可以使用代码进行模拟一下:
首先,我们得定义一个节点类:

  1. value: 节点的值

  2. left_child: 左子节点

  3. right_child: 右子节点

class Node {    constructor(value, left, right) {        this.value = value;        this.left_child = left;        this.right_child = right    }}

我们基本的BST 应该具有的方法有: add, find. 这里, 我们先模拟一下, 如果将数据插入二叉树中:

class BST {    constructor(root) {        this.root = root;    }    add(value) {        let new_node = new Node(value, null, null),            parent = this.root;        while (true) {            if (parent.value === null) {                parent = new_node;                break;            } else {                if (parent.value > value) {                    if(parent.left_child==null){                        parent.left_child = new_node;                        break;                    }                }else{                    if(parent.right_child == null){                        parent.right_child = new_node;                        break;                    }                }            }        }    }}

现在, 我们已经存放了一些值. 那怎样去获取他呢?
常用的方法有, 中序, 先序, 后序 三种方法.

  1. 中序(in-order): 先以递归的形式访问左子树,然后再访问根节点, 最后访问右子树. 而隐含其中的关系就是: 由小到大的访问. 所以中序是遍历方法中唯一一个有顺序的.

  2. 先序(Pre-order): 先访问根节点, 然后以递归的方式访问左子树和右子树

  3. 后序(Post-order): 先以递归的方式访问左子树和右子树, 最后访问根节点.

上面的叙述,感觉有点干. 我们借助wiki提供的图,进行简单的讲解,方便理解遍历的具体过程.
这里,我们使用一种绕线法,跟着线的顺序, 接触一个点,表示被遍历到.

  1. 先序 : 线与左边相接触

  2. 中序 : 线与底边相接触

  3. 后序 : 线与右边相接触

现在,我们用代码来模拟一下中序遍历:

in_order(node){        if(node!==null){            this.in_order(node.left_child);            console.log(node.value);            this.in_order(node.right_child);        }    }

这里,利用了递归的写法, 因为二叉树本身的结构也是属于一种深层次数据结构. 只要靠自身的递归,这样才能不断的找到最里面那一层. 这样做虽然, 有点耗费内存, 但时间节省成本是相当大的.
那先序以及后序的写法,就很简单了.
先序: 根+左子树+右子树

pre_order(node) {        if (node !== null) {            console.log(node.value);            this.pre_order(node.left_child);            this.pre_order(node.right_child);        }    }

后序: 左子树+ 右子树 + 根

post_order(node){    if(node!==null){            this.in_order(node.left_child);            this.in_order(node.right_child);            console.log(node.value);        }}

是不是很简单嘞? en. 看起来是的.
但 往往看起来很简单的,深层次都是复杂的一逼.

二叉树的相关性质

接下来, 我们通过 二叉查找树的查找内容,来探究二叉树的相关性质. 首先, 我们已经清楚

  1. 右节点> 父节点 > 左节点

首先, 我们来找一下二叉树的最小值. 推理一下, 当只有3个节点的时候, 那么最小值在左节点, 当有7 个节点时, 最小是还在左节点. 后面就不推了, 这里我们就假定最小值就在树的左下节点.
聪明的童鞋, 应该知道是什么意思, 自己看看我们插入的原理应该就清楚了.

现在我们来找一下最小值(左子节点). 方法很简单,还是用递归.
(这里使用的nodeJS 6.x版本添加的默认参数特性)

    constructor(root) {        this.root = root;        this.min;        this.max;    }    min(node = this.root) {        if (node.left_child !== null) {            // 递归遍历左节点            this.min(node.left_child);        } else {            this.min = node.value;        }        return this.min;    }

同理, 最大值就是树的右下节点:

max(node = this.root) {        if (node.right_child !== null) {            // 递归遍历右节点            this.max(node.right_child);        } else {            this.max = node.value;        }        return this.max;    }

现在,我们有3条关于二叉树的性质:

  1. 右节点> 父节点 > 左节点

  2. 所有右子树 > 根节点 > 左子树

  3. 最小值是左叶子节点, 最大值是右叶子节点

接着,我们来在二叉树上查找给定的值:
由于上述性质我们可以知道, 二叉树实际上就是一个完美的二分法实验苗圃. 可以看一个总结图:

首先给你一个值, 在和根节点比较, 如果小则直接和左子树进行比较, 如果大则直接和右子树进行比较. 一次类推, 所以, 二叉树找数据是灰常快的. 不过, 我们这里就不用递归了, 使用循环来描述一下(因为简单的递归都可以使用循环来描述):

    find(value, node = this.root) {        while (true) {            if(node === null){                // 如果节点为空,返回null                return null;            }else if(node.value===value){                // 找到对应的值并返回                return node;            }else if(node.value > value){                // 查找左子节点                node = node.left_child;            }else{                // 查找右子节点                node = node.right_child;            }        }    }

接下来, 又到打Boss 环节. 删除节点. 首先, 我们必须记住树的原则, 再来一遍:

  1. 右节点> 父节点 > 左节点

删除二叉树的情况,可以分为三种:

  1. 没有子节点: 直接删除, over

  2. 有一个节点: 用父节点指向节点,over

  3. 有两个节点: 用父节点,指向右子树节点,并且左节点放到右子树的左叶子节点.

有童鞋可能会问了. 需不需要考虑一下,有没有子树呢?
考虑个屁~
因为二叉树就是一个链式结构, 你只要移动父节点就可以了(即, 只要管一个节点).但当向链表的删除结构就比较复杂, 这里同样需要补充一个查找父节点的方法. 并且, 你还需要知道该节点相对于父节点而言是左还是右, 这就比较尴尬了:

        child_contain(node, value) {        if (node.left_child !== null) {            if (node.left_child.value === value) {                return [true, 'left'];            }        }        if (node.right_child !== null) {            if (node.right_child.value === value) {                return [true, 'right']            }        }        return [false, 'null']    }    findParent(value, node = this.root) {        let has, child;        while (true) {            if (node === null) {                // 如果节点为空,返回null                return null;            }           [has,child] = this.child_contain(node, value)            if (has) {                // 找到父节点                return [node, child]            } else {                // 没有则继续遍历                if (node.value > value) {                    // 查找左子节点                    node = node.left_child;                } else {                    // 查找右子节点                    node = node.right_child;                }            }        }    }

有了上述两个方法之后, 我们就可以开始真正的删除节点了. 情况还是上述3种:

    remove(value) {        // 找到删除节点        let node = this.find(value),            [parentNode, child] = this.findParent(value),            tmp; // 临时节点        //找到删除节点的父节点        if (node === null) {            // 节点不存在            return null;        }        if (node.left_child === null && node.right_child === null) {            // 没有子节点            parentNode[child] = null;        } else {            if (node.left_child === null) {                // 左子节点为空                parentNode[child] = node.right_child;            } else if (node.right_child === null) {                // 右子节点为空                parentNode[child] = node.left_child;            } else {                //子节点都不为空                // 找到右子树最小的节点位置                tmp = this.min(node.right_child);                tmp.left_child = node.left_child;                parentNode[child] = node.right_child;                // 解除引用                node.left_child = null;                node.right_child = null;            }        }        return node.value;    }

所有的程序放在JSFiddle中, 欢迎参考
现在,关于二叉树的基本内容,差不多详述完了. 不过,还有一个痛点还没有解决, 二叉树能不能存放相同的数据.
通常的答案是不行. 因为这样将会增大BST所有方法的复杂度. 如果你想弥补一个bug, 可以在Node 类中,添加一个count 统计重复出现的次数.

class Node {    constructor(value, left, right) {        this.value = value;        this.left_child = left;        this.right_child = right        this.count = 1;    }}

其他方法 留个读者们去完成吧

最后的最后,总结一下:

关键字:数据结构, bst, 二叉树, node

版权声明

本文来自互联网用户投稿,文章观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符,请点击 举报 进行投诉反馈!

立即
投稿

微信公众账号

微信扫一扫加关注

返回
顶部