-
从左到右开始，左小，右大查看全部
-
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta http-equiv="X-UA-Compatible" content="ie=edge" />
<title>Document</title>
</head>
<body>
<script>
function BinaryTree() {
//初始化root根为空值
var root = null
//将传入值添加this.key,this.left,this.right属性
var Node = function(key) {
this.key = key
this.left = null
this.right = null
}
//将传入值进行判断,作为父节点的左支或右支
var insertNode = function(node, newNode) {
if (newNode.key < node.key) {
//如果传入值小于父节点,作为左支,不过要先进行判断左支是否已经存在
if (node.left === null) {
//如果左支是null空值,将传入值作为左支
node.left = newNode
console.log(node.left.key)
} else {
//否则(左支已经存在)继续执行函数进行下个节点的判断
insertNode(node.left, newNode)
}
} else {
//否则(传入值大于父节点)作为右支,不过要先进行判断右支是否已经存在
if (node.right === null) {
//如果右支是null空值,将传入值作为右支
node.right = newNode
console.log(node.right.key)
} else {
//否则(右支已经存在)继续执行函数进行下个节点的判断
insertNode(node.right, newNode)
}
}
}
//函数的入口,第一步执行的函数,确定root根的值
this.insert = function(key) {
var newNode = new Node(key)
if (root === null) {
root = newNode
console.log(root.key)
//如果没有root根,将传入值作为root根
} else {
insertNode(root, newNode)
//如果已经存在根,执行insertNode函数
}
}
// 删除二叉树
this.remove = function(key) {
root = removeNode(root, key)
}
}
//传入子节点(callback)和父节点(node)(第一次的父节点就是root)
var inOrderTraverseNode = function(node, callback) {
//如果父节点存在,继续将左支和右支执行inOrderTraverseNod(),直到不存在子分支为止
// !!注意if结构里面的函数执行顺序,先执行inOrderTraverseNode(node.left,callback);再执行callback(node.key);最后执行inOrderTraverseNode(node.right,callback);
//当inOrderTraverseNode(node.left,callback);执行完之后,才会再执行callback(node.key);(即先打印完左分支的值,再打印最顶层的父节点,这样就达到了从小到大的排序效果).右分支同理
if (node !== null) {
inOrderTraverseNode(node.left, callback)
callback(node.key)
inOrderTraverseNode(node.right, callback)
}
}
var findMinNode = function(node) {
if (node) {
while (node && node.left !== null) {
node = node.left
}
return node
}
return null
}
TODO:;
// 删除二叉树
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 {
// 这事判断第一种情况,没有左右分支的情况下,
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
}
}
//
var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]
//实例化BinaryTree
var binaryTree = new BinaryTree()
//遍历nodes数组,将每个数组的值(key)传入binary.insert(),执行 insert()函数
nodes.forEach(function(key) {
binaryTree.insert(key)
})
console.log(binaryTree.remove(10))
</script>
</body>
</html>
查看全部 -
CRV现在利用一些平台的新的框架，嗯，开发出来的程序可以同时应用于安卓平嗯，平板nlss以及电脑上。查看全部
-
在老司out除了可以开发web前端，还可以开发服务器后台恩，他需要用到新的技术note js。查看全部
-
中序遍历 ： 左左左 没有先打印 然后 回去 打印 然后右 左 没有打印 ，有右看右 没有回去。
前序遍历 ：先打印根，然后左 打印 ，再左打印，然后看看有没有左没有就看右 右有打印 然后这个节点没有左右就回去 ，再回去 ，再看看右有没有，然后和前面一样。
后续遍历 ：一直看左 打印左， 然后返回看右 的左 打印 再看右的右 是叶子节点就打印自己 然后发挥 本节点 而且它的左右都打印完了就打印自己。
前序遍历可用于复制一颗二叉树
中序便历可用于排序
后序遍历可以用在文件系统里
查看全部 -
<!DOCTYPE html> <html> <head> <meta charset="utf-8" /> <title>Binary Tree</title> </head> <body> <script> /** * 二叉排序树 * 新插入的数据只是增加在原先的树上（新加入的结点找到一个位置，作为原先树上某个结点的孩子结点） * 并不会破坏之前已形成的树 */ var Node = function(key) { this.key = key; this.left = null; this.right = null; }; // var Node end // nodes数组存储一下待排序的数据 var nodes = [ 8, 3, 10, 1, 6, 14, 4, 7 ]; // 新建一个排序树对象，是个函数对象 var binaryTree = new BinaryTree(); // 利用数组的forEach函数，依次处理数组中的数据，按下标 nodes.forEach(function(key) { // 对于数组中的每一个值，进行二叉排序树的插入操作 binaryTree.insert(key); }); // var callback = function(key) { // 1 console.log(key); } binaryTree.inOrderTraverse(callback); // 1 function BinaryTree() { 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); } } }; // var insertNode end // 中序遍历 this.inOrderTraverse = function(callback) { // callback是一个输出语句方法参数 inOrderTraverseNode(root, callback); }; var inOrderTraverseNode = function(node, callback) { // node节点为根节点 if(node !== null) { // 如果根节点不为空，即树存在时，进行先左，在中，在右，并递归 inOrderTraverseNode(node.left, callback); // 输出节点中的key值 callback(node.key); // 这是外部的一个函数 var callback = function(key) 这里的意思是，上一句进入左子树，如果上一句的结点没有左子树的话，就打印是一个结点 /** * *inOrderTraverse中的callback参数的意义何在？ *睡了一觉，自己悟出来了。传入的callback，实际上就是老师定义的callback函数， *因为老师的callback函数是定义在binarytree外部的，所以他把这个函数传进去，以便后续调用。 *我自己的代码，把callback函数定义在binarytree内部了，所以我不传callback参数是没有任何问题的，但是我的callback函数在其它地方就无法调用了。... * *callback只是一个引用，你也可以改成其他名字。为什么要用callback是因为程序员的习惯吧，大家一看就知道这里是一个回调函数。 *var声明的函数和this来声明的函数作用域不一样，var声明的在外面无法调用才对，你可以试试，我没验证。。。。。。。... */ inOrderTraverseNode(node.right, callback); } }; } </script> </body> </html>查看全部 -
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Title</title> </head> <body> <script type="text/javascript"> function binaryTree() { /** * 定义节点 * @param key int|float 节点值 */ var node = function (key) { this.key = key; this.left = null; this.right = null; } //定义根节点 var root = null; /** * 定义插入属性 * @param key int|float 要插入的值 */ this.insert = function (key) { var newNode = new node(key); if (root === null) { root = newNode; } else { insertNoder(root, newNode); } } /** * 插入数据 小左大右 * @param node obj 节点数据 * @param newNode obj 要插入的节点数据 */ var insertNoder = function (node, newNode) { if (newNode.key < node.key) { if (node.left === null) { node.left = newNode; } else { insertNoder(node.left, newNode); } } else { if (node.right === null) { node.right = newNode; } else { insertNoder(node.right, newNode); } } } /** * 查找节点 * @param key int|float 查找的节点值 * @param node obj 节点 * @returns obj|null 查找的节点, 不存在返回null */ this.find = function (key, node = root) { return findNode(key, node)[1]; } /** * 判断节点是否存在 * @param key int|float 查找的节点值 * @param node obj 节点 * @returns bool 存在true, 不存在false */ this.exists = function (key, node = root) { return findNode(key, node)[0]; } /** * 查找节点 * @param key int|float 查找的节点值 * @param node obj 节点 * @returns array */ var findNode = function (key, node) { if (node === null) return [false, null]; if (key == node.key) return [true, node]; if (key < node.key) return findNode(key, node.left); return findNode(key, node.right); } /** * 中序排列查询 * @param node obj 节点 * @returns {Array} */ this.inOrder = function (sort = 'ASC', node = root) { var nodeArr = []; if (node !== null) { if (sort.toUpperCase() == 'DESC') { inOrderDescNode(node, nodeArr); } else { inOrderAscNode(node, nodeArr); } } return nodeArr; } /** * 中序查询-升序(左->中->右) * @param node obj 节点 * @param nodeArr array 存储排序的值 */ var inOrderAscNode = function (node, nodeArr) { if (node !== null) { inOrderAscNode(node.left, nodeArr); nodeArr.push(node.key) inOrderAscNode(node.right, nodeArr); } } /** * 中序查询-降序(右->中->左) * @param node obj 节点 * @param nodeArr array 存储排序的值 */ var inOrderDescNode = function (node, nodeArr) { if (node !== null) { inOrderDescNode(node.right, nodeArr); nodeArr.push(node.key); inOrderDescNode(node.left, nodeArr) } } /** * 前序查询 * @param node obj 节点 * @returns {Array} */ this.preOrder = function (node = root) { var nodeArr = []; if (node !== null) { preOrderNode(node, nodeArr); } return nodeArr; } /** * 前序(中->左->右) * @param node obj 节点 * @param nodeArr 存储查询的值 */ var preOrderNode = function (node, nodeArr) { if (node !== null) { nodeArr.push(node.key); preOrderNode(node.left, nodeArr); preOrderNode(node.right, nodeArr) } } /** * 后序查询 * @param node obj 节点 * @returns {Array} */ this.reOrder = function (node = root) { var nodeArr = []; if (node !== null) { reOrderNode(node, nodeArr); } return nodeArr; } /** * 后序(左->右->中) * @param node obj 节点 * @param nodeArr 存储查询的值 */ var reOrderNode = function (node, nodeArr) { if (node !== null) { reOrderNode(node.left, nodeArr); reOrderNode(node.right, nodeArr); nodeArr.push(node.key); } } /** * 最大值 * @param node obj 节点 * @returns {*} */ this.max = function (node = root) { var newNode = maxNode(node); return newNode === null ? null : newNode.key; } /** * 查找一个节点最大的值 * @param node obj 节点 * @returns {*} */ var maxNode = function (node) { if (node === null) return null; while (node !== null && node.right !== null) { node = node.right; } return node; } /** * 最小值 * @param node obj 节点 * @returns {*} */ this.min = function (node = root) { var newNode = minNode(node); return newNode === null ? null : newNode.key; } /** * 查找一个节点最小值 * @param node obj 节点 * @returns {*} */ var minNode = function (node) { if (node === null) return null; if (node.left !== null) return minNode(node.left); return node; } /** * 移除一个节点 * @param key int|float 要移除的节点值 * @param node obj 节点 * @returns {*} */ this.remove = function (key, node = root) { return removeNode(key, node); } /** * 移除节点 * @param key int|float 要移除的节点值 * @param node obj 节点 * @returns {*} */ var removeNode = function (key, node) { if (node === null) return null; if (key === node.key) { if (node.left === null && node.right === null) return null; if (node.left === null) return node.right; if (node.right === null) return node.left var aux = minNode(node.right); node.key = aux.key; node.right = removeNode(node.right, aux.key); return node; } if (key < node.key) { node.left = removeNode(key, node.left); return node; } node.right = removeNode(key, node.right); return node; } } var arr = [9, 7, 4, 4, 6.4, 5, 8, 3.2, 11, 15, 9, 5, 6, 0, 3, 2, 13, 3.6, 1, 12, 14]; var node = new binaryTree(); //循环插入数据 arr.forEach(function (key) { node.insert(key); }) console.log('exists: ', node.exists(9)); console.log('exists-100: ', node.exists(100)); console.log('find: ', node.find(9)); console.log('find-1000: ', node.find(1000)); console.log('inOrder-Asc: ', node.inOrder()); //js实现对象的复制，不影响原对象 //var newNode = Object.assign({}, node.find(4));// var newNode = JSON.parse(JSON.stringify(node.find(4)));//当源对象的属性值是一个指向对象的引用时，应用深度复制 console.log('inOrder-Asc-4: ', node.inOrder('ASC', newNode)); console.log('remove-2: ', node.remove(2,newNode)); console.log('remove-3: ', node.remove(3)); console.log('remove-15: ', node.remove(15)); console.log('inOrder-Asc: ', node.inOrder()); console.log('inOrder-Asc-4: ', node.inOrder('ASC', newNode)); console.log('inOrder-desc: ', node.inOrder('DESC')); console.log('inOrder-desc-11: ', node.inOrder('DESC', node.find(11))); console.log('preOrder: ', node.preOrder()); console.log('reOrder: ', node.reOrder()); console.log('max: ', node.max()); console.log('max-4: ', node.max(node.find(4))); console.log('min: ', node.min()); console.log('min-11: ', node.min(node.find(11))); console.log('min-11: ', node.max(null)); </script> </body> </html>查看全部
举报