中序遍历二叉树T的非递归算法的代码
时间: 2024-02-17 20:02:14 浏览: 36
下面是中序遍历二叉树T的非递归算法的代码实现,其中假设二叉树节点类型为TreeNode,具有val、left、right三个属性:
```
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
return res;
}
```
该算法使用了一个栈来辅助遍历,首先将根节点入栈,然后在每次迭代中取出栈顶节点并访问,如果该节点有右子节点,则将右子节点入栈,然后再将左子节点入栈。这样可以保证在访问某个节点时,其左子树已经全部访问完毕。当栈为空时,整个二叉树的中序遍历就完成了。
相关问题
中序遍历二叉树T的非递归算法代码
中序遍历二叉树的非递归算法代码如下:
```
void inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* node = root;
while (node || !s.empty()) {
while (node) {
s.push(node);
node = node->left;
}
node = s.top();
s.pop();
cout << node->val << " ";
node = node->right;
}
}
```
其中,stack是用来存储待访问的节点的,node是当前访问的节点。算法的思路是,先把当前节点的所有左子树节点入栈,然后访问栈顶节点并出栈,最后访问栈顶节点的右子树。重复这个过程直到栈为空。
中序遍历二叉树t的非递归算法
中序遍历二叉树T的非递归算法可以使用栈来实现。具体步骤如下:
1. 初始化栈S为空,当前节点为根节点T。
2. 当T不为空或栈S不为空时,执行以下步骤:
a. 当T不为空时,将T入栈,T指向T的左子树。
b. 当T为空时,从栈S中弹出节点并访问,T指向弹出节点的右子树。
3. 重复步骤2,直到T为空且栈S为空。
通过这种方式,可以实现中序遍历二叉树的非递归算法。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)