-
從左到右開始，左小，右大查看全部
-
<!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
}
//將傳入值進行判斷,作為父節(jié)點的左支或右支
var insertNode = function(node, newNode) {
if (newNode.key < node.key) {
//如果傳入值小于父節(jié)點,作為左支,不過要先進行判斷左支是否已經(jīng)存在
if (node.left === null) {
//如果左支是null空值,將傳入值作為左支
node.left = newNode
console.log(node.left.key)
} else {
//否則(左支已經(jīng)存在)繼續(xù)執(zhí)行函數(shù)進行下個節(jié)點的判斷
insertNode(node.left, newNode)
}
} else {
//否則(傳入值大于父節(jié)點)作為右支,不過要先進行判斷右支是否已經(jīng)存在
if (node.right === null) {
//如果右支是null空值,將傳入值作為右支
node.right = newNode
console.log(node.right.key)
} else {
//否則(右支已經(jīng)存在)繼續(xù)執(zhí)行函數(shù)進行下個節(jié)點的判斷
insertNode(node.right, newNode)
}
}
}
//函數(shù)的入口,第一步執(zhí)行的函數(shù),確定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)
//如果已經(jīng)存在根,執(zhí)行insertNode函數(shù)
}
}
// 刪除二叉樹
this.remove = function(key) {
root = removeNode(root, key)
}
}
//傳入子節(jié)點(callback)和父節(jié)點(node)(第一次的父節(jié)點就是root)
var inOrderTraverseNode = function(node, callback) {
//如果父節(jié)點存在,繼續(xù)將左支和右支執(zhí)行inOrderTraverseNod(),直到不存在子分支為止
// !!注意if結(jié)構(gòu)里面的函數(shù)執(zhí)行順序,先執(zhí)行inOrderTraverseNode(node.left,callback);再執(zhí)行callback(node.key);最后執(zhí)行inOrderTraverseNode(node.right,callback);
//當inOrderTraverseNode(node.left,callback);執(zhí)行完之后,才會再執(zhí)行callback(node.key);(即先打印完左分支的值,再打印最頂層的父節(jié)點,這樣就達到了從小到大的排序效果).右分支同理
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
}
// 如果左右兩個分支都存在的時候,那么執(zhí)行下面的代碼
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數(shù)組,將每個數(shù)組的值(key)傳入binary.insert(),執(zhí)行 insert()函數(shù)
nodes.forEach(function(key) {
binaryTree.insert(key)
})
console.log(binaryTree.remove(10))
</script>
</body>
</html>
查看全部 -
CRV現(xiàn)在利用一些平臺的新的框架，嗯，開發(fā)出來的程序可以同時應用于安卓平嗯，平板nlss以及電腦上。查看全部
-
在老司out除了可以開發(fā)web前端，還可以開發(fā)服務器后臺恩，他需要用到新的技術(shù)note js。查看全部
-
中序遍歷 ：?左左左?沒有先打印?然后?回去?打印?然后右? 左?沒有打印 ，有右看右?沒有回去。
前序遍歷 ：先打印根，然后左?打印 ，再左打印，然后看看有沒有左沒有就看右?右有打印?然后這個節(jié)點沒有左右就回去 ，再回去 ，再看看右有沒有，然后和前面一樣。
后續(xù)遍歷 ：一直看左?打印左，?然后返回看右?的左?打印?再看右的右?是葉子節(jié)點就打印自己?然后發(fā)揮?本節(jié)點?而且它的左右都打印完了就打印自己。
前序遍歷可用于復制一顆二叉樹
中序便歷可用于排序
后序遍歷可以用在文件系統(tǒng)里
查看全部 -
<!DOCTYPE?html> <html> ????<head> ????????<meta?charset="utf-8"?/> ????????<title>Binary?Tree</title> ????</head> ????<body> ????????<script> ????????????/** ?????????????*?二叉排序樹 ?????????????*?新插入的數(shù)據(jù)只是增加在原先的樹上（新加入的結(jié)點找到一個位置，作為原先樹上某個結(jié)點的孩子結(jié)點） ?????????????*?并不會破壞之前已形成的樹 ?????????????*/ ????????????var?Node?=?function(key)?{ ????????????????this.key?=?key; ????????????????this.left?=?null; ????????????????this.right?=?null; ????????????};?//?var?Node?end ????????????//?nodes數(shù)組存儲一下待排序的數(shù)據(jù) ????????????var?nodes?=?[ ????????????????8, ????????????????3, ????????????????10, ????????????????1, ????????????????6, ????????????????14, ????????????????4, ????????????????7 ????????????]; ????????????//?新建一個排序樹對象，是個函數(shù)對象 ????????????var?binaryTree?=?new?BinaryTree(); ????????????//?利用數(shù)組的forEach函數(shù)，依次處理數(shù)組中的數(shù)據(jù)，按下標 ????????????nodes.forEach(function(key)?{ ????????????????//?對于數(shù)組中的每一個值，進行二叉排序樹的插入操作 ????????????????binaryTree.insert(key); ????????????}); ????????????//? ???????????? ????????????var?callback?=?function(key)?{?//?1 ????????????????console.log(key); ????????????} ????????????binaryTree.inOrderTraverse(callback);?//?1 ????????????function?BinaryTree()?{ ????????????????var?root?=?null; ????????????????//?將數(shù)組轉(zhuǎn)換為二叉排序樹 ????????????????this.insert?=?function(key)?{ ????????????????????var?newNode?=?new?Node(key); ????????????????????if(root?===?null)?{ ????????????????????????root?=?newNode; ????????????????????}?else?{ ????????????????????????insertNode(root,?newNode); ????????????????????} ????????????????}; ????????????????var?insertNode?=?function(node,?newNode)?{?//?遞歸地進行節(jié)點的插入 ????????????????????if(newNode.key?<?node.key)?{?//?如果新節(jié)點的值小于這個節(jié)點的父節(jié)點 ????????????????????????if(node.left?===?null)?{ ????????????????????????????//?如果父節(jié)點左孩子節(jié)點為空，則將新節(jié)點置為左孩子節(jié)點 ????????????????????????????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是一個輸出語句方法參數(shù) ????????????????????inOrderTraverseNode(root,?callback); ????????????????}; ????????????????var?inOrderTraverseNode?=?function(node,?callback)?{?//?node節(jié)點為根節(jié)點 ????????????????????if(node?!==?null)?{?//?如果根節(jié)點不為空，即樹存在時，進行先左，在中，在右，并遞歸 ????????????????????????inOrderTraverseNode(node.left,?callback); ????????????????????????//?輸出節(jié)點中的key值 ????????????????????????callback(node.key); ????????????????????????//?這是外部的一個函數(shù)??var?callback?=?function(key)?這里的意思是，上一句進入左子樹，如果上一句的結(jié)點沒有左子樹的話，就打印是一個結(jié)點 ????????????????????????/** ?????????????????????????*? ?????????????????????????*inOrderTraverse中的callback參數(shù)的意義何在？ ?????????????????????????*睡了一覺，自己悟出來了。傳入的callback，實際上就是老師定義的callback函數(shù)， ?????????????????????????*因為老師的callback函數(shù)是定義在binarytree外部的，所以他把這個函數(shù)傳進去，以便后續(xù)調(diào)用。 ?????????????????????????*我自己的代碼，把callback函數(shù)定義在binarytree內(nèi)部了，所以我不傳callback參數(shù)是沒有任何問題的，但是我的callback函數(shù)在其它地方就無法調(diào)用了。... ?????????????????????????* ?????????????????????????*callback只是一個引用，你也可以改成其他名字。為什么要用callback是因為程序員的習慣吧，大家一看就知道這里是一個回調(diào)函數(shù)。? ?????????????????????????*var聲明的函數(shù)和this來聲明的函數(shù)作用域不一樣，var聲明的在外面無法調(diào)用才對，你可以試試，我沒驗證。。。。。。。... ?????????????????????????*/ ????????????????????????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()?{ ????????/** ?????????*?定義節(jié)點 ?????????*?@param?key?int|float?節(jié)點值 ?????????*/ ????????var?node?=?function?(key)?{ ????????????this.key?=?key; ????????????this.left?=?null; ????????????this.right?=?null; ????????} ????????//定義根節(jié)點 ????????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); ????????????} ????????} ????????/** ?????????*?插入數(shù)據(jù)?小左大右 ?????????*?@param?node?obj?節(jié)點數(shù)據(jù) ?????????*?@param?newNode?obj?要插入的節(jié)點數(shù)據(jù) ?????????*/ ????????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); ????????????????} ????????????} ????????} ????????/** ?????????*?查找節(jié)點 ?????????*?@param?key?int|float?查找的節(jié)點值 ?????????*?@param?node?obj?節(jié)點 ?????????*?@returns?obj|null?查找的節(jié)點,?不存在返回null ?????????*/ ????????this.find?=?function?(key,?node?=?root)?{ ????????????return?findNode(key,?node)[1]; ????????} ????????/** ?????????*?判斷節(jié)點是否存在 ?????????*?@param?key?int|float?查找的節(jié)點值 ?????????*?@param?node?obj?節(jié)點 ?????????*?@returns?bool?存在true,?不存在false ?????????*/ ????????this.exists?=?function?(key,?node?=?root)?{ ????????????return?findNode(key,?node)[0]; ????????} ????????/** ?????????*?查找節(jié)點 ?????????*?@param?key?int|float?查找的節(jié)點值 ?????????*?@param?node?obj?節(jié)點 ?????????*?@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?節(jié)點 ?????????*?@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?節(jié)點 ?????????*?@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?節(jié)點 ?????????*?@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?節(jié)點 ?????????*?@returns?{Array} ?????????*/ ????????this.preOrder?=?function?(node?=?root)?{ ????????????var?nodeArr?=?[]; ????????????if?(node?!==?null)?{ ????????????????preOrderNode(node,?nodeArr); ????????????} ????????????return?nodeArr; ????????} ????????/** ?????????*?前序(中->左->右) ?????????*?@param?node?obj?節(jié)點 ?????????*?@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?節(jié)點 ?????????*?@returns?{Array} ?????????*/ ????????this.reOrder?=?function?(node?=?root)?{ ????????????var?nodeArr?=?[]; ????????????if?(node?!==?null)?{ ????????????????reOrderNode(node,?nodeArr); ????????????} ????????????return?nodeArr; ????????} ????????/** ?????????*?后序(左->右->中) ?????????*?@param?node?obj?節(jié)點 ?????????*?@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?節(jié)點 ?????????*?@returns?{*} ?????????*/ ????????this.max?=?function?(node?=?root)?{ ????????????var?newNode?=?maxNode(node); ????????????return?newNode?===?null???null?:?newNode.key; ????????} ????????/** ?????????*?查找一個節(jié)點最大的值 ?????????*?@param?node?obj?節(jié)點 ?????????*?@returns?{*} ?????????*/ ????????var?maxNode?=?function?(node)?{ ????????????if?(node?===?null)?return?null; ????????????while?(node?!==?null?&&?node.right?!==?null)?{ ????????????????node?=?node.right; ????????????} ????????????return?node; ????????} ????????/** ?????????*?最小值 ?????????*?@param?node?obj?節(jié)點 ?????????*?@returns?{*} ?????????*/ ????????this.min?=?function?(node?=?root)?{ ????????????var?newNode?=?minNode(node); ????????????return?newNode?===?null???null?:?newNode.key; ????????} ????????/** ?????????*?查找一個節(jié)點最小值 ?????????*?@param?node?obj?節(jié)點 ?????????*?@returns?{*} ?????????*/ ????????var?minNode?=?function?(node)?{ ????????????if?(node?===?null)?return?null; ????????????if?(node.left?!==?null)?return?minNode(node.left); ????????????return?node; ????????} ????????/** ?????????*?移除一個節(jié)點 ?????????*?@param?key?int|float?要移除的節(jié)點值 ?????????*?@param?node?obj?節(jié)點 ?????????*?@returns?{*} ?????????*/ ????????this.remove?=?function?(key,?node?=?root)?{ ????????????return?removeNode(key,?node); ????????} ????????/** ?????????*?移除節(jié)點 ?????????*?@param?key?int|float?要移除的節(jié)點值 ?????????*?@param?node?obj?節(jié)點 ?????????*?@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(); ????//循環(huán)插入數(shù)據(jù) ????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實現(xiàn)對象的復制，不影響原對象 ????//var?newNode?=?Object.assign({},?node.find(4));// ????var?newNode?=?JSON.parse(JSON.stringify(node.find(4)));//當源對象的屬性值是一個指向?qū)ο蟮囊脮r，應用深度復制 ????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>查看全部
舉報
0/150
提交
取消