二叉树非递归的遍历c++
时间: 2023-01-11 16:55:36 浏览: 105
二叉树的非递归遍历有两种常用的方法: 先序遍历和中序遍历。
先序遍历的非递归算法步骤如下:
1. 创建一个栈, 用于存储节点。
2. 将根节点入栈。
3. 只要栈不为空, 就执行以下操作:
a. 取出栈顶节点。
b. 访问栈顶节点。
c. 如果栈顶节点有右子节点, 则将右子节点入栈。
d. 如果栈顶节点有左子节点, 则将左子节点入栈。
中序遍历的非递归算法步骤如下:
1. 创建一个栈, 用于存储节点。
2. 将根节点入栈。
3. 只要栈不为空, 就执行以下操作:
a. 取出栈顶节点。
b. 如果栈顶节点有右子节点, 则将右子节点入栈。
c. 访问栈顶节点。
d. 如果栈顶节点有左子节点, 则将左子节点入栈。
相关问题
二叉树的非递归遍历c++
以下是二叉树的非递归遍历C语言代码:
1. 非递归先序遍历
```
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
printf("%d ", node->val);
if (node->right) {
s.push(node->right);
}
if (node->left) {
s.push(node->left);
}
}
}
```
2. 非递归中序遍历
```
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> s;
TreeNode* node = root;
while (!s.empty() || node != NULL) {
if (node != NULL) {
s.push(node);
node = node->left;
} else {
node = s.top();
s.pop();
printf("%d ", node->val);
node = node->right;
}
}
}
```
3. 非递归后序遍历
```
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> s;
s.push(root);
TreeNode* pre = NULL;
while (!s.empty()) {
TreeNode* node = s.top();
if ((node->left == NULL && node->right == NULL) || (pre != NULL && (pre == node->left || pre == node->right))) {
printf("%d ", node->val);
s.pop();
pre = node;
} else {
if (node->right != NULL) {
s.push(node->right);
}
if (node->left != NULL) {
s.push(node->left);
}
}
}
}
```
非递归遍历二叉树c++
非递归遍历二叉树是指在不使用递归函数的情况下,对二叉树进行遍历的方法。以下是三种非递归遍历二叉树的方法:
1. 非递归中序遍历二叉树
中序遍历二叉树的顺序是:左子树 -> 根节点 -> 右子树。使用栈来保存未被访问的节点,具体步骤如下:
1)从根节点开始,将当前节点入栈。
2)如果当前节点有左子树,则将左子树入栈并进入左子树,重复步骤2,直到左子树为空。
3)从栈中弹出节点,访问该节点。
4)如果该节点有右子树,则将右子树入栈并进入右子树,重复步骤2、3、4。
2. 非递归先序遍历二叉树
先序遍历二叉树的顺序是:根节点 -> 左子树 -> 右子树。使用栈来保存未被访问的节点,具体步骤如下:
1)从根节点开始,将当前节点入栈。
2)从栈中弹出节点,访问该节点。
3)如果该节点有右子树,则将右子树入栈。
4)如果该节点有左子树,则将左子树入栈。
5)重复步骤2、3、4,直到栈为空。
3. 非递归后序遍历二叉树
后序遍历二叉树的顺序是:左子树 -> 右子树 -> 根节点。使用两个栈来实现,具体步骤如下:
1)将根节点入栈1。
2)从栈1中弹出节点,并将该节点入栈2。
3)如果该节点有左子树,则将左子树入栈1。
4)如果该节点有右子树,则将右子树入栈1。
5)重复步骤2、3、4,直到栈1为空。
6)从栈2中依次弹出节点并访问。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)