JS数据结构与算法二叉树和二叉查找树 [复制链接]

树是一种非线性的数据结构，以分层的方式存储数据。树被用来存储具有层级关系的结构，比如文件系统中的文件；树还被用来存储有序列表

二叉树与二叉查找树二叉树是一种特殊的树，它的子节点个数不超过两个；一个父节点的两个子节点分别称为左节点和右节点。

二叉查找树(BST)是一种特殊的二叉树；相对较小的值保持在左节点中，较大的值保存在右节点中。

js代码实现二叉查找树?首先我们先定义一个Node对象，用于保存数据(data)，也保存和其他节点的链接（left和right）。

functionNode(data,left,right){this.data=data;this.left=left;this.right=right;this.show=show;}

?定义show方法

functionshow(){returnthis.data;}

?创建一个类，用来表示二叉查找树(BST)

functionBST(){//将根节点初始化为nullthis.root=null;//insert方法用来向树中加入新节点this.insert=insert;//inOrder方法用来遍历树this.inOrder=inOrder;}

?定义insert方法

functioninsert(data){//首先实例化一个新的Node对象varn=newNode(data,null,null);//检查BST是否有根节点，如果没有，那么是颗新树，传入的该节点就是根节点if(this.root==null){this.root=n;}else{//反之就定义一个current变量用于保存当前节点（根节点）varcurrent=this.root;varparent;while(true){parent=current;//如果插入的节点保存的数据小于当前节点，且当前节点的左节点为null，就将这个新的节点插入到这个位置if(datacurrent.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代码实现中序遍历中序遍历使用递归的方式，以升序访问树中所有节点，先访问左子树，在访问根节点，最后访问右子树。

functioninOrder(node){if(!(node==null)){inOrder(node.left);console.log(node.show());inOrder(node.right);}}//比如：varnums=newBST();nums.insert(56);nums.insert(22);nums.insert(81);nums.insert(10);nums.insert(30);nums.insert(77);nums.insert(92);inOrder(nums.root);//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代码放置的位置不同。主要是理解递归。

?先序遍历

functioninOrder(node){if(!(node==null)){console.log(node.show());inOrder(node.left);inOrder(node.right);}}inOrder(nums.root);

?后序遍历

functioninOrder(node){if(!(node==null)){inOrder(node.left);inOrder(node.right);console.log(node.show());}}inOrder(nums.root);

参考学习：《数据结构与算法JavaScript描述》《高级程序设计》