TOC
JavaScript 二叉树
最近在学习一些数据结构方面的知识，稍作记录。
二叉树的创建
首先二叉树是一种树形的结构，那么他的特点就是每个构建树的节点最多只有两个子节点。他的效率非常之高，比如二分法查找他的路线就类似于一个二叉树。
function CreatTree() {
this.root = null;
}//创建一个树
CreatTree.prototype.CreatNode = function (data,l,r) {
//小心大小比较必须两个都是数字 如果是字符串永远为真
data = parseInt(data);
this.data = data;
this.right = r;
this.left = l;
this.show = show;
return this;
} //创建一个节点
function show() {
console.log(this.data);
}//展示节点的数据
var tree = new CreatTree();
首先，我们创建一个一个基本的工具代码，我们拥有了一棵树，以及节点的创建和展示方法。接下来我们要做的就是创建一个添加节点的方法。通常我们将值小、常用的值放在子left节点，值大、不常用的值放在子right。
CreatTree.prototype.addNode = function (data) {
//自动添加节点
var new_node = new this.CreatNode(data,null,null);
if(this.root === null){
this.root = new_node;
return;
}
//判断步骤
var curr_node = this.root;
//首先执行大小判断 沿着路线开始判断是否目标位置是否为空 插入 如果不为空，就进一步设置下个参照节点
while (curr_node){
// console.log(new_node.data < curr_node.data);
if(new_node.data <= curr_node.data){
if(curr_node.left === null){
curr_node.left = new_node;
break;
}else {
curr_node = curr_node.left;
}
}else if(new_node.data > curr_node.data){
if(curr_node.right === null){
curr_node.right = new_node;
break;
}else {
curr_node = curr_node.right;
}
}
}
}
//开始添加
tree.addNode("23");
tree.addNode("45");
tree.addNode("16");
tree.addNode("1");
tree.addNode("3");
tree.addNode("99");
他的结构也很简单，按序挂载，对比与参照节点（最初是root节点）的大小关系(大于参照节点放在right,小于放在left)，如果参照节点left/right已经有了，那么就将参照节点更新，直到成功挂载为止。
二叉树的遍历
二叉树的遍历方式主要有两种，一为利用递归函数，二为利用栈堆保存快照。 这两种方式的行走路线是相同的。这两者方式其实都是利用了数据保存和回溯。可能堆栈的性能会更高占用的内存更少，但是递归函数更加简单明了
1.递归方式遍历
function ergodicTree(node) {
if(node === null){
return
}
node.show();
ergodicTree(node.left);
ergodicTree(node.right);
}
// 遇到一个节点首先判断是不是不存在 接着打印他 然后进行递归调用
ergodicTree(tree.root);
2.栈堆方式遍历
var inOrderUnRecur = function(node) {
if(!node) {
throw new Error('Empty Tree')
}
var stack = [] //stack存储器
while(stack.length !== 0 || node) {
if(node) {
stack.push(node)
node = node.left
} else {
node = stack.pop()
node.show();
node = node.right
}
}
}
这个遍历函数可以被看作两部分操作。第一部分是一直向左走，直到走不通 不断将遇到的节点入栈。第二部分首先出栈检查他的子右节点是否存在，存在则调用第一部分。不存在则调用继续出栈。
根据遍历时顺序的不同，可以被分为三种情况 分别为，前序遍历，中序遍历，后序遍历。实质上一个节点的被经过顺序正好有三次，比如有一个A节点，他第一次被访问是入栈前后 第二次访问出栈前 第三次访问是出栈后。所有只要正确的修改show()的放置位置就可以更改他的遍历顺序。但路线不变。
查找二叉树
//搜索对应值
var search = function(sdata,tree) {
var currentNode = tree.root;
while(currentNode != null) {
if(sdata === currentNode.data){
return currentNode;
}else if(sdata < currentNode.data){
currentNode = currentNode.left;
}else if(sdata > currentNode.data){
currentNode = currentNode.right;
}
}
return null;
}
// 二叉树查找最小值
function getMin(tree){
var current = tree.root;
while(!(current.left == null)) {
current = current.left;
}
return current.data;
}
// 二叉树上查找最大值
function getMax(tree) {
var current = tree.root;
while(!(current.right == null)) {
current = current.right;
}
return current.data;
}
二叉树的删除
二叉树的删除操作会有四种基本情况。 - 拥有一个左子节点 - 拥有一个右子节点 - 拥有两个子节点 - 没有任何子节点
相对而言，最简单的是没有子节点，我们只需要将他的父节点的指针指向null（在递归方式中就是递归底层返回一个null） 复杂一点的是拥有一个子节点，我们可以让他的父节点的指针指向他的子节点。
更复杂的是拥有两个子节点，我们可以把相对复杂的问题简单化。（找到他右子树中的最小节点/找到他左子树的最大节点）将找到的这个节点替换到将被删除的节点。所以有两步，第一步是找到那个节点，然后替换将要删除节点。第二部是将原本的那个节点的父节点指向null。
function removeNode(root,data) {
var tmp;
rData = root.data;
if(data < rData){
root.left = removeNode(root.left,data); //准备最后一层返回reutn
}else if(data > rData){
root.right = removeNode(root.right,data)
}else {
if(root.right && root.left){
tmp = getMin(root.right);
root.data = tmp;//替换内容 接下来就是递归删除那个tmp
root.right = removeNode(root.right,tmp.data);
} else {
if(!root.right){
root = root.left;
}else if(!root.left){
root = root.right
}
}//主体删除部分
}
// console.log(root.data);
return root;
}
在这段代码之中，最底层的递归会返回一个对象 以供上一层的root.right来指向，要是没有任何子节点就会指向Null也就是被删除了。
最近开始看一些Mooc，想提升一下自身的基础水平。对于数据结构这一课程，我认为难度还是比较高的。但是非常的重要，可以有效的提升自己的逻辑思维能力，以及理解能力。