                        課程
                    
                        /計(jì)算機(jī)基礎(chǔ)
                        
                            /算法與數(shù)據(jù)結(jié)構(gòu)
                        
                        /Javascript實(shí)現(xiàn)二叉樹算法

簡(jiǎn)略版的完整代碼，可以玩一哈~

<!DOCTYPE html>

<html>

<head>

? ? <meta charset="UTF-8">

? ? <title>Document</title>

? ? <style>

? ? #stage {

? ? ? ? width: 300px;

? ? ? ? height: 300px;

? ? ? ? position: relative;

? ? }

? ? #background {

? ? ? ? width: 300px;

? ? ? ? height: 300px;

? ? ? ? position: absolute;

? ? ? ? top: 0;

? ? ? ? left: 0;

? ? ? ? background: yellow;

? ? }

? ? #cannon {

? ? ? ? width: 20px;

? ? ? ? height: 20px;

? ? ? ? position: absolute;

? ? ? ? top: 270px;

? ? ? ? left: 140px;

? ? ? ? background: red;

? ? }

? ? #alien {

? ? ? ? width: 20px;

? ? ? ? height: 20px;

? ? ? ? position: absolute;

? ? ? ? top: 20px;

? ? ? ? left: 80px;

? ? ? ? background: blue;

? ? }

? ? #missile {

? ? ? ? width: 10px;

? ? ? ? height: 10px;

? ? ? ? position: absolute;

? ? ? ? top: 270px;

? ? ? ? left: 140px;

? ? ? ? background: black;

? ? }

? ? #explosion {

? ? ? ? width: 20px;

? ? ? ? height: 20px;

? ? ? ? position: absolute;

? ? ? ? top: 0;

? ? ? ? left: 0;

? ? ? ? background: pink;

? ? ? ? display: none;

? ? }

? ? </style>

</head>

<body>

? ? <div id="stage">

? ? ? ? <div id="background"></div>

? ? ? ? <div id="cannon"></div>

? ? ? ? <div id="missile"></div>

? ? ? ? <div id="alien"></div>

? ? ? ? <div id="explosion"></div>

? ? </div>

? ? <p id="output">請(qǐng)輸入x和y坐標(biāo)（0-300），然后點(diǎn)擊fire</p>

? ? <input type="text" id="inputX" placeholder="X...">

? ? <input type="text" id="inputY" placeholder="Y...">

? ? <button>fire</button>

? ? <script>

? ? function BinaryTree() {

? ? ? ? var Node = function(key) {

? ? ? ? ? ? this.key = key;

? ? ? ? ? ? this.left = null;

? ? ? ? ? ? this.right = null;

? ? ? ? ? ? this.selected = false;

? ? ? ? };

? ? ? ? var root = null;

? ? ? ? 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.insert = function(key) {

? ? ? ? ? ? var newNode = new Node(key);

? ? ? ? ? ? if (root == null) {

? ? ? ? ? ? ? ? root = newNode;

? ? ? ? ? ? } else {

? ? ? ? ? ? ? ? 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 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 node;

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? this.search = function(key) {

? ? ? ? ? ? return searchNode(root, key);

? ? ? ? }

? ? }

? ? var callback = function(key) {

? ? ? ? console.log(key);

? ? };

? ? // init alienSiteArray

? ? var nodesForAlien = [];

? ? for (var i = 0; i < 10; i++) {

? ? ? ? nodesForAlien.push(Math.floor(Math.random() * 281));

? ? }

? ? // nodesArray for selected

? ? var nodesForSelected = [];

? ? for (var i = 0; i < 10; i++) {

? ? ? ? nodesForSelected.push({selected: false});

? ? }

? ? // activate first alienSite

? ? var alienNodeSelect = Math.floor(Math.random() * 9);

? ? nodesForSelected[alienNodeSelect].selected = true;

? ? var binaryTree = new BinaryTree();

? ? nodesForAlien.forEach(function(key) {

? ? ? ? binaryTree.insert(key)

? ? });

? ? //Game section

? ? var alienX = 20;

? ? var alienY = 20;

? ? var guessX = 0,

? ? ? ? guessY = 0,

? ? ? ? shotsRemaning = 8,

? ? ? ? shotsMade = 0,

? ? ? ? gameState = "",

? ? ? ? gameWon = false;

? ? var cannon = document.querySelector("#cannon"),

? ? ? ? alien = document.querySelector("#alien"),

? ? ? ? missile = document.querySelector("#missile"),

? ? ? ? explosion = document.querySelector('#explosion');

? ? var inputX = document.querySelector('#inputX'),

? ? ? ? inputY = document.querySelector('#inputY'),

? ? ? ? output = document.querySelector('#output');

? ? var button = document.querySelector("button");

? ? button.style.cursor = "pointer";

? ? button.addEventListener("click", clickHandler, false);

? ? window.addEventListener("keydown", keydownHandler, false);

? ? function clickHandler() {

? ? ? ? validateInput();

? ? }

? ? function keydownHandler() {

? ? ? ? if (event.keyCode === 13) {

? ? ? ? ? ? validateInput();

? ? ? ? }

? ? }

? ? function validateInput() {

? ? ? ? guessX = parseInt(inputX.value);

? ? ? ? guessY = parseInt(inputY.value);

? ? ? ? if (isNaN(guessX) || isNaN(guessY)) {

? ? ? ? ? ? output.innerHTML = "請(qǐng)輸入數(shù)字坐標(biāo)";

? ? ? ? } else if (guessX > 300 || guessY > 300) {

? ? ? ? ? ? output.innerHTML = "坐標(biāo)不能大于300"

? ? ? ? } else {

? ? ? ? ? ? playGame();

? ? ? ? }

? ? }

? ? function playGame() {

? ? ? ? shotsRemaning--;

? ? ? ? shotsMade++;

? ? ? ? gameState = "炮彈：" + shotsMade + ",數(shù)量：" + shotsRemaning;

? ? ? ? guessX = parseInt(inputX.value);

? ? ? ? guessY = parseInt(inputY.value);

? ? ? ? var alienNode = binaryTree.search(guessX);

? ? ? ? var alienFlag = -1;

? ? ? ? if (alienNode) {

? ? ? ? ? ? nodesForAlien.forEach(function(val, index) {

? ? ? ? ? ? ? ? if (val === alienNode.key) {

? ? ? ? ? ? ? ? ? ? alienFlag = index;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? })

? ? ? ? }

? ? ? ? if (alienNode !== null && alienNodeSelect === alienFlag) {

? ? ? ? ? ? if (guessY >= alienY && guessY <= alienY + 20) {

? ? ? ? ? ? ? ? gameWon = true;

? ? ? ? ? ? ? ? endGame();

? ? ? ? ? ? }

? ? ? ? } else {

? ? ? ? ? ? output.innerHTML = "沒有擊中" + "<br>" + gameState;

? ? ? ? ? ? if (shotsRemaning < 1) {

? ? ? ? ? ? ? ? endGame();

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? if (!gameWon) {

? ? ? ? ? ? alienNodeSelect = Math.floor(Math.random() * 9);

? ? ? ? ? ? alienX = nodesForAlien[alienNodeSelect];

? ? ? ? ? ? alienY += 30;

? ? ? ? }

? ? ? ? render();

? ? ? ? console.log("X" + alienX);

? ? ? ? console.log("Y" + alienY);

? ? }

? ? function render() {

? ? ? ? alien.style.left = alienX + 'px';

? ? ? ? alien.style.top = alienY + 'px';

? ? ? ? cannon.style.left = guessX + 'px';

? ? ? ? missile.style.left = guessX + 'px';

? ? ? ? missile.style.top = guessY + 'px';

? ? ? ? if (gameWon) {

? ? ? ? ? ? explosion.style.display = 'block';

? ? ? ? ? ? explosion.style.left = alienX + 'px';

? ? ? ? ? ? explosion.style.top = alienY + 'px';

? ? ? ? ? ? alien.style.display = "none";

? ? ? ? ? ? missile.style.display = "none";

? ? ? ? }

? ? }

? ? function endGame() {

? ? ? ? if (gameWon) {

? ? ? ? ? ? output.innerHTML = "Hit! 你拯救了地球" + "<br>" + "你發(fā)射了炮彈" + shotsMade;

? ? ? ? } else {

? ? ? ? ? ? output.innerHTML = "失敗了！" + "<br>" + "地球被外星人侵略！";

? ? ? ? }

? ? ? ? button.removeEventListener("click", clickHandler, false);

? ? ? ? button.disabled = true;

? ? ? ? window.removeEventListener("keydown", keydownHandler, false);

? ? ? ? inputX.disabled = true;

? ? ? ? inputY.disabled = true;

? ? }

? ? </script>

</body>

</html>

Qzhor

2017-10-06

源自：Javascript實(shí)現(xiàn)二叉樹算法 2-5

關(guān)注問題我要回答

1912

操作

收起

6 回答

大米小米米
2020-09-17

試一下

<html>
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Document</title>
<style>
#stage {
width: 300px;
height: 300px;
position: relative;
}

#background {
width: 300px;
height: 300px;
position: absolute;
top: 0;
left: 0;
background-image: url(./images/background.jpg);
}

#cannon {
width: 20px;
height: 20px;
position: absolute;
top: 270px;
left: 140px;
background-image: url(./images/cannon.jpg);
background-size: 100%;
}

#alien {
width: 20px;
height: 20px;
position: absolute;
top: 20px;
left: 80px;
background-image: url(./images/alien.jpg);
background-size: 100%;
}

#missile {
width: 10px;
height: 10px;
position: absolute;
top: 270px;
left: 140px;
background-image: url(./images/missllie.jpg);
background-size: 100%;
}

#explosion {
width: 20px;
height: 20px;
position: absolute;
top: 0;
left: 0;
background-image: url(./images/explosion.jpg);
background-size: 100%;
display: none;
}
</style>
</head>
<body>
<div id="stage">
<div id="background"></div>
<div id="cannon"></div>
<div id="missile"></div>
<div id="alien"></div>
<div id="explosion"></div>
</div>
<p id="output">請(qǐng)輸入X和Y坐標(biāo)(0-300)，然后點(diǎn)擊fire.</p>
<input type="text" id="inputX" placeholder="X..." />
<input type="text" id="inputY" placeholder="Y..." />
<button id="button">fire!</button>

<script>
function BinaryTree() {
var Node = function (key) {
this.key = key;
this.left = null;
this.right = null;
this.selected = false;
};

root = null;

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.insert = function (key) {
var newNode = new Node(key);
if (root === null) {
root = newNode;
} else {
insertNode(root, newNode);
}
};

// 中序遍歷
var inOrderTraverseNode = function (node, callback) {
if (node !== null) {
inOrderTraverseNode(node.left, callback);
callback(node);
inOrderTraverseNode(node.right, callback);
}
};

this.inOrderTraverse = function (callback) {
inOrderTraverseNode(root, callback);
};

// 前序遍歷
var preOrderTraverseNode = function (node, callback) {
if (node !== null) {
callback(node);
preOrderTraverseNode(node.left, callback);
preOrderTraverseNode(node.right, callback);
}
};

this.preOrderTraverse = function (callback) {
preOrderTraverseNode(root, callback);
};

// 后序遍歷
var postOrderTraverseNode = function (node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback);
postOrderTraverseNode(node.right, callback);
callback(node);
}
};

this.postOrderTraverse = function (callback) {
postOrderTraverseNode(root, callback);
};

// 最小值
var minNode = function (node) {
if (node) {
while (node && node.left !== null) {
node = node.left;
}

return node.key;
}
};
this.min = function () {
return minNode(root);
};

// 最大值
var maxNode = function (node) {
if (node) {
while (node && node.right !== null) {
node = node.right;
}

return node.key;
}
};
this.max = function () {
return maxNode(root);
};

// 查找
function searchNode(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 node;
}
}
this.search = function (key) {
return searchNode(root, key);
};

var findMinNode = function (node) {
if (node) {
while (node && node.left !== null) {
node = node.left;
}

return node;
}
};
// 刪除節(jié)點(diǎn)
function removeNode(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;
}

var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right, aux.key);
return node;
}
}
this.remove = function (key) {
return removeNode(root, key);
};
}

var binaryTree = new BinaryTree();
[31, 55, 50, 201, 116, 241, 78, 140, 144].forEach(function (key) {
binaryTree.insert(key);
});
var nodesForAlien = [];
var callback = function (node) {
nodesForAlien.push(node);
};

binaryTree.preOrderTraverse(callback);
var alienNodeSelect = Math.floor(Math.random() * 9);
nodesForAlien[alienNodeSelect].selected = true;

var alienX = nodesForAlien[alienNodeSelect].key;

// var calllback = function (key) {
// ? ? console.log(key);
// };

// binaryTree.inOrderTraverse(calllback);
// binaryTree.preOrderTraverse(calllback);
// binaryTree.postOrderTraverse(calllback);
// console.log('min node is: ' + binaryTree.min());
// console.log('max node is: ' + binaryTree.max());
// console.log(binaryTree.search(7) ? 'key 7 is found' : 'key 7 is not found');
// console.log(binaryTree.search(9) ? 'key 9 is found' : 'key 9 is not found');

// binaryTree.remove(10);

// Game section
var alienY = 20;
var guessX = 0;
var guessY = 0;
var shotsRemaing = 8;
var shotsMade = 0;
var gameState = '';
var gameWon = false;

var cannon = document.querySelector('#cannon');
var alien = document.querySelector('#alien');
var missile = document.querySelector('#missile');
var explosion = document.querySelector('#explosion');

var inputX = document.querySelector('#inputX');
var inputY = document.querySelector('#inputY');
var output = document.querySelector('#output');

var button = document.querySelector('#button');
button.style.curor = 'pointer';
button.addEventListener('click', clickHandler, false);
window.addEventListener('keydown', keydownHandler, false);

function clickHandler() {
validateInput();
}

function keydownHandler(e) {
if (e.keyCode == 13) {
validateInput();
}
}

function validateInput() {
guessX = parseInt(inputX.value);
guessY = parseInt(inputY.value);

if (isNaN(guessX) || isNaN(guessY)) {
output.innerHTML = '請(qǐng)輸入坐標(biāo)';
} else if (guessX > 300 && guessY > 300) {
output.innerHTML = '坐標(biāo)不能大于300。';
} else {
playGame();
}
}

function playGame() {
shotsRemaing--;
shotsMade++;
gameState = '炮彈：' + '，數(shù)量：' + shotsRemaing;

guessX = parseInt(inputX.value);
guessY = parseInt(inputY.value);

var alienNode = binaryTree.search(guessX);
if (alienNode !== null && alienNode.selected === true) {
if (guessY >= alienY && guessY < alienY + 20) {
gameWon = true;
endGame();
}
} else {
output.innerHTML = '炮彈沒有擊中！<br>' + gameState;
if (shotsRemaing < 1) {
endGame();
}
}

if (!gameWon) {
nodesForAlien[alienNodeSelect].selected = false;
alienNodeSelect = Math.floor(Math.random() * 9);
nodesForAlien[alienNodeSelect].selected = true;
alienX = nodesForAlien[alienNodeSelect].key;
alienY += 30;
}

render();
console.log(alienX, alienY);
}

function render() {
alien.style.left = alienX + 'px';
alien.style.top = alienY + 'px';

cannon.style.left = guessX + 'px';

missile.style.left = guessX + 'px';
missile.style.top = guessY + 'px';

if (gameWon) {
alien.style.display = 'none';
explosion.style.display = 'block';
explosion.style.left = alienX + 'px';
explosion.style.top = alienY + 'px';
}
}

function endGame() {
if (gameWon) {
output.innerHTML = 'Hit!拯救了地球。<br>發(fā)射炮彈' + shotsMade + '枚。';
} else {
output.innerHTML = '你失敗了！';
}
button.removeEventListener('click', clickHandler, false);
button.disable = true;
window.removeEventListener('keydown', keydownHandler, false);
inputX.disable = true;
inputY.disable = true;
}
</script>
</body>
</html>

0 回復(fù) 有任何疑惑可以回復(fù)我~

收起回答

猴犀利的7號(hào)
2018-11-14

其實(shí)js array對(duì)象有這些方法，這(二叉樹)有何優(yōu)勢(shì)？

2 回復(fù) 有任何疑惑可以回復(fù)我~

收起回答

#1

陽(yáng)仔214

所以他開篇介紹了node，如果有機(jī)會(huì)用node寫接口，處理數(shù)據(jù)庫(kù)中大量數(shù)據(jù)的時(shí)候就有價(jià)值了，web的應(yīng)用，可能使用場(chǎng)景不多…

2020-08-27 回復(fù) 有任何疑惑可以回復(fù)我~

楓葉咚咚咚
2018-01-18

給樓主點(diǎn)贊。樓上慕粉的方法不可行，把callback函數(shù)內(nèi)容改為nodesForAlien.push(node)時(shí)，只能成功將根結(jié)點(diǎn)復(fù)制進(jìn)新數(shù)組的[0]號(hào)元素，后面的復(fù)制都會(huì)報(bào)錯(cuò)，因?yàn)槔蠋煒?gòu)造的二叉樹，結(jié)點(diǎn)之間的關(guān)系是靠node.left(或者node.righht)指向另一個(gè)node維系的，使用push并不能得到nodesForAlien的[0]號(hào)元素是一個(gè)結(jié)點(diǎn)，[1]號(hào)元素是另一個(gè)結(jié)點(diǎn)。

0 回復(fù) 有任何疑惑可以回復(fù)我~

收起回答

慕粉2124514671
2017-10-14

//生成一個(gè)隨機(jī)數(shù)的數(shù)組nodesArr[]

var nodesArr = [];

for(var i =0; i < 10 ; i++){

nodesArr[i] = Math.floor((Math.random() * (281-20))+20);

}

for(var i=0;i<10;i++){

console.log(nodesArr[i]);

}

var binaryTree = new BinaryTree();

nodesArr.forEach(function (key) {

binaryTree.insert(key);

});

var nodesForAlien = [];? //存放二叉樹節(jié)點(diǎn)的數(shù)組

var callback = function (node) {

nodesForAlien.push(node);

console.log(nodesForAlien);

}

var call = function(key){

console.log(key);

}

//binaryTree.inOrderTraverse(call);

binaryTree.preOrderTraverse(callback);? //通過前序遍歷復(fù)制二叉樹存入數(shù)組nodesForAlien中

//建立第一次外星人橫坐標(biāo)

var alienNodeSelect = Math.floor(Math.random() * 9);

nodesForAlien[alienNodeSelect].selected = true;

var alienX = nodesForAlien[alienNodeSelect].key;

1 回復(fù) 有任何疑惑可以回復(fù)我~

收起回答

慕粉2124514671
2017-10-14

應(yīng)該不是給每個(gè)node另外附上selected：false 屬性，而是新建一個(gè)nodesForAlien數(shù)組，利用前序遍歷的方法復(fù)制二叉樹中的節(jié)點(diǎn)給nodesForAlien數(shù)組，這樣二叉樹中的node屬性（key，selected……）在nodesForAlien數(shù)組中的元素也有。

0 回復(fù) 有任何疑惑可以回復(fù)我~

收起回答

#1

Qzhor 提問者

selected屬性怎么初始化的啊，前面講二叉樹沒有提到

2017-10-21 回復(fù) 有任何疑惑可以回復(fù)我~

#2

我是一個(gè)好人啊_ 回復(fù) Qzhor 提問者

試一試這個(gè)回答

2017-11-05 回復(fù) 有任何疑惑可以回復(fù)我~

#3

ideal_idiot 回復(fù) Qzhor 提問者