二叉树
本文引用至: 二叉树
树, 实际上是一个非常重要的数据结构, 比如,我们的进程树,文件树,HTML节点树等. 都是依赖这样的一个结构. 树,实际上是一种非线性的数据结构,但是他们是有序的. 如下图
每一个节点下面,都有本身的value,parent_node,child_node属性(除了根节点).
树的基本概念
每颗树都有根节点,叶子节点, 子节点,父节点的属性. 如果按 树组分的话, 还可分为子树等. 可以看一下下面这张图, 详细的阐述了基本的概念:
这里,我们先从简单的开始, 先了解一下 binary tree(二叉树)
二叉树基本内容
二叉树不同于基本的树: 他的基本性质如下:
每个节点只有两个子节点
每个子节点分为左子节点和右子节点
左子节点在索引顺序时优于右子节点
但是映射到数据结构中,我们怎么区分左右节点. 这里我们可以定义一个规则:
相对较小的值保存在左节点中,较大的值保存在右节点中
右节点的值,比父节点和左子节点都大(这条很重要)
基于这条规则,我们就可以创建一个二叉树. 二叉树,实际上就是有linked list组成的二维树. 但他不同于linked list , 该是一种非线性的结构。 所以, 他的插入方式,也是非线性的. 我们通常将该种方式查找树叫做,Binary search tree(BST). 我们可以使用代码进行模拟一下:
首先,我们得定义一个节点类:
value: 节点的值
left_child: 左子节点
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; } } } } }}现在, 我们已经存放了一些值. 那怎样去获取他呢？
常用的方法有, 中序, 先序, 后序 三种方法.
中序(in-order): 先以递归的形式访问左子树,然后再访问根节点, 最后访问右子树. 而隐含其中的关系就是: 由小到大的访问. 所以中序是遍历方法中唯一一个有顺序的.
先序(Pre-order): 先访问根节点, 然后以递归的方式访问左子树和右子树
后序(Post-order): 先以递归的方式访问左子树和右子树, 最后访问根节点.
上面的叙述,感觉有点干. 我们借助wiki提供的图,进行简单的讲解,方便理解遍历的具体过程.
这里,我们使用一种绕线法,跟着线的顺序, 接触一个点,表示被遍历到.
先序 ： 线与左边相接触
中序 : 线与底边相接触
后序 : 线与右边相接触
现在,我们用代码来模拟一下中序遍历:
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. 看起来是的.
但 往往看起来很简单的,深层次都是复杂的一逼.
二叉树的相关性质
接下来, 我们通过 二叉查找树的查找内容,来探究二叉树的相关性质. 首先, 我们已经清楚
- 右节点> 父节点 > 左节点
首先, 我们来找一下二叉树的最小值. 推理一下, 当只有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条关于二叉树的性质:
右节点> 父节点 > 左节点
所有右子树 > 根节点 > 左子树
最小值是左叶子节点, 最大值是右叶子节点
接着,我们来在二叉树上查找给定的值:
由于上述性质我们可以知道, 二叉树实际上就是一个完美的二分法实验苗圃. 可以看一个总结图:
首先给你一个值, 在和根节点比较, 如果小则直接和左子树进行比较, 如果大则直接和右子树进行比较. 一次类推, 所以, 二叉树找数据是灰常快的. 不过, 我们这里就不用递归了, 使用循环来描述一下(因为简单的递归都可以使用循环来描述):
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 环节. 删除节点. 首先, 我们必须记住树的原则, 再来一遍:
- 右节点> 父节点 > 左节点
删除二叉树的情况,可以分为三种:
没有子节点: 直接删除, over
有一个节点: 用父节点指向节点,over
有两个节点: 用父节点,指向右子树节点,并且左节点放到右子树的左叶子节点.
有童鞋可能会问了. 需不需要考虑一下,有没有子树呢？
考虑个屁~
因为二叉树就是一个链式结构, 你只要移动父节点就可以了(即, 只要管一个节点).但当向链表的删除结构就比较复杂, 这里同样需要补充一个查找父节点的方法. 并且, 你还需要知道该节点相对于父节点而言是左还是右, 这就比较尴尬了:
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
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！