位置: 编程技术 - 正文
JS中的二叉树遍历详解(js实现二叉查找树)
编辑：rootadmin推荐整理分享JS中的二叉树遍历详解(js实现二叉查找树)，希望有所帮助，仅作参考，欢迎阅读内容。
文章相关热门搜索词:js二叉树遍历,js二叉树层次遍历,二叉树遍历java,js实现二叉树数据结构,js二叉树遍历,js二叉树遍历方法,js二叉树遍历方法,js二叉树遍历方法,内容如对您有帮助，希望把文章链接给更多的朋友！
二叉树是由根节点，左子树，右子树组成，左子树和友子树分别是一个二叉树。这篇文章主要在JS中实现二叉树的遍历。
一个二叉树的例子
广度优先遍历广度优先遍历是从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。实现：<!--more-->使用数组模拟队列。首先将根节点归入队列。当队列不为空的时候，执行循环：取出队列的一个节点，如果该结点的左子树为非空，则将该结点的左子树入队列；如果该结点的右子树为非空，则将该结点的右子树入队列。（描述有点不清楚，直接看代码吧。）
递归遍历觉得用这几个字母表示递归遍历的三种方法不错：D：访问根结点，L：遍历根结点的左子树，R：遍历根结点的右子树。先序遍历：DLR中序遍历：LDR后序遍历：LRD顺着字母表示的意思念下来就是遍历的顺序了 ^ ^
这3种遍历都属于递归遍历，或者说深度优先遍历（Depth-First Search，DFS），因为它总是优先往深处访问。
先序遍历的递归算法：
中序遍历的递归算法：
后序遍历的递归算法：
非递归深度优先遍历其实对于这些概念谁是属于谁的我也搞不太清楚。有的书里将二叉树的遍历只讲了上面三种递归遍历。有的分广度优先遍历和深度优先遍历两种，把递归遍历都分入深度遍历当中;有的分递归遍历和非递归遍历两种，非递归遍历里包括广度优先遍历和下面这种遍历。个人觉得怎么分其实并不重要，掌握方法和用途就好 ：）
刚刚在广度优先遍历中使用的是队列，相应的，在这种不递归的深度优先遍历中我们使用栈。在JS中还是使用一个数组来模拟它。这里只说先序的：额，我尝试了描述这个算法，然而并描述不清楚，按照代码走一边你就懂了。
看了这一篇，找到了非递归后序的算法，所以在这里把非递归的遍历方法补充完整。非递归中序先把数的左节点推入栈，然后取出，再推右节点。
非递归后序(使用一个栈)这里使用了一个临时变量记录上次入栈/出栈的节点。思路是先把根节点和左树推入栈，然后取出左树，再推入右树，取出，最后取跟节点。
非递归后序(使用两个栈)这个算法的思路和上面那个差不多，s1有点像一个临时变量。
Morris遍历这个方法即不用递归也不用栈实现三种深度遍历，空间复杂度为O(1)（这个概念我也不是特别清楚org）（这三种算法我先放着，有空再研究）Morris先序:
Morris中序:
Morris后序:
标签: js实现二叉查找树
本文链接地址:https://www.jiuchutong.com/biancheng/377434.html 转载请保留说明！上一篇：简述JavaScript提交表单的方式 （Using JavaScript Submit Form）(简述javascript的作用)
