树的定义
数据结构中的树结构和我们现实中的树非常类似,学习的时候完全可以进行类比学习
数据结构中的树
,把现实中树
的根抽象为根结点
,树枝抽象为边
,树枝的两个端点抽象为结点
,树叶抽象为叶子结点
,然后整体在整体翻转180度,就得到了数据结构中的树
。
除此之外,树还有以下几个概念高度
,深度
,层
一图胜过千言万语
对着图看文字解释,加深理解
- 高度 节点到叶子节点
最长路径
- 深度 根节点到这个节点所经历
边的个数
- 层 深度+1
什么是二叉树
很好理解,每个节点 最多 有两个"叉"的树就是二叉树。其中,二叉树又分为 满二叉树 和 完全二叉树
- 满二叉树
叶子节点全都在最底层,除了叶子节点之外,每个节点都有左右两个子节点
- 完全二叉树
叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大
一图胜过千言万语
其中我们把 左子树上所有结点的数据域都小于等于根结点的数据域,右子树上所有结点的数据域都大于等于根结点的数据域 的二叉树称之为二叉搜索树
一图胜过千言万语
使用javascript
实现二叉搜索树
在写代码之前我们先分析下二叉搜索树
这种数据结构的特点如何使用编程思想表达出来
- 首先我们需要一个创建节点的
类
,并且每个节点都有left
和right
属性及自身存放的数据key
function Node(data){
this.key = data;
this.left=null; // 左节点
this.right=null; // 右节点
}
递归遍历
整棵树,找到需要插入数据对应的地方
情况1: 如果为空树直接插入
情况2: 逐层递归遍历节点,把小数插入到最左边,大数插入到最右边
开始撸代码(注释已给出)
function searchTree() {
// 树的节点
function Node(data) {
this.key = data;
this.left = null;
this.right = null;
}
//定义树的根节点
this.root = null;
//插入方法
searchTree.prototype.inster = function (key) {
const newNode = new Node(key);
// 如果是空树,直接把当前值赋值给root
if (this.root === null) {
this.root = newNode;
} else {
this.insterNode(this.root, newNode);
}
};
searchTree.prototype.insterNode = function (node, newNode) {
// todo 递归查找当前数据应该在的位置
if (newNode.key > node.key) {
// 把新节点放到最右边
if (node.right === null) {
node.right = newNode;
} else {
this.insterNode(node.right, newNode);
}
} else {
// 把新节点放到左端
if (node.left === null) {
node.left = newNode;
} else {
this.insterNode(node.left, newNode);
}
}
};
}
二叉搜索树的遍历
为什么要遍历?
遍历就是为了按照某种顺序获得到全部数据,其中二叉搜索树本身就是按照顺序存储数据的,所以遍历二叉搜索树更有实际意义
按照根结点
的输出位置,遍历又大致可以分为以下几种
- 先序遍历
- 中序遍历
- 后序遍历
一图胜过千言万语
使用javascript
实现二叉搜索树遍历
先序遍历
// handler用于接收处理遍历数据的函数
searchTree.prototype.Preorder = function (handler) {
this.preOrderNode(this.root, handler);
};
searchTree.prototype.preOrderNode = function (node, handler) {
if (node != null) {
handler(node.key); // 先序
this.preOrderNode(node.left, handler);
this.preOrderNode(node.right, handler);
}
};
中序遍历
// handler用于接收处理遍历数据的函数
searchTree.prototype.Middle = function (handler) {
this.preOrderNode(this.root, handler);
};
searchTree.prototype.MiddleNode = function (node, handler) {
if (node != null) {
this.preOrderNode(node.left, handler);
handler(node.key); // 中序
this.preOrderNode(node.right, handler);
}
};
后序遍历
// handler用于接收处理遍历数据的函数
searchTree.prototype.After = function (handler) {
this.preOrderNode(this.root, handler);
};
searchTree.prototype.AfterNode = function (node, handler) {
if (node != null) {
this.preOrderNode(node.left, handler);
this.preOrderNode(node.right, handler);
handler(node.key); // 后序
}
};
测试
let s = new searchTree();
s.inster(10);
s.inster(8);
s.inster(7);
s.inster(6);
s.inster(12);
s.inster(14);
//中序遍历
s.Middle(function (val) {
console.log(val);
});
console.log(s);
结果
可以看出,中序遍历正好是数据从大到小排序好的结果
理解二叉平衡树(红黑树)
为什么会有平衡二叉树?
如果我们使用树结构存储这样一组数据1,2,3,4,5,6
如果这样的数据量非常大呢? 这时树的深度
就会变的非常深,对应的递归遍历
整个树的效率就会变的比较低,所有我们需要引入平衡因子
什么是平衡二叉树
二叉树中任意一个节点的左右子树的高度相差不能大于 1 其中1
可以理解为最优结果,也就是说,树的左右节点存放的数据基本相等,这个时候可以保证树的深度
最小,效率最高
红黑树是怎样做到自平衡的
首先说说红黑树的性质
- 性质1:每个节点要么是黑色,要么是红色。
- 性质2:根节点是黑色。
- 性质3:每个叶子节点是黑色。
- 性质4:每个红色结点的两个子结点一定都是黑色。
- 性质5:任意一结点到每个叶子结点的路径都包含数量相同的黑
红黑树只要时刻满足这些约束,就可以达到自平衡,其中自平衡常见的操作有变色
,左旋转
,右旋转
,实现原理也比较复杂,在这里就不进行源码实现了
其他方法实现
上面我们实现了二叉搜索树的插入和遍历,还有在树中查找一个键
,查找最大值,最小值
,从树中移除某个键
等方法在文章中没有实现,完整的源码已经放到github,感兴趣的可以自取研究哦
最后
吃不了学习的苦,就要吃生活的苦
如果此文对你有帮助,记得点赞关注哦?
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用?
- 本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了?
- 找不到素材资源介绍文章里的示例图片?
- 模板不会安装或需要功能定制以及二次开发?
发表评论
还没有评论,快来抢沙发吧!