章節連結
樹的遍歷是指訪問樹的每個節點，並對它們進行各種操作。訪問的方法可以分為三種：中序、前序和後序。(Wikipedia)
遍歷方法
前序(Pre-Order Traversal)：得知這棵樹的結構。這方法是由根節點開始，先訪問左側和相對左側節點，再來為右側和相對右側節點。
中序(In-Order Traversal)：依照節點的大小順序，由小到大訪問節點。
後序(Post-Order Traversal)：由左到右的順序，從後代節點一層層往上尋找。當子樹的同層和其第一階父層都被訪問完畢時，才會再度往上。
遍歷二元樹
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 |
function BinarySearchTree(){ /*to set node structure*/ let Node = function(key){ this.key = key this.left = null this.right = null } /*to set root*/ let root = null this.insert = (key)=>{ let newNode = new Node(key) let insertNode = (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) } } } if(root===null){ root = newNode }else{ insertNode(root,newNode) } } /*find min, follow left part of the tree*/ this.min = ()=>{ let minNode = (node)=>{ if(node){ while(node && node.left !== null){ node = node.left } return node.key } return null } return minNode(root) } /*find max, follow right part of the tree*/ this.max = ()=>{ let minNode = (node)=>{ if(node){ while(node && node.right !== null){ node = node.right } return node.key } return null } return minNode(root) } /*find particular value whether it is existed*/ this.search = (key)=>{ let 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 true } } return searchNode(root,key) } /* pre-order Traverse*/ let preOrderTraverseNode = (node,callback) => { if(node !== null){ callback(node.key) preOrderTraverseNode(node.left,callback) preOrderTraverseNode(node.right,callback) } } this.preOrderTraverse = (callback) => { preOrderTraverseNode(root,callback) } /* in-order Traverse*/ let inOrderTraverseNode = (node,callback) => { if(node !== null){ inOrderTraverseNode(node.left,callback) callback(node.key) inOrderTraverseNode(node.right,callback) } } this.inOrderTraverse = (callback) => { inOrderTraverseNode(root,callback) } /* post-order Traverse*/ let postOrderTraverseNode = (node,callback) => { if(node !== null){ postOrderTraverseNode(node.left,callback) postOrderTraverseNode(node.right,callback) callback(node.key) } } this.postOrderTraverse = (callback) => { postOrderTraverseNode(root,callback) } } let tree = new BinarySearchTree() function printNode(value){ console.log(value) } tree.insert(11) tree.insert(7) tree.insert(15) tree.insert(5) tree.insert(3) tree.insert(9) tree.insert(8) tree.insert(10) tree.insert(13) tree.insert(12) tree.insert(14) tree.insert(20) tree.insert(18) tree.insert(25) tree.insert(6) console.log(tree.min()) console.log(tree.max()) console.log(tree.search(12)) console.log(tree.search(100)) console.log('-----------------------') tree.preOrderTraverse(printNode) console.log('-----------------------') tree.inOrderTraverse(printNode) console.log('-----------------------') tree.postOrderTraverse(printNode) |
LeetCode 練習記錄
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// 94. binary-tree-inorder-traversal function dfs(result,node){ if (!node) return if(node.left){ dfs(result,node.left) } result.push(node.val) if(node.right){ dfs(result,node.right) } return } var inorderTraversal = function(root) { let result = [] dfs(result,root) return result }; |
