JS中的二叉树遍历详解

二叉树是一种重要的数据结构，它由根节点、左子树和右子树组成，其中左子树和右子树也是二叉树。本文将详细介绍二叉树的遍历方式，包括广度优先遍历和优先遍历。

以一个简单的二叉树为例：

```javascript

var tree = {

value: 1,

left: {

value: 2,

left: { value: 4 }

},

right: {

value: 3,

left: {

value: 5,

left: { value: 7 },

right: { value: 8 }

},

right: { value: 6 }

}

};

```

一、广度优先遍历（Breadth-First Search）

广度优先遍历从二叉树的第一层（根节点）开始，逐层遍历，在同一层中，按照从左到右的顺序对节点逐一访问。实现方式可以使用队列。将根节点加入队列，当队列不为空时，取出队列中的一个节点，将其子节点加入队列。具体实现如下：

二、优先遍历（Depth-First Search）

一、非递归后序遍历（使用一个栈）

这种方法使用一个临时变量来记录上次入栈或出栈的节点，以避免重复访问节点。我们先将根节点和左子树推入栈中，然后取出左子树，再推入右子树，接着取出右子树，最后取出根节点并打印其值。这样我们可以确保每次处理的都是未被访问过的节点。如果节点为空，则抛出错误提示空树。代码如下：

```javascript

var postOrderUnRecur = function(node) {

if (!node) throw new Error('Empty Tree');

var stack = [];

stack.push(node);

var tmp = null;

while (stack.length !== 0) {

tmp = stack[stack.length - 1]; // 获取当前栈顶元素

if (tmp.left && node !== tmp.left && node !== tmp.right) { // 先将左子树推入栈中

stack.push(tmp.left);

} else if (tmp.right && node !== tmp.right) { // 再将右子树推入栈中

stack.push(tmp.right);

} else { // 处理当前节点，并弹出栈顶元素

console.log(stack.pop().value); // 输出当前节点的值并弹出栈顶元素

node = tmp; // 更新当前节点为上一个处理的节点

}

}

};

```

二、非递归中序遍历（使用栈）和上文描述一致。我们先将左节点推入栈，再取出节点打印其值，并依次推入右节点。这样依次循环直到遍历完整棵树。如果节点为空，则抛出错误提示空树。代码如下：

三、非递归后序遍历（使用两个栈）的思路与上一个方法类似，其中一个栈用于存储待处理的节点，另一个用于存储已经处理过的节点。这样我们可以保证每次处理的节点都是未被访问过的。具体的实现细节较为复杂，需要细心处理各种边界情况。在此不进行详细展开代码实现。如果感兴趣的话，可以查阅相关算法书籍或教程进行深入了解。这些方法都保持了原文风格特点，同时增强了内容的生动性和丰富性。希望对你有所帮助！【Morris遍历方法】

在计算机科学中，Morris遍历是一种非常有效的优先遍历方法，其独特之处在于它能在无需使用递归和栈的情况下，实现对二叉树的优先遍历。这种方法的最大亮点在于其空间复杂度为O(1)，极大地节省了内存资源。

一、Morris先序遍历

Morris先序遍历是一种特殊的优先遍历方式。其核心思想是在遍历过程中，通过临时改变节点的连接关系，创建一种类似于“线索二叉树”的结构，从而达到在不使用栈的情况下进行优先遍历的目的。具体实现如下：

```javascript

var morrisPre = function(head) {

if(!head) return; // 如果节点为空，直接返回

var cur1 = head; // 当前节点初始化为头节点

while(cur1) { // 当当前节点存在时

var cur2 = cur1.left; // 左子树节点

if(cur2) { // 如果左子树存在

while(cur2.right && cur2.right !== cur1) { // 寻找左子树的最右节点

cur2 = cur2.right;

}

// 如果最右节点没有指向父节点，则建立连接关系，并输出当前节点的值，然后遍历左子树

if(!cur2.right) {

cur2.right = cur1;

console.log(cur1.value);

cur1 = cur1.left;

continue;

} else { // 如果已经存在指向父节点的连接，断开这个连接

cur2.right = null;

}

} else { // 如果左子树不存在或已经遍历完，输出当前节点的值，然后遍历右子树

console.log(cur1.value);

}

cur1 = cur1.right; // 切换到下一个兄弟节点进行遍历

}

}

```

二、Morris中序遍历与Morris后序遍历

Morris中序遍历和Morris后序遍历的实现思路与Morris先序遍历类似，只是在输出节点值的时机上有所区别。它们的共同点是，在遍历过程中，都会通过改变节点的连接关系，创建类似于“线索二叉树”的结构，从而达到在不使用栈的情况下进行优先遍历的目的。具体的实现细节可以根据实际需求进行调整。由于篇幅限制，这里不再赘述。希望以上内容能对大家的学习有所帮助。如有更多疑问或需要深入的地方，欢迎随时交流。感谢阅读！