共计 1108 个字符,预计需要花费 3 分钟才能阅读完成。
接数据结构 - 初学二叉树创立文章后,咱们在来对二叉树进行中序排序,输入一个有序数据。
二叉树的中序遍历就是首先遍历左子树,而后拜访以后节点,最初遍历右子树。对于上面的二叉树,中序遍历后果如下:
这是思路最简略的办法,容易想到并且容易实现。递归的终止条件是以后节点是否为空。首先递归调用遍历左子树,而后拜访以后节点,最初递归调用右子树。代码如下:
function BinaryTree(){var Node = function(key){
this.key = key;
this.left = null;
this.right = null;
}
// 插入节点 大于旧节点,放在 node.right 小于旧节点,放在 node.left
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)
}
}
}
var root = null;
// 创立节点并插到相应的地位
this.insert = function(key){var newNode = new Node(key)
if(root === null){root = newNode}else{insertNode(root,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(root,callback)
}
}
var nodes = [8,3,10,1,6,14,4,7,13]
var binaryTree = new BinaryTree()
nodes.forEach(key =>{binaryTree.insert(key)
})
// 回调函数只做打印以后值
var callback = function(key){console.log(key)
}
binaryTree.inOrderTraverse(callback)
正文完
发表至: javascript
2021-04-22