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,想提升一下自身的基础水平。对于数据结构这一课程,我认为难度还是比较高的。但是非常的重要,可以有效的提升自己的逻辑思维能力,以及理解能力。