树
8.1 树的相关术语
- 位于树顶部的节点叫做根节点
- 内部节点(至少有一个子节点)和外部节点(没有子节点)
- 节点的深度，取决于它祖先节点的个数
- 树的高度取决于所有节点深度的最大值
- 键是树中对节点的称呼
8.2 二叉树和二叉搜索树
- 二叉树的节点最多只能有两个子节点
- 一个是左侧子节点
- 一个是右侧子节点
- ==有助于写出更高效的向树中插入，查找和删除节点的算法==
- 二叉搜索树是二叉树的一种
- 只允许在左侧节点存储比父节点小的值
- 在右侧节点存储比父节点大的值
// 创建二叉搜索树类
function BinarySearchTree() {
// 声明Node类来表示树中的每个节点
var Node = function (key) {
this.key = key;
this.left = null;
this.right = null;
};
// 根元素
var root = null;
/*
insert(key): 向树中插入一个新的键
search(key): 在树中查找一个键，存在返回true,否则false
inOrderTraverse: 通过中序遍历方式遍历所有节点
preOrderTraverse: 通过先序遍历方式遍历所有节点
postOrderTraverse:通过后序遍历方式遍历所有节点
min:返回树中最小的值/键
max:返回树中最大的值/键
remove(key):从树中移除某个键
*/
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);
}
}
};
// insert(key)
this.insert = function (key) {
var newNode = new Node(key);
if (root === null) {
root = newNode;
} else {
insertNode(root, newNode);
}
};
}
8.3 树的遍历
中序遍历就是从最小到最大的顺序访问所有节点。
应用于对树进行排序操作
this.inOrderTraverse = function(callback) {
inOrderTraverseNode(root, callback);
};
function inOrderTraverseNode(node, callback) {
if (node !== null) {
inOrderTraverseNode(node.left, callback);
callback(node.key);
inOrderTraverseNode(node.right, callback);
}
}
先序遍历是以优先于后代节点的顺序访问每个节点
应用于打印一个结构化的文档
this.preOrderTraverse = function (callback) {
preOrderTraverseNode(root, callback);
};
function preOrderTraverseNode(node, callback) {
if (node !== null) {
callback(node.key);
preOrderTraverseNode(node.left, callback);
preOrderTraverseNode(node.right, callback);
}
}
后序遍历是先访问节点的后代节点，再访问节点本身
应用于计算一个目录和它的子目录中所有文件所占空间的大小
this.postOrderTraverse = function (callback) {
postOrderTraverseNode(root, callback);
};
function postOrderTraverseNode(node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback);
postOrderTraverseNode(node.right, callback);
callback(node.key);
}
}
function printNode(val) {
console.log(val);
}
// 使用二叉搜索树类
var tree = new BinarySearchTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);
// 中序遍历，从小到大
// tree.inOrderTraverse(printNode);
// 先序遍历
// tree.preOrderTraverse(printNode);
// 后序遍历
tree.postOrderTraverse(printNode);
搜索树中的值
在树中，有三种经常执行的搜索类型
最大值、最小值、搜索特定的值
// 最小值
var minNode = function (node) {
if (node) {
while (node && node.left !== null) {
node = node.left
}
return node.key;
}
return null;
};
this.min = function () {
return minNode(root);
};
// 最大值
var maxNode = function (node) {
if (node) {
while (node && node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
};
this.max = function () {
return maxNode(root);
}
// 搜索一个特定的值
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.search = function (key) {
return searchNode(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, axu.key);
return node;
}
};
function findMinNode(node) {
if (node) {
while (node && node.left !== null) {
node = node.left;
}
return node;
}
return null;
}
this.remove = function (key) {
root = removeNode(root, key);
};
