# 二叉樹的迭代有序遍歷

## 例

```                 2

/     \

1         3

/   \

4       5

```
`4 1 5 2 3`
```           1

/    \

2        3

/            \

4               6

\

7

```
`4 2 1 3 6 7`

## 算法

1. 初始化變量 “ curNode” 作為二叉樹的根
2. 初始化一個空棧， 包含節點 當他們被遍歷
3. 執行以下操作，直到堆棧不為空或 節點 尚未成為 空值：
• 節點 is 空值：
1. 節點 進入堆棧
2. 通過將當前節點更改為 curNode = curNode->左
• 現在，堆棧中的頂部節點是當前子樹的最左側節點，因此我們打印堆棧中頂部節點的值
• 分配 節點 作為堆棧中頂部節點的右子元素，如 curNode = stack.top（）->右
• 通過將當前節點更改為 curNode = curNode->左 處理這個最左邊節點的右邊子樹
• 從堆棧中彈出一個元素

## 履行

### 二叉樹的迭代有序遍歷的C ++程序

```#include <bits/stdc++.h>

using namespace std;

struct treeNode
{
int value;
treeNode *left , *right;
treeNode(int x)
{
value = x;
left = NULL;
right = NULL;
}
};

void iterativeInorder(treeNode* root)
{
stack <treeNode*> ;
treeNode* curNode = root;elements

while(curNode != NULL || !elements.empty())
{
while(curNode != NULL)
{
elements.push(curNode);
curNode = curNode->left;
}

cout << elements.top()->value << " ";
curNode = elements.top()->right;
elements.pop();
}
}

int main()
{
treeNode* root = new treeNode(2);
root->left = new treeNode(1);
root->right = new treeNode(3);
root->left->left = new treeNode(4);
root->left->right = new treeNode(5);

iterativeInorder(root);
cout << endl;
return 0;
}
```
```4 1 5 2 3
```

### 二叉樹迭代有序遍歷的Java程序

```import java.util.Stack;

class treeNode
{
int value;
treeNode left, right;

public treeNode(int x)
{
value= x;
left = right = null;
}
}

class Tree
{
treeNode root;
void iterativeInorder()
{

Stack<treeNode> elements = new Stack<treeNode>();
treeNode curNode = root;

while (curNode != null || !elements.empty())
{
while (curNode != null)
{
elements.push(curNode);
curNode = curNode.left;
}

curNode = elements.peek().right;
System.out.print(elements.peek().value + " ");
elements.pop();
}
}

public static void main(String args[])
{
Tree tree = new Tree();
tree.root = new treeNode(2);
tree.root.left = new treeNode(1);
tree.root.left.left = new treeNode(4);
tree.root.left.right = new treeNode(5);
tree.root.right = new treeNode(3);
tree.iterativeInorder();
}
}```
`4 1 5 2 3`