英文:binary search tree。
前序遍历:8 3 1 6 4 7 10 14 13
中序遍历:1 3 4 6 7 8 10 13 14
后序遍历:1 4 7 6 3 13 14 10 8
层次遍历:8 3 10 1 6 14 4 7 13
// 节点对象的构造函数
function Node (data, left, right) {
this.data = data
this.left = left
this.right = right
}
Node.prototype.getData = function () {
return this.data
}
// 二叉树的构造函数
function BST () {
this.root = null
}
// 插入方法
BST.prototype.insert = function (data) {
var n = new Node(data, null, null)
if (this.root === null) {
this.root = n
} else {
var current = this.root
var parent
while (true) {
parent = current
if (data < current.data) {
current = current.left
if (current === null) {
parent.left = n
break
}
} else {
current = current.right
if (current === null) {
parent.right = n
break
}
}
}
}
}
var nums = new BST()
nums.insert(8)
nums.insert(3)
nums.insert(10)
nums.insert(1)
nums.insert(6)
nums.insert(14)
nums.insert(4)
nums.insert(7)
nums.insert(13)
// 节点对象的构造函数
function Node (data, left, right) {
this.data = data
this.left = left
this.right = right
}
Node.prototype.getData = function () {
return this.data
}
// 二叉树的构造函数
function BST () {
this.root = null
}
// 插入方法
BST.prototype.insert = function (data) {
var n = new Node(data, null, null)
if (this.root === null) {
this.root = n
} else {
var current = this.root
var parent
while (true) {
parent = current
if (data < current.data) {
current = current.left
if (current === null) {
parent.left = n
break
}
} else {
current = current.right
if (current === null) {
parent.right = n
break
}
}
}
}
}
var nums = new BST()
nums.insert(8)
nums.insert(3)
nums.insert(10)
nums.insert(1)
nums.insert(6)
nums.insert(14)
nums.insert(4)
nums.insert(7)
nums.insert(13)
这个算法很好实现,主要是容易记混怎么样算前序遍历、中序遍历、后续遍历,其遍历顺序分别为:
// 前序遍历二叉树
BST.prototype.preOrder = function (node) {
if (node !== null) {
console.log(node.getData())
this.preOrder(node.left)
this.preOrder(node.right)
}
}
// 中序遍历二叉树
BST.prototype.inOrder = function (node) {
if (node !== null) {
this.inOrder(node.left)
console.log(node.getData())
this.inOrder(node.right)
}
}
// 后序遍历二叉树
BST.prototype.postOrder = function (node) {
if (node !== null) {
this.postOrder(node.left)
this.postOrder(node.right)
console.log(node.getData())
}
}
// 测试
nums.inOrder(nums.root)
// 依次输出如下内容:
// 1 3 4 6 7 8 10 13 14
// 前序遍历二叉树
BST.prototype.preOrder = function (node) {
if (node !== null) {
console.log(node.getData())
this.preOrder(node.left)
this.preOrder(node.right)
}
}
// 中序遍历二叉树
BST.prototype.inOrder = function (node) {
if (node !== null) {
this.inOrder(node.left)
console.log(node.getData())
this.inOrder(node.right)
}
}
// 后序遍历二叉树
BST.prototype.postOrder = function (node) {
if (node !== null) {
this.postOrder(node.left)
this.postOrder(node.right)
console.log(node.getData())
}
}
// 测试
nums.inOrder(nums.root)
// 依次输出如下内容:
// 1 3 4 6 7 8 10 13 14
根据前序遍历访问的顺序,优先访问根结点,然后再分别访问左孩子和右孩子。 即对于任一结点,其可看做是根结点,因此可以直接访问,访问完之后,若其左孩子不为空, 按相同规则访问它的左子树;当访问其左子树时,再访问它的右子树。因此其处理过程如下:
对于任一结点P:
访问结点P,并将结点P入栈;
判断结点P的左孩子是否为空,若为空,则取栈顶结点并进行出栈操作,并将栈顶结点的右孩子置为当前的结点P,循环至1;若不为空,则将P的左孩子置为当前的结点P;
直到P为NULL并且栈为空,则遍历结束。
function preOrder (bst) {
let p = bst.root
const arr = []
while (p !== null || arr.length > 0) {
while (p !== null) {
console.log(p.getData())
arr.push(p)
p = p.left
}
if (arr.length > 0) {
p = arr.pop()
p = p.right
}
}
}
function preOrder (bst) {
let p = bst.root
const arr = []
while (p !== null || arr.length > 0) {
while (p !== null) {
console.log(p.getData())
arr.push(p)
p = p.left
}
if (arr.length > 0) {
p = arr.pop()
p = p.right
}
}
}
根据中序遍历的顺序,对于任一结点,优先访问其左孩子,而左孩子结点又可以看做一根结点, 然后继续访问其左孩子结点,直到遇到左孩子结点为空的结点才进行访问,然后按相同的规则访问其右子树。因此其处理过程如下:
对于任一结点P,
若其左孩子不为空,则将P入栈并将P的左孩子置为当前的P,然后对当前结点P再进行相同的处理;
若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后将当前的P置为栈顶结点的右孩子;
直到P为NULL并且栈为空则遍历结束。
function inOrder (bst) {
let p = bst.root
const arr = []
while (p !== null || arr.length > 0) {
while (p !== null) {
arr.push(p)
p = p.left
}
if (arr.length > 0) {
p = arr.pop()
console.log(p.getData())
p = p.right
}
}
}
function inOrder (bst) {
let p = bst.root
const arr = []
while (p !== null || arr.length > 0) {
while (p !== null) {
arr.push(p)
p = p.left
}
if (arr.length > 0) {
p = arr.pop()
console.log(p.getData())
p = p.right
}
}
}
后续遍历比前中/序遍历是要麻烦一些的。
遍历顺序:左右根。左路的遍历和上面的思路是类似的,区别是元素出栈时不能直接打印, 因为如果有没访问过的右侧子树的话,需要先访问右侧子树。 右侧子树访问结束后才访问根(一些列子树的根)。
function postOrder (bst) {
let p = bst.root
let last = null
const arr = []
while (p !== null || arr.length > 0) {
while (p !== null) {
arr.push(p)
p = p.left
}
if (arr.length > 0) {
p = arr[arr.length - 1] // 栈顶元素
// 当p不存在右子树或右子树已被访问过的话,直接访问当前节点数据
if (!p.right || p.right === last) {
p = arr.pop()
console.log(p.getData())
last = p // 记录上一次访问过的节点
p = null // 这个容易漏掉,避免下个循环继续访问左子树
} else {
p = p.right
}
}
}
}
function postOrder (bst) {
let p = bst.root
let last = null
const arr = []
while (p !== null || arr.length > 0) {
while (p !== null) {
arr.push(p)
p = p.left
}
if (arr.length > 0) {
p = arr[arr.length - 1] // 栈顶元素
// 当p不存在右子树或右子树已被访问过的话,直接访问当前节点数据
if (!p.right || p.right === last) {
p = arr.pop()
console.log(p.getData())
last = p // 记录上一次访问过的节点
p = null // 这个容易漏掉,避免下个循环继续访问左子树
} else {
p = p.right
}
}
}
}