二叉树的中序非递归遍历

二叉树中序遍历是指按照左根右的顺序遍历一棵二叉树。在递归遍历中，我们可以先递归遍历左子树，再输出根节点，最后递归遍历右子树。但是，在非递归的情况下，我们需要使用一些辅助数据结构来实现这个功能。本文将从四个方面分析二叉树的中序非递归遍历的实现方式。

一、使用栈

使用栈是一种常见的实现方式。我们首先将根节点压入栈中，然后访问左子树，将左子树的节点按顺序压入栈中。当左子树遍历完成后，将栈顶节点输出，同时将右子树进栈。对于右子树，我们重复上述步骤，直到栈为空。以下是伪代码实现：

```

stack s;

TreeNode* p = root;

while(p || !s.empty()) {

while(p) {

s.push(p);

p = p->left;

}

if(!s.empty()) {

TreeNode* node = s.top();

cout << node->val << endl;

s.pop();

p = node->right;

}

}

```

二、Morris遍历

Morris遍历是一种不使用栈的实现方式。该算法使用线索二叉树的概念，即将空闲的右孩子指向中序遍历的后继节点。然后遍历当前节点的左子树，并不断将当前节点的右孩子指向下一个要访问的节点，避免使用栈或递归。以下是伪代码实现：

```

TreeNode* cur = root;

while(cur) {

if(cur->left == NULL) {

cout << cur->val << endl;

cur = cur->right;

} else {

TreeNode* pre = cur->left;

while(pre->right && pre->right != cur) {

pre = pre->right;

}

if(pre->right == NULL) {

pre->right = cur;

cur = cur->left;

} else {

pre->right = NULL;

cout << cur->val << endl;

cur = cur->right;

}

}

}

```

Morris遍历在空间复杂度上得到了优化，但是在时间复杂度上可能略逊于使用栈的方法。因为需要寻找到左子树的最右侧节点。

三、颜色标记法

颜色标记法可以算作是同时使用栈和标记的一种方法。我们通过外部标记节点的颜色来区分它是第一次被访问还是第二次被访问。第一次被访问时，我们将其右子树和左子树依次进栈。第二次被访问时，直接输出节点。以下是伪代码实现：

```

stack > s;

s.push(make_pair(root, 0));

while(!s.empty()) {

TreeNode* node = s.top().first;

int color = s.top().second;

s.pop();

if(node == NULL) {

continue;

}

if(color == 0) {

s.push(make_pair(node->right, 0));

s.push(make_pair(node, 1));

s.push(make_pair(node->left, 0));

} else {

cout << node->val << endl;

}

}

```

四、线索化二叉树

线索化二叉树是一种特殊的二叉树，其中每个节点都存储了其前驱和后继节点的指针，使得中序遍历可以在常数附近的时间内完成。该算法的主要思路是通过中序遍历重新处理二叉树，使得节点的空闲孩子指针指向遍历的前/后继节点。这样，我们就可以不用栈或标记来实现中序遍历了。以下是伪代码实现：

```

void inOrderTraversal(TreeNode* node) {

TreeNode* predecessor = NULL;

while(node) {

if(node->left) {

predecessor = node->left;

while(predecessor->right && predecessor->right != node) {

predecessor = predecessor->right;

}

if(predecessor->right == NULL) {

predecessor->right = node;

node = node->left;

} else {

predecessor->right = NULL;

cout << node->val << endl;

node = node->right;

}

} else {

cout << node->val << endl;

node = node->right;

}

}

}

```

本文介绍了四种二叉树中序非递归遍历的实现方式，包括基于栈的方法、Morris遍历、颜色标记法、线索化二叉树。每种方法都有其优缺点，读者可以选择适合自己场景的方法来实现中序非递归遍历。