1.创建排序二叉树的构造函数
/**
* 创建排序二叉树的构造函数
* @param valArr 排序二叉树中节点的值
* @constructor
*/
function BinaryTree(valArr) {
function Node(val) {
this.value = val;
this.left = null;
this.right = null;
}
var root = null;
valArr.forEach(function (val) {
var newNode = new Node(val);
if(root === null){
root = newNode;
} else {
this.insetNode(root,newNode);
}
},this);
this.root = root;
}
2.向排序二叉树中插入节点
// 向二叉树中插入节点
BinaryTree.prototype.insetNode = function (node, newNode) {
if(newNode.value > node.value){
if(node.right === null){
node.right = newNode;
} else {
this.insetNode(node.right,newNode);
}
} else {
if(node.left === null){
node.left = newNode;
} else {
this.insetNode(node.left,newNode);
}
}
};
3.中序遍历
// 中序遍历
BinaryTree.prototype.LFR = function () {
const result = [];
function computed(node) {
if(node !== null ){
computed(node.left);
result.push(node.value);
computed(node.right);
}
}
computed(this.root);
return result;
};
4.前序遍历
// 前序遍历
BinaryTree.prototype.FLR = function () {
const result = [];
function computed(node) {
if(node !== null ){
result.push(node.value);
computed(node.left);
computed(node.right);
}
}
computed(this.root);
return result
};
5.后序遍历
// 后序遍历
BinaryTree.prototype.RFL = function () {
const result = [];
function computed(node) {
if(node !== null ){
computed(node.right);
result.push(node.value);
computed(node.left);
}
}
computed(this.root);
return result
};
6.获取最小值
// 获取二叉树中的最小值
BinaryTree.prototype.getMin = function (node) {
var min = null;
function computed(node) {
if(node){
if(node.left){
computed(node.left);
} else {
min = node.value;
}
}
}
computed(node || this.root);
return min;
};
7.获取最大值
// 获取二叉树中的最大值
BinaryTree.prototype.getMax = function (node) {
var Max = null;
function computed(node) {
if(node){
if(node.right){
computed(node.right);
} else {
Max = node.value;
}
}
}
computed(node || this.root);
return Max;
};
8.查找给定的值
// 查找给定值
BinaryTree.prototype.findVal = function (val,node) {
function find(node) {
if(node){
if(node.value === val) return true;
else if(val > node.value) return find(node.right);
else {
return find(node.left);
}
} else {
return false;
} }
return find(node || this.root);
};
9.删除节点
// 删除节点
BinaryTree.prototype.removeNode = function (val,node) {
function remove(val,node) {
if(!node) return null;
if(val > node.value) {
node.right = remove.call(this,val,node.right);
} else if(val < node.value){
node.left = remove.call(this,val,node.left);
} else {
// 要删除的节点没有左孩子也没有右孩子
if(node.right === null && node.left === null){
return null;
}
// 只有右孩子没有左孩子
else if(node.right && node.left === null){
return node.right;
}
// 只有左孩子没有右孩子
else if (node.left && node.right === null) {
return node.left;
}
// 有左孩子也有右孩子
else {
var min = this.getMin(node.right);
node.value = min;
node.right = remove.call(this,min, node.right);
return node;
}
}
return node;
}
remove.call(this,val,node || this.root);
};
10.使用上面的方法
var binaryTree = new BinaryTree([10,4,2,14,3,15,13,12,6,9]);
console.log('中序遍历',binaryTree.LFR());
console.log('前序遍历',binaryTree.FLR());
console.log('后序遍历',binaryTree.RFL());
console.log('最小值',binaryTree.getMin());
console.log('最大值',binaryTree.getMax());
console.log(binaryTree.findVal(4));
binaryTree.removeNode(3);