JavaScript--数据结构与算法之二叉树
2024-08-31 17:29:39
树是一种非线性的数据结构，以分层的方式存储数据。
二叉树：查找非常快，而且二叉树添加或者删除元素也非常快。
形象的可以描述为组织结构图，用来描述一个组织的结构。树是由边连接的点组成。
树的一些基本概念：
根节点：一棵树最上面的节点。
父节点：一个节点下面连接多个节点，该节点是父节点。
子节点：父节点下面的节点。（一个节点可以有0，1，或者多个子节点）
叶子节点：没有任何子节点的节点。
路径：从一个节点到另一个节点的这一组边。
树的遍历：以某种特定顺序访问树中所有的节点。
树的分层：根节点是0层，它的子节点是第一层以此类推。
树的深度：书的层数就是深度。
键：每个节点都有一个与之相关的值。
二叉树和二叉查找树
二叉树：一种特殊的树，子节点不超过两个将子树节点的个数限定为2，可以写出高效的程序在树中插入、查找、删除数据。
左右节点：父节点的两个子节点。
二叉查找树：是一种特殊的二叉树，相对较小的节点存在左节点，较大的存在右节点。这一特性是的查找的效率很高。
1、实现二叉查找树：
又节点组成，定义的第一个对象是Node,和链表的Node对象相似。
Node对象既能保存保存数据，也能保存和其他节点链接（left,right）,show()用来显示保存在节点中的数据。
function Node(data,left,right) {
this.data = data;
this.left = left;
this.right = right;
//this.show = show;
}
Node.prototype.show = function() {
return this.data;
};
二叉树的创建：binary search tree
二叉树的创建：binary search tree
该类只有一个数据成员，表示二叉树查找树根节点的Node对象，初始化null;
BST有一个insert()方法，用来插入新节点，有点复杂，首先创建一个Node对象，将对象传入该数据中。检查BST是否有根结点，如果没有则是新树，该节点是根节点。否则待插入节点不是根节点，需要遍历BST，找到插入的适当位置。该过程类似与遍历链表。用一个变量存储当前结点，一层层地遍历BST。进入BST以后，下一步就是决定将节点放在什么地方，找到正确的插入点。
1）设置根节点为当前节点。
2）如果待插入节点保存的数据小于当前节点，则设置新的当前节点为原节点的左节点；反之4）
3）如果当前节点的左节点为null，就将新的节点插入这个位置，退出循环；反之执行下一次循环。
4）设置新的当前节点为原节点的右节点。
5）如果当前节点的右节点为null，就将新的节点插入这个位置，推出循环；反之执行下一次循环；
function BST() {
this.root = null;
//this.insert = insert;
this.preOrder = preOrder;//先序遍历
this.inOrder = inOrder;//中序遍历
this.postOrder = postOrder;//后序遍历
}
BST.prototype.insert = function(data) {
var _node = new Node(data,null,null);
if(this.root == null) {
this.root = _node;
}else{
var _current = this.root;
var _parent;
while(true) {
_parent = _current;
if(data < _current.data) {
_current = _current.left;
if(_current == null) {
_parent.left = _node;
break;
}
}else{
_current = _current.right;
if(_current == null) {
_parent.right = _node;
break;
}
}
}
}
};
2、遍历二叉树
方式：先序，中序，后序。（都是以根为参照访问）
先序：先访问根节点，再以升序的方式访问左子树和右子树。
中序：以升序的方式访问左中右的次序。
后序：先访问叶子节点，从左子树到右子树再到根节点。
//先序遍历preOrder
function preOrder (node) {
if(!(node == null)) {
console.log(node.show());
preOrder(node.left);
preOrder(node.right);
}
}
//test...
var bst = new BST();
bst.insert(23);
bst.insert(45);
bst.insert(16);
bst.insert(37);
bst.insert(3);
bst.insert(99);
bst.insert(22);
preOrder(bst.root);
//中序遍历inOrder
function inOrder (node) {
if(!(node == null)) {
inOrder(node.left);
console.log(node.show());
inOrder(node.right);
}
}
console.log("--------------------");
inOrder(bst.root);
//后序遍历inOrder
function postOrder (node) {
if(!(node == null)) {
postOrder(node.left);
postOrder(node.right);
console.log(node.show());
}
}
console.log("--------------------");
postOrder(bst.root);
//完整代码：
~(function() {
function Node(data,left,right) {
this.data = data;
this.left = left;
this.right = right;
//this.show = show;
}
Node.prototype.show = function() {
return this.data;
};
function BST() {
this.root = null;
//this.insert = insert;
this.preOrder = preOrder;//先序遍历
this.inOrder = inOrder;//中序遍历
this.postOrder = postOrder;//后序遍历
}
BST.prototype.insert = function(data) {
var _node = new Node(data,null,null);
if(this.root == null) {
this.root = _node;
}else{
var _current = this.root;
var _parent;
while(true) {
_parent = _current;
if(data < _current.data) {
_current = _current.left;
if(_current == null) {
_parent.left = _node;
break;
}
}else{
_current = _current.right;
if(_current == null) {
_parent.right = _node;
break;
}
}
}
}
};
//先序遍历preOrder
function preOrder (node) {
if(!(node == null)) {
console.log(node.show());
preOrder(node.left);
preOrder(node.right);
}
}
//中序遍历inOrder
function inOrder (node) {
if(!(node == null)) {
inOrder(node.left);
console.log(node.show());
inOrder(node.right);
}
}
//后序遍历inOrder
function postOrder (node) {
if(!(node == null)) {
postOrder(node.left);
postOrder(node.right);
console.log(node.show());
}
}
})();
3、二叉树上的查找：
1）查找最小值；
2）查找最大值；
3）查找给定值。
最大最小值的查找比较简单，只要遍历到最左，最右即可。
BST.prototype.getMin = function() {
var _current = this.root;
while(!(_current.left == null)) {
_current = _current.left;
}
return _current.data;
};
BST.prototype.getMax = function () {
var _current = this.root;
while(!(_current.right == null)) {
_current = _current.right;
}
return _current.data;
};
console.log("-----------");
console.log( bst.getMin() );
console.log( bst.getMax() );
查找给定值：find(); 需要比较该值和当前节点上的值的大小。通过比较大小，确定左遍历还是右遍历。
BST.prototype.find = function(data) {
var _current = this.root;
while(_current != null) {
if(_current.data == data) {
return _current;
}else if(data < _current.data) {
_current = _current.left;
}else{
_current = _current.right;
}
}
return null;//没找到返回null
};
console.log("-----------");
console.log( bst.find(99) );
4、删除二叉查找树上的节点
删除操作相对复杂，分为三种情况
1）删除叶子节点（没有子节点的节点）
2）删除只有一个子节点
3）删除包含两个子节点
删除时要删除数据和删除节点。
算法具体过程：
先判断当前节点是否包含待删除的数据，如果包含则删除该节点。如果不包含则比较当前节点上的数据和待删除的数据(删除根节点)。如果不包含，则比较当前节点的数据和待删除的数据。如果待删除数据小于当前节点上的数据，则移至当前结点的左子树节点继续比较；如果大于当前节点上的数据，则移至当前节点的右子节点继续比较。
叶子节：只需要将从父节点指向它的链接指向null;
删除节点只包含一个子节点：原本只想他的节点就的做些调整，使其指向它的子节点。
删除包含两个子节点：一种是查找待删除节点左子树上的最大值，要么查找其右子树上的最小值。
这个过程有两个方法完成，一个删除数据remove();，一个删除节点removeNode();
function remove(data) {
root = removeNode(this.root,data);
}
function getSmallest(node) {
if (node.left == null) {
return node;
}else {
return getSmallest(node.left);
}
}
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;
}
//有两个子节点的节点
var _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.remove(3);
preOrder(bst.root);
//console.log( bst.show() );
最新文章
- Vsftp精解之安装配置及原理（一）
- 【CSU1808】地铁
- spring aop中的propagation的7种配置的意思
- 夺命雷公狗---Thinkphp----10之后台登录.注销一条龙
- 使用JAVA反射初始化数组（转）
- mysql select 报错
- sorted函数
- php 加密解密方法
- CareerCup它1.8 串移包括问题
- redis client protocol 分解
- Qt Quick里的图形效果：阴影（Drop Shadow）
- 编译安装 Nginx1.12.1
- R语言-时间序列
- c# try-finally有什么用
- 云摘录︱Word2Vec 作者Tomas Mikolov 的三篇代表作解析
- Kotlin基础
- 调试 - Chrome调试
- Oracle中connect by用法示例
- Multiple markers at this line - Missing semicolon时的解决方法
- 依据Axis2官网的高速入门英文文档总结