概念
二叉树：树中每个节点最多只能有两个子节点。
二叉搜索树（BST）：二叉树的一种，但是它只允许你在左侧节点存储(比父节点)小的值， 在右侧节点存储(比父节点)大(或者等于)的值。
比如：
11
7 13
5 9
3
代码中存储结构如下
{
key: 11, // root 指向 key 为 11 的对象。
left: {
key: 7,
left: {
key: 5,
left: {
key: 3,
left: null,
right: null
},
right: null
},
right: {
key: 9,
left: null,
right: null
}
},
right: {
key: 13,
left: null,
right: null
}
}
代码实现及注释
var Node = function(key){
this.key = key;
this.left = null;
this.right = null;
var root = null;
this.insert = function (key) {
var newNode = new Node(key);
if(root === null){
root = newNode
}else{
insertNode(root,newNode)
}
}
var insertNode = function (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)
}
}
}
// 递归方式进行中序遍历，先访问左子树，然后访问根，最后访问右子树
this.inOrderTraverse = function (callback) {
inOrderTraverseNode(root,callback)
}
var inOrderTraverseNode = function (node, callback) {
if(node !== null){
inOrderTraverseNode(node.left,callback)
callback(node.key)
inOrderTraverseNode(node.right,callback)
}
}
// 递归方式进行先序遍历，先访问根，然后访问左子树和右子树
this.proOderTraverse = function (callback) {
proOderTraverseNode(root,callback)
}
var proOderTraverseNode = function (node,callback) {
if(node !== null){
callback(node.key);
proOderTraverseNode(node.left,callback)
proOderTraverseNode(node.right,callback)
}
}
// 递归方式进行后序遍历，先访问左子树和右子树，最后访问根
this.postOrderTraverse = function (callback) {
postOrderTraverseNode(root,callback)
}
var postOrderTraverseNode = function (node,callback) {
if(node !== null){
postOrderTraverseNode(node.left,callback)
postOrderTraverseNode(node.right,callback)
callback(node.key)
}
}
this.values = function (traversFunc) {
var keyList = [];
this[traversFunc](function (key) {
keyList.push(key)
})
return keyList
}
// 非递归方式实现中序遍历，通过栈的方式实现
this.inOrderTraverseUnRec = function (calback) {
// 存在跟节点时才进行遍历
if(root !== null){
// 使用数组实现一个栈的存储
var items = [], node = root;
// 当栈不为空或者当前的节点时存在时都会进行如下操作
while(items.length !== 0 && node){
if(node){
// node存在时向左遍历整个树结构，将最左边的节点push到栈中
items.push(node);
node = node.left
}else{
// 如果node不存在时，可能是上次遍历的左节点或右节点不存在，这时是需要pop栈中之前存放的一个节点，对该节点进行其循环操作
node = items.pop();
calback(node.key)
node = node.right
}
}
}
}
// 非递归法实现先序遍历法，先访问根节点，然后访问左右子树
this.preOrderTraverseUnRec = function (calback) {
if (root !== null) {
var items = [];
// 最初将根节点push到栈中
items.push(root);
// 当栈不为空时进行如下操作，每次都将一个节点push到栈中，栈为空时是将节点遍历完了
while (item.length !== 0) {
// 从根节点开始，先访问当前节点，然后将当前节点的右、左节点一次push到栈中，因为后入先出，每次循环都pop出一个节点
var node = items.pop();
if (calback) {
calback(node.key)
}
if (node.right) {
item.push(node.right)
}
if (node.left) {
item.push(node.left)
}
}
}
}
// 非递归法实现后序遍历法，先访左右子树节点，然后访问根节点
this.postOrderTraverseUnRec = function (calback) {
if (root !== null) {
var items1 = [],
items2 = [],
node;
// 非递归法实现后序遍历需要用到两个栈，第一个栈用于先序遍历，
// 第二个栈用于存放先序遍历的结果，该栈出栈的结果即为后序遍历结果
items1.push(root)
while (items1.length !== 0) {
node = items1.pop();
items2.push(node);
// 此处需要进入到另一个栈出栈，左右节点进入到第二个栈的顺序与先序遍历有所不同
if (node.left) {
items1.push(node.left)
}
if (node.right) {
items1.push(node.right)
}
}
while (items2.length !== 0) {
node = items2.pop()
if (calback) {
calback(node.key)
}
}
}
}
}
网友评论