-
源代码:
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>Document</title>
</head>
<body>
</body>
<script type="text/javascript">
function BinaryTree () {
var Node = function (key) {
this.key = key;
this.left = null;
this.right = null;
}
this.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(newNode.key > node.key){
if(node.right === null){
node.right = newNode;
}else{
insertNode(node.right,newNode);
}
}
}
this.insert = function (key) {
if(this.root === null){
this.root = new Node(key);
}else{
insertNode(this.root,new Node(key));
}
}
//栈是先进后出的,所以在节点1的时候,它没有左子节点,这个时候开始出栈,继续执行上一次的inOrderTraverceNodes里未执行完的代码,当节点1也没有右子节点的时候,到节点3开始继续执行上一次的inOrderTraverceNodes里未执行完的代码,以此类推。
//栈是先进后出的,一开始节点8执行函数,有左子节点3,节点3执行函数,有左子节点1,节点1执行函数,没有左子节点,这时是null,这时这个函数已经出栈,到节点1之前执行的函数开始出栈了,然后调用callback,打印了1,然后节点1传入node.right,这时又是null,然后这个函数出栈了,开始到节点3之前执行的函数出栈了,所以进栈的顺序是8,3,1,1的左null,出栈的顺序是1的左null,1,1的右null,3,3执行后,右边有个6,6进栈,6有4,4进栈,这个时候栈里还有8,3,,6,4
//中序遍历代码,先找左子节点,再找右子节点
var inOrderTraverceNodes = function (node,callback) {
if(node !== null){
inOrderTraverceNodes(node.left,callback);
callback(node.key);//调动callback
inOrderTraverceNodes(node.right,callback);
}
}
this.inOrderTraverce = function (callback) {
inOrderTraverceNodes(this.root,callback);
}
//前序遍历代码,先找自己,再找左子节点,再找右子节点
var preOrderTraverceNodes = function (node,callback) {
if(node !== null){
callback(node.key);//调动callback
preOrderTraverceNodes(node.left,callback);
preOrderTraverceNodes(node.right,callback);
}
}
this.preOrderTraverce = function (callback) {
preOrderTraverceNodes(this.root,callback);
}
//后序遍历代码,先找左子节点,再找右子节点,需要找完自己的左右子节点
var postOrderTraverceNodes = function (node,callback) {
if(node !== null){
postOrderTraverceNodes(node.left,callback);
postOrderTraverceNodes(node.right,callback);
callback(node.key);//调动callback
}
}
this.postOrderTraverce = function (callback) {
preOrderTraverceNodes(this.root,callback);
}
//查找最小值,只需要查找左子节点
var minNode = function (node) {
if(node){
while (node && node.left !== null) {
node = node.left;
}
return node.key;
}
return null;
}
this.min = function () {
return minNode(this.root);
}
//查找最大值,只需要查找右子节点
var maxNode = function (node) {
if(node){
while (node && node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
}
this.max = function () {
return minNode(this.root);
}
//查找值x
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(this.root,key);
}
//查找最小值,只需要查找左子节点
var findMinNode = function (node) {
if(node){
while (node && node.left !== null) {
node = node.left;
}
return node;
}
return null;
}
//删除叶子节点
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;
}else{
//例如删除的是节点3,走到这里当前节点就是节点3了,传入节点6,找到它的最小节点,返回当前节点,修改节点3的key为节点4,传入节点6和要删除的节点4,删除后重新对节点6赋值,在返回其父节点4
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right,aux.key);
return node;
}
}
}
this.remove = function (key) {
removeNode(this.root,key);
}
}
var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree;
nodes.forEach((key) =>{
binaryTree.insert(key);
})
console.dir(binaryTree.root);
var callback = function (key) {
console.log(key);
}
// binaryTree.preOrderTraverce(callback);
// console.log('this is min: ' + binaryTree.min());
console.log('this is search: ' + binaryTree.search(7));
console.log('this is search: ' + binaryTree.search(9));
binaryTree.remove(1);
</script>
</html>
查看全部 -
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,1,6,14,4,7,13];
var binaryTree=new BinaryTree();
nodes.forEach(function(key){
binaryTree.insert(key);
});
var callback=function(key){
console.log(key);
}
binaryTree.inOrderTraverse(callback);
查看全部 -
function(callback){
}
当我们要输出某一个节点的值得时候,我们就把这个节点的值传入这个回调函数中,让这个回调函数决定怎么输出出来
查看全部 -
“==”是"==="
var nodes=[8,3,1];
查看全部 -
Node.js
开发的APP可以在IOS和Android平台上同时运行
console.log("Hello World");
在开发者工具中显示
单步调试
查看全部 -
后序遍历---先遍历左节点,然后遍历右节点,最后打印当前父节点
查看全部 -
public static final String node= "xxxxx"; //二叉树前序遍历复制数据最快
查看全部 -
<!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> //文档声明,便于解析
breakpoints: 单步调式
查看全部 -
单点调试功能,打断点查看全部
-
这个太神奇了,原来可以通过将一个算法的数学模型,用代码表示出来,最于明白,算法,数据结构,编程之间的关系了查看全部
-
前序遍历复制二叉树查看全部
-
中序遍历、前序遍历、后序遍历查看全部
-
console对象的其他方法查看全部
-
二叉树图查看全部
举报