二叉树 in JavaScript
2018-02-28 本文已影响0人
康乐芳华
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)