-
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>JavaScript二叉树中序算法</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;
} else {
//否则(左支已经存在)继续执行函数进行下个节点的判断
insertNode(node.left, newNode);
}
} else {
//否则(传入值大于父节点)作为右支,不过要先进行判断右支是否已经存在
if (node.right === null) {
//如果右支是null空值,将传入值作为右支
node.right = newNode;
} else {
//否则(右支已经存在)继续执行函数进行下个节点的判断
insertNode(node.right, newNode);
}
}
};
//函数的入口,第一步执行的函数,确定root根的值
this.insert = function (key) {
var newNode = new Node(key);
//newNode拥有newNode.key=key,newNode.left=null,newNode.right=null
if (root === null) {
root = newNode;
//如果没有root根,将传入值作为root根
} else {
insertNode(root, newNode)
//如果已经存在根,执行insertNode函数
}
};
//将root根值和传入值(callback)赋给inOrderTraverseNod(),执行inOrderTraverseNod()
this.inOrderTraverse = function (callback) {
inOrderTraverseNode(root, callback);
};
};
//传入子节点(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 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);
});
//定义callback函数,将传入callback的值打印出来
var callback = function (key) {
console.log(key);
};
//注意此callback是参数,不是function函数,执行的是inOrderTraverse(),不是上面的callback()
binaryTree.inOrderTraverse(callback);
</script>
</body>
</html>
查看全部 -
<!-- 稍微改造了一下下,可视化二叉树排序,非常有利于学习和理解哟!-->
<!DOCTYPE html>
<html>
<title>二叉排序树</title>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
</head>
<body >
<canvas id="canvas" width="1366" height="768" ></canvas>
</body>
</html>
<script type="text/javascript">
//二叉算法函数
function BinaryTree(){
//node 节点函数
var Node=function(key){
this.key=key;
this.left=null;
this.right=null;
this.x = 0;//图形绘制坐标
this.y = 0;//图形绘制坐标
};
/**二叉树可视图形描述**/
this.graphical = [];//图形数组
this.lrMove = 100;//左右偏移量
this.udMove = 100;//上下偏移量
/**==================**/
//定义根节点
var root=null;
//插入节点 循环递归函数 左右分插
this.insertNode=function(node,newNode){
if(newNode.key < node.key){
if(node.left===null){
var x = node.x;
var y = node.y;
newNode.x = (x -= this.udMove);
newNode.y = (y += this.lrMove);
node.left=newNode;
}else{
this.insertNode(node.left,newNode);
}
}else{
if(node.right===null){
var x = node.x;
var y = node.y;
newNode.x = (x += this.udMove);
newNode.y = (y += this.lrMove);
node.right=newNode;
}else{
this.insertNode(node.right,newNode);
}
}
};
//入口程序
this.insert=function(key){
var newNode= new Node(key);
if(root===null){
root=newNode;
root.x = 500;
root.y = 100;
this.graphical.push(root);
}else{
this.insertNode(root,newNode);
}
};
var inOrdertraverseNode = function(node,callback){
if(node !== null){
inOrdertraverseNode(node.left,callback);
callback(node.key);
inOrdertraverseNode(node.right,callback);
}
}
this.inOrdertraverse = function(callback){
inOrdertraverseNode(root,callback);
}
}
var nodes=[8,3,10,1,6,14,4,15,12,13];
var binaryTree=new BinaryTree;
for(var i = 0 ; i < nodes.length ; i++){
binaryTree.insert(nodes[i]);
}
var callback = function(key){
console.log(key)
}
binaryTree.inOrdertraverse(callback);
/*=====================================================开始绘制================================*/
var canvas = document.getElementById("canvas");
var context = canvas.getContext('2d'); //获取对应的2D对象(画笔)
function draw(key,x,y){
this.counter = 0;
this.render = function(c){
c.fillStyle = "hsl("+ this.counter +", 100%, 50%)";
c.strokeStyle = '#fff'; //设置笔触的颜色
c.font = "bold 40px '字体','字体','微软雅黑','宋体'"; //设置字体
c.textBaseline = 'hanging'; //在绘制文本时使用的当前文本基线
c.fillText(key ,x ,y);
}
this.update = function(){
this.counter += 5;
}
}
var fontCavaseArr = [];
function init() {
loop();//绘制文字
setInterval(run, 1000/30);
}
function run(x,y){
context.fillStyle = "rgba(0,0,0,0.1)";
context.fillRect(0,0,1366,768); //绘制 1366*768 像素的已填充矩形:
for (i=0; i<fontCavaseArr.length; i++) {
var particle = fontCavaseArr[i];
particle.render(context);
particle.update();
}
gLine();//绘制线条
}
function loop(){
font(binaryTree.graphical[0]);
}
function font(obj){
if(obj.key != null && obj.key != undefined){
var drawFont = new draw(obj.key,obj.x,obj.y);
fontCavaseArr.push(drawFont);
}
if(obj.left != null && obj.left != undefined){
var drawFont = new draw(obj.left.key,obj.left.x,obj.left.y);
fontCavaseArr.push(drawFont);
font(obj.left);
}
if(obj.right != null && obj.right != undefined){
var drawFont = new draw(obj.right.key,obj.right.x,obj.right.y);
fontCavaseArr.push(drawFont);
font(obj.right);
}
}
function gLine(){
line(binaryTree.graphical[0]);
}
function line(obj){
context.lineJoin="round";
context.lineCap="butt";
context.beginPath();
if(obj.left != null && obj.left != undefined){
context.moveTo(obj.x+20,obj.y+20);
context.lineTo(obj.left.x+20,obj.left.y+20);
context.stroke();
context.closePath();
line(obj.left);
}
if(obj.right != null && obj.right != undefined){
context.moveTo(obj.x+20,obj.y+20);
context.lineTo(obj.right.x+20,obj.right.y+20);
context.stroke();
context.closePath();
line(obj.right);
}
}
init();
</script>
查看全部 -
1.前序遍历可用于复制一颗二叉树 2.中序便历可用于排序 3.后序遍历可以用在文件系统里查看全部
-
中序遍历,排序 前序遍历,复制 后序遍历,查找最下 二叉树:从根节点开始,当传入的值小于根节点时,放在左边,否则放在右边。若根节点下有(左右)子节点,进一步对其值进行比较,直到叶节点,使其成为叶节点的子节点。 1,中序遍历原理:从根节点开始,先从左子树遍历,遵循从左至右的原则,当遇到叶节点(即没有左右子节点)后,打印当前节点值,并返回到父节点(中间节点),打印当前父节点值,再遍历其右子节点,遇到叶节点后,打印当前节点值,并返回到父节点(中间节点),直到返回到根节点,打印节点值,再遍历右子树,方法与左子树相同。 2,前序遍历原理:从根节点开始,打印当前节点值,之后从左子树遍历,遵循从左至右的原则,无论遇到中间节点还是叶节点,遵循先打印当前节点值,再进行遍历。当遇到叶节点之后,返回到父节点,当左右子节点遍历完之后,回到根节点。 3,后序遍历原理:从根节点开始,先从左子树遍历,遵循从左至右的原则,当遇到叶节点(即没有左右子节点)后,打印当前节点值,并返回到父节点(中间节点),只有父节点的左右子节点遍历完之后,再打印父节点的值。当左右子树均遍历完之后,再打印根节点的值。查看全部
-
<!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>
查看全部 -
中序遍历 : 左左左 没有先打印 然后 回去 打印 然后右 左 没有打印 ,有右看右 没有回去。
前序遍历 :先打印根,然后左 打印 ,再左打印,然后看看有没有左没有就看右 右有打印 然后这个节点没有左右就回去 ,再回去 ,再看看右有没有,然后和前面一样。
后续遍历 :一直看左 打印左, 然后返回看右 的左 打印 再看右的右 是叶子节点就打印自己 然后发挥 本节点 而且它的左右都打印完了就打印自己。
前序遍历可用于复制一颗二叉树
中序便历可用于排序
后序遍历可以用在文件系统里
查看全部 -
<!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>
查看全部 -
这里漏了吧,不过没关系,也就截图上的内容
查看全部 -
根节点
中间节点
叶子结点
节点层次:二叉树的高
排序二叉树:左子节点值小于父节点,右子节点值大于父节点
查看全部 -
从左到右开始,左小,右大查看全部
-
CRV现在利用一些平台的新的框架,嗯,开发出来的程序可以同时应用于安卓平嗯,平板nlss以及电脑上。查看全部
-
在老司out除了可以开发web前端,还可以开发服务器后台恩,他需要用到新的技术note js。查看全部
-
排序二叉树:左孩子 <父节点< 右孩子 兄弟节点 根节点
查看全部 -
==用于一般比较,===用于严格比较,==在比较的时候可以转换数据类型,===严格比较,只要类型不匹配就返回flase
查看全部 -
前序遍历---相当于复制当前的二叉树
查看全部
举报