本文引用至: 二叉树
树, 实际上是一个非常重要的数据结构, 比如,我们的进程树,文件树,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){// 如果节点为空,返回nullreturn 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) {// 如果节点为空,返回nullreturn 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 = rightthis.count = 1;}
}其他方法 留个读者们去完成吧
最后的最后,总结一下：
