最近正在看慕课网的《Javascript实现二叉树算法》课程，现把看到的东西记录下来。
什么是二叉树？简单来说，二叉树是一种具有层级特性的数据结构，一棵树包含多个节点。节点自身含有一个属性，就是他所代表的数值。
排序二叉树具有以下特征：
1、如果他的左子树上不为空，则他的左子树上所有节点的值都小于根节点上的值；
2、如果他的右子树上不为空，则他的右子树上所有节点的值都小于根节点上的值；
3、他的左、右子树也是二叉排序树；
4、没有完全相等的两个节点；
二叉树
二叉排序树的代码实现
<script>
var BinaryTree = function(){
var Node = function(key){
this.key = key;
this.left = null;
this.right = null;
}
var rootNode = null;
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.insert = function(key){
var newNode = new Node(key);
if( rootNode == null ){
rootNode = newNode;
}else{
insertNode(rootNode , newNode);
}
}
}
var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree();
nodes.forEach(function(key){
binaryTree.insert(key)
})
</script>
二叉树的中序遍历
从根节点开始，如果存在左子树就开始遍历左子树，然后再遍历右子树，最后输出根节点的值。遍历左、右子树时也是先遍历左子树，然后遍历右子树，最少输出改接点，如此循环。
代码实现：
<script>
var BinaryTree = function(){
var Node = function(key){
this.key = key;
this.left = null;
this.right = null;
}
var rootNode = null;
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.insert = function(key){
var newNode = new Node(key);
if( rootNode == null ){
rootNode = newNode;
}else{
insertNode(rootNode , newNode);
}
}
var inOrderTraverseNode = function(node , callback){
if( node !== null ){
inOrderTraverseNode(node.left , callback);
callback(node.key);
inOrderTraverseNode(node.right , callback);
}
}
this.inOrderTraverse = function(callback){
inOrderTraverseNode(rootNode , callback)
}
}
var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree();
nodes.forEach(function(key){
binaryTree.insert(key)
})
var callback = function(key){
console.log(key)
}
console.log("中序遍历")
// 中序遍历
binaryTree.inOrderTraverse(callback);
</script>
打印出来的结果
中序遍历
二叉树的前序遍历
从根节点开始，先输出当前节点，如果存在左子树就开始遍历左子树，然后再遍历右子树。遍历左、右子树的规则同上。
代码实现：
<script>
var BinaryTree = function(){
var Node = function(key){
this.key = key;
this.left = null;
this.right = null;
}
var rootNode = null;
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.insert = function(key){
var newNode = new Node(key);
if( rootNode == null ){
rootNode = newNode;
}else{
insertNode(rootNode , newNode);
}
}
var preOrderTraverseNode = function(node , callback){
if( node !== null ){
callback(node.key);
preOrderTraverseNode(node.left , callback);
preOrderTraverseNode(node.right , callback);
}
}
this.preOrderTraverse = function(callback){
preOrderTraverseNode(rootNode , callback);
}
}
var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree();
nodes.forEach(function(key){
binaryTree.insert(key)
})
var callback = function(key){
console.log(key)
}
console.log("前序遍历")
// 前序遍历
binaryTree.preOrderTraverse(callback)
</script>
打印出来的结果
前序遍历
二叉树的后序遍历
代码实现：
<script>
var BinaryTree = function(){
var Node = function(key){
this.key = key;
this.left = null;
this.right = null;
}
var rootNode = null;
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.insert = function(key){
var newNode = new Node(key);
if( rootNode == null ){
rootNode = newNode;
}else{
insertNode(rootNode , newNode);
}
}
var nextOrderTraverseNode = function(node , callback){
if( node !== null ){
nextOrderTraverseNode(node.left , callback);
nextOrderTraverseNode(node.right , callback);
callback(node.key);
}
}
this.nextOrderTraverse = function(callback){
nextOrderTraverseNode(rootNode , callback);
}
}
var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree();
nodes.forEach(function(key){
binaryTree.insert(key)
})
var callback = function(key){
console.log(key)
}
console.log("后序遍历")
// 后序遍历
binaryTree.nextOrderTraverse(callback)
</script>
打印结果
后序遍历
查找最小值
<script>
var BinaryTree = function(){
var Node = function(key){
this.key = key;
this.left = null;
this.right = null;
}
var rootNode = null;
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.insert = function(key){
var newNode = new Node(key);
if( rootNode == null ){
rootNode = newNode;
}else{
insertNode(rootNode , newNode);
}
}
var minNode = function(node){
if(node){
while(node && node.left !== null){
node = node.left;
}
return node.key;
}
return null;
}
this.min = function(){
return minNode(rootNode);
}
}
var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree();
nodes.forEach(function(key){
binaryTree.insert(key)
})
console.log("查找最小值")
// 查找最小值
console.log(binaryTree.min())
</script>
查找最大值
<script>
var BinaryTree = function(){
var Node = function(key){
this.key = key;
this.left = null;
this.right = null;
}
var rootNode = null;
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.insert = function(key){
var newNode = new Node(key);
if( rootNode == null ){
rootNode = newNode;
}else{
insertNode(rootNode , newNode);
}
}
var maxNode = function(node){
if( node ){
while(node && node.right !== null){
node = node.right
}
return node.key
}
return null;
}
this.max = function(){
return maxNode(rootNode);
}
}
var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree();
nodes.forEach(function(key){
binaryTree.insert(key)
})
console.log("查找最大值")
// 查找最大值
console.log(binaryTree.max())
</script>
查找某个值
<script>
var BinaryTree = function(){
var Node = function(key){
this.key = key;
this.left = null;
this.right = null;
}
var rootNode = null;
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.insert = function(key){
var newNode = new Node(key);
if( rootNode == null ){
rootNode = newNode;
}else{
insertNode(rootNode , newNode);
}
}
var searchNode = function(num ,node){
if( node == null ){
return false;
}
if( node.key < num ){
return searchNode(num , node.right)
}else if( node.key > num ){
return searchNode(num , node.left)
}else{
return true;
}
}
this.search = function(num){
return searchNode(num , rootNode);
}
}
var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree();
nodes.forEach(function(key){
binaryTree.insert(key)
})
console.log("查找某个值")
// 查找某个值
var num = 7;
console.log(binaryTree.search(num))
</script>
未完待续...
网友评论