JS数据结构与算法-二叉树和二叉查找树
树是一种非线性的数据结构，以分层的方式存储数据。树被用来存储具有层级关系的结构，比如文件系统中的文件；树还被用来存储有序列表。
- 二叉树与二叉查找树 二叉树是一种特殊的树，它的子节点个数不超过两个；一个父节点的两个子节点分别称为左节点和右节点。 二叉查找树(BST)是一种特殊的二叉树；相对较小的值保持在左节点中，较大的值保存在右节点中。
- js代码实现二叉查找树
- 首先我们先定义一个Node对象，用于保存数据(data)，也保存和其他节点的链接（left和right）。
function Node(data,left,right) {
this.data = data;
this.left = left;
this.right = right;
this.show = show;
}- 定义show方法
function show() {
return this.data;
}- 创建一个类，用来表示二叉查找树(BST)
function BST() {
//将根节点初始化为null
this.root = null;
//insert方法用来向树中加入新节点
this.insert = insert;
//inOrder方法用来遍历树
this.inOrder = inOrder;
}- 定义insert方法
function insert(data) {
//首先实例化一个新的Node对象
var n = new Node(data,null,null);
//检查BST是否有根节点，如果没有，那么是颗新树，传入的该节点就是根节点
if(this.root == null) {
this.root = n;
}else {
//反之就定义一个current变量用于保存当前节点（根节点）
var current = this.root;
var parent;
while(true) {
parent = current;
//如果插入的节点保存的数据小于当前节点，且当前节点的左节点为null，就将这个新的节点插入到这个位置
if(data < current.data) {
current = current.left;
if(current == null) {
parent.left = n;
break;
}
}else {
//反之，同理
current = current.right;
if(current == null) {
parent.right = n;
break;
}
}
}
}
}- 遍历二叉查找树 有三种遍历BST的方式 中序：中序遍历按照节点上的键值，以升序访问BST上的所有节点。 先序：先序遍历先访问根节点，然后以同样的方式访问左子树和右子树。 后序：后序遍历先访问叶子节点(没有任何子节点的节点)，从左子树到右子树，再到根节点。 这三种遍历理解了一种的实现代码，其他的都好理解，所以我着重写一下我对js代码实现中序遍历过程的具体理解。
- js代码实现中序遍历 中序遍历使用递归的方式，以升序访问树中所有节点，先访问左子树，在访问根节点，最后访问右子树。
function inOrder(node) {
if(!(node == null)) {
inOrder(node.left);
console.log(node.show());
inOrder(node.right);
}
}
//比如：
var nums = new BST();
nums.insert(56);
nums.insert(22);
nums.insert(81);
nums.insert(10);
nums.insert(30);
nums.insert(77);
nums.insert(92);
inOrder(nums.root); //10 22 30 56 81 77 92①先递归遍历左子树到尽头，将每一项push到一个数组中，先是得到这样的一个结果[56,22,10]。
②递归完成了，现在pop出第一项即10开始遍历右子树,为undefined。
③然后pop出第二项即22，遍历右子树，得30，因为console是在先递归左子树后打印的，所以把30插到(push)56和22中间，结果为[56,30,22,10]。
④然后pop出第三项即30，undefined。
⑤然后pop出第四项即56，遍历该右子树，得结果[92,81,56,30,22,10]
⑥然后pop出第五项即81，发现有左子树77，所以push进去，又因为console代码在中间，所以要放到92和81中间，结果[92,81,77,56,30,22,10]所以最后打印结果为10,22,30,56,77,81,92
理解了一个，后面的先序遍历和后序遍历就没问题了，只是console代码放置的位置不同。主要是理解递归。
- 先序遍历
function inOrder(node) {
if(!(node == null)) {
console.log(node.show());
inOrder(node.left);
inOrder(node.right);
}
}
inOrder(nums.root);- 后序遍历
function inOrder(node) {
if(!(node == null)) {
inOrder(node.left);
inOrder(node.right);
console.log(node.show());
}
}
inOrder(nums.root);参考学习：
《数据结构与算法JavaScript描述》 《高程》
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.08.31 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读