二叉樹in JavaScript
1946 ワード
function Node(data, left, right) {
this.data = data
this.left = left
this.right = right
}
Node.prototype = {
constructor: Node,
show: function () {
return this.data
}
}
function BSTree() {
this.root = null
}
BSTree.prototype = {
constructor: BSTree,
//
insert: function (data) {
var node = new Node(data, null, null)
if (this.root == null) {
this.root = node
} else {
//
// current
var current = this.root
var parent
while (1) {
parent = current
if (data < current.data) {
// current
current = current.left
// null
if (!current) {
//
parent.left = node
break
}
} else {
current = current.right
if (!current) {
parent.right = node
break
}
}
}
}
},
//
inOrder: function (node) {
if (node) {
this.inOrder(node.left)
console.log(node.show())
this.inOrder(node.right)
}
},
//
preOrder: function (node) {
if (node) {
console.log(node.show())
this.inOrder(node.left)
this.inOrder(node.right)
}
},
//
postOrder: function (node) {
if (node) {
this.inOrder(node.left)
this.inOrder(node.right)
console.log(node.show())
}
}
}
var nums = new BSTree()
nums.insert(23)
nums.insert(45)
nums.insert(16)
nums.insert(37)
nums.insert(3)
nums.insert(99)
nums.insert(22)
nums.inOrder(nums.root)
console.log(nums)