本篇文章主要介绍了js实现二叉查找树的建立以及一些遍历方法实现,具有一定的参考价值,感兴趣的小伙伴们可以参考一下。
二叉查找树是由节点和边组成的。
我们可以定义一个节点类Node,里面存放节点的数据,及左右子节点,再定义一个用来显示数据的方法:
//以下定义一个节点类
function Node(data,left,right){
// 节点的键值
this.data = data;
// 左节点
this.left = left;
// 右节点
this.right = left;
// 显示该节点的键值
this.show = show;
}
// 实现show方法
function show(){
return this.data;
}
再定义一个二叉查找树类BST,该类中有定义树的根节点,初始化为null,然后定义插入节点的方法,还有一边遍历的方法:
// 二叉查找树BST
// 有一个节点属性,还有一些其他的方法,以下定义一个二叉查找树BST类
function BST(){
// 根节点初始化为空
this.root = null;
// 方法
// 插入
this.insert = insert;
// 中序遍历
this.inorder = inorder;
// 先序遍历
this.preorder = preorder;
// 后序遍历
this.postorder = postorder;
}
//实现insert插入方法
function insert(data){
// 创建一个节点保存数据
var node = new Node(data,null,null);
// 下面将节点node插入到树中
// 如果树是空的,就将节点设为根节点
if(!this.root){
this.root = node;
}else{ //树不为空
// 判断插在父节点的左边还是右边
// 所以先要保存一下父节点
// var parent = this.root;
var current = this.root;
var parent;
// 如果要插入的节点键值小于父节点键值,则插在父节点左边,
// 前提是父节点的左边为空,否则要将父节点往下移一层,
// 然后再做判断
while(true){
// data小于父节点的键值
parent = current;
if(data <p>测试:</p><p class="jb51code"><br></p><pre class="brush:js;">// 后序遍历(左右中)
function postorder(node){
if(node){
postorder(node.left);
postorder(node.right);
console.log(node.show());
}
}
// 实例化一个BST树
var tree = new BST();
// 添加节点
tree.insert(30);
tree.insert(14);
tree.insert(35);
tree.insert(12);
tree.insert(17);
// 中序遍历
tree.inorder(tree.root);
// 先序遍历
tree.preorder(tree.root);
// 后序遍历
tree.postorder(tree.root);
结果:
中序遍历:
KeystoneJS 是一个功能强大的开源无头 CMS,适用于 Node.js,它根据您的模式定义自动生成 GraphQL API 和基于 React 的管理界面。由 Thinkmill 构建,支持 PostgreSQL 和 SQLite、自定义访问控制、钩子、虚拟字段和基于文档的富文本编辑。

先序遍历:

后序遍历:











