JS数据结构与算法 - 二叉树（一）基本算法
2024-10-08 21:35:47
仅供JavaScript刷题参考用。
二叉查找树和平衡二叉树
其它树：满二叉树、完全二叉树、完美二叉树、哈弗曼树、二叉查找树BST、平衡二叉树AVL
了解：红黑树，是一种特殊的二叉树。这种树可以进行高效的中序遍历
建立
创建BinarySearchTree类。首先，声明它的结构：
（注意，BinarySearchTree是个类，后面所有函数都定义在该结构体内）
function BinarySearchTree() {
//私有的辅助函数
var Node = function(key){
this.key = key;
this.left = null;
this.right = null;
};
//声明一个私有变量以控制此数据结构的第一个节点。在树中，它不是头节点，而是根元素
var root = null;
}
插入
this.insert = function(key){
var newNode = new Node(key);
if (root === null){
root = newNode;
} else {
insertNode(root,newNode);
}
};
// 私有的辅助函数
var insertNode = function (node, newNode) {
if (newNode.key < node.key) {
if (node.left === null) {
node.left = newNode;
} else {
insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
insertNode(node.right, newNode);
}
}
};
删除
this.remove = function (key) {
root = removeNode(root, key);
};
var removeNode = function (node, key) {
if (node === null) {
return null;
}
if (key < node.key) {
node.left = removeNode(node.left, key);
return node;
} else if (key > node.key) {
node.right = removeNode(node.right, key);
return node;
} else { //键等于node.key
//第一种情况——一个叶节点
if (node.left === null && node.right === null) {
node = null;
return node;
}
//第二种情况——一个只有一个子节点的节点
if (node.left === null) {
node = node.right;
return node;
} else if (node.right === null) {
node = node.left;
return node;
}
//第三种情况——一个有两个子节点的节点
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right, aux.key);
return node;
}
};
查找
this.search = function (key) {
return searchNode(root, key);
};
var searchNode = function (node, key) {
if (node === null) {
return false;
}
if (key < node.key) {
return searchNode(node.left, key);
} else if (key > node.key) {
return searchNode(node.right, key);
} else {
return true;
}
};
寻找最大值
this.max = function () {
return maxNode(root);
};
var maxNode = function (node) {
if (node) {
while (node && node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
};
寻找最小值
this.min = function () {
return minNode(root);
};
var minNode = function (node) {
if (node) {
while (node && node.left !== null) {
node = node.left;
}
return node.key;
}
return null;
};
遍历
✔先序
this.preOrderTraverse = function (callback) {
preOrderTraverseNode(root, callback);
};
var preOrderTraverseNode = function (node, callback) {
if (node !== null) {
callback(node.key);
preOrderTraverseNode(node.left, callback);
preOrderTraverseNode(node.right, callback);
}
};
✔中序
this.inOrderTraverse = function (callback) {
inOrderTraverseNode(root, callback);
};
var inOrderTraverseNode = function (node, callback) {
if (node !== null) {
inOrderTraverseNode(node.left, callback);
callback(node.key);
inOrderTraverseNode(node.right, callback);
}
};
✔后序
this.postOrderTraverse = function (callback) {
postOrderTraverseNode(root, callback);
};
var postOrderTraverseNode = function (node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback);
postOrderTraverseNode(node.right, callback);
callback(node.key);
}
};
✔深度优先（DFS)
在二叉树中，DFS就相当于先序遍历
✔广度优先（BFS）/层次遍历
利用队列来模拟，就很容易了
this.bfsTraverse = function (callback) {
bfsTraverseNode(root, callback)
}
var bfsTraverseNode = function (root, callback) {
var queue = []
if(root){
queue.push(root)
}
while(queue.length){
var node = queue.shift()
callback(node.key)
if(node.left){
queue.push(node.left)
}
if(node.right){
queue.push(node.right)
}
}
}
线索化二叉树
最新文章
- JS中使用MD5加密
- Home 安转beta版软件
- OstrichNet 简易统计信息收集工具
- jquery mobile 实现自定义confirm确认框效果
- 格式化Double类型
- 转：JQuery选择器
- 【iCore3 双核心板】例程二十六：MODBUS TCP实验——电源监控
- Sencha Touch 2.2.1 Custom Icon 自定义图标
- iOS-实现验证码倒计时功能（1）
- http://www.cnblogs.com/doit8791/p/4093808.html
- PowerDesigner 物理数据模型（PDM）
- 读取Excel数据绑定到Gridview进行显示
- SVD在推荐系统中的应用
- 安卓平台多个视频叠加演示demo说明
- 【SSH项目实战三】脚本密钥的批量分发与执行
- Struts 2.5 Filter mapping specifies an unknown filter name [struts2]
- Vuejs实例-使用vue-cli创建项目
- ●BZOJ 2442 [Usaco2011 Open]修剪草坪
- spring MVC，controller中获得resuqest和response的方式
- Django——photo