前言：

继上一章二叉树的javascript实现之后，我们来谈谈二叉树的遍历。

这种严重的废话，就拿下面的二叉树作为例子来遍历吧：

然后是介绍二叉树实现的代码：

函数Node(数据，左，右){ this.data=datathis.left=leftthis.right=右；this.show=show}函数show() {返回this.data}函数BST(){ this . root=null；this.insert=insert}函数插入(数据){ var n=new Node(数据，null，null)；if(this . root==null){ this . root=n；} else { var current=this.rootvar父级；while(true){ parent=current；if(data current . data){ current=current . left；if(current==null){ parent . left=n；打破；} } else { current=current.rightif(current==null){ parent . right=n；打破；二叉树遍历的分类

二叉树的遍历分为一阶、中阶和末阶遍历。这里提到的优先级、中间优先级和后优先级都是相对于父节点的。父节点的第一个输出是第一个序列，中间输出是中间序列，最后一个输出是最后一个序列。至于哪个节点是父节点，那是相对的，因为除了叶节点(最低节点)之外的每个节点都可以是父节点。

前序遍历

顺序遍历是指先打印父节点，再打印左子节点(左子树)，然后打印右子节点(子树)。

函数preOrder(节点){ if(！(node==null)){ console . log(node . show()' ')；preOrder(node . left)；preOrder(node . right)；} }//将成员方法函数BST() {this.root=null添加到BST类中；this.insert=insertthis.preOrder=preOrder}preOrder函数是递归实现的，所以应该说二叉树的遍历是递归实现的。有些人可能会因为顺序遍历的特点而陷入错误的思路：“先打印父节点，再打印左子节点(左子树)，再打印右子节点(子树)”。这是什么想法？请看下图：

注意红框，父节点为10，左子节点为3，右子节点为18。因为以上结论，你可能会误以为打印顺序是10 3 18，但事实并非如此【捂脸】。真正的顺序是：先打印10，再打印左边的子树。打印完左侧子树的所有节点后，开始打印包含10个父节点的右侧子树：

这时，你的头脑应该这样想：

然后这样想：

以此类推，打印以10为父节点的左子树，然后以同样的方式打印以10为父节点的右子树。二叉树的遍历反而按照拆分的思路会更好理解。

那么，最终，通过一阶遍历改变二叉树的顺序是：

根据图表的输出顺序是：10-3-2-4-9-8-9-18-13-21

最后，让我们练习一下，一阶遍历：

var BST=new BST()；var nums=[10，3，18，2，4，13，21，9，8，9]；for(var I=0；i nums.lengthI){ BST . insert(nums[I])；} BST . preorder(BST . root)；

这里强调的是，输出顺序与插入顺序有关，因为不同插入顺序生成的二叉树也是不同的。如果你有任何问题，你可以仔细看看二叉树的javascript实现。二叉树有明确的解释，你也可以实验：

有序遍历

读完一阶遍历，很多与中阶和末阶遍历相关的知识点都可以类比出来。中序遍历的特点是：先打印左子树(左子节点)，再打印父节点，最后打印右子树(右子节点)。

函数inOrder(节点){ if(！(node==null)){ Inorder(node . left)；console . log(node . show()' ')；inoder(node . right)；} }//将成员方法函数BST() {this.root=null添加到BST类中；this.insert=insertthis.preOrder=preOrderthis.inOrder=inOrder}中间顺序遍历的打印顺序：

根据上图的输出顺序为：2-3-4-8-9-9-10-13-18-21

然后，练习中间顺序遍历：

后序遍历

函数postOrder(节点){ if(！(node==null)){ PostOrder(node . left)；posterorder(node . right)；console . log(node . show()' ')；} }//将成员方法函数BST() {this.root=null添加到BST类中；this.insert=insertthis.preOrder=preOrderthis.inOrder=inOrderthis.postOrder=postOrder}后续遍历的打印顺序

根据上图的输出顺序为：2-8-9-9-4-3-13-21-18-10

以上就是本文的全部内容。希望对大家的学习有帮助，支持我们。