设计递归和非递归遍历二叉树的流程图
时间: 2023-06-29 22:15:19 浏览: 42
好的,下面是二叉树的递归遍历和非递归遍历的流程图:
1. 二叉树的递归遍历
- 先序遍历
```
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
// 访问当前节点
visit(root);
// 遍历左子树
preorderTraversal(root->left);
// 遍历右子树
preorderTraversal(root->right);
}
```
流程图如下:
```
┌────────────────────┐
│ 1. 判断当前节点是否为空 │
└────────────────────┘
│
│ 是
▼
┌────────────────────┐
│ 2. 访问当前节点 │
└────────────────────┘
│
│
▼
┌────────────────────┐
│ 3. 遍历左子树 │
└────────────────────┘
│
│
▼
┌────────────────────┐
│ 4. 遍历右子树 │
└────────────────────┘
```
- 中序遍历
```
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
// 遍历左子树
inorderTraversal(root->left);
// 访问当前节点
visit(root);
// 遍历右子树
inorderTraversal(root->right);
}
```
流程图如下:
```
┌────────────────────┐
│ 1. 判断当前节点是否为空 │
└────────────────────┘
│
│ 是
▼
┌────────────────────┐
│ 2. 遍历左子树 │
└────────────────────┘
│
│
▼
┌────────────────────┐
│ 3. 访问当前节点 │
└────────────────────┘
│
│
▼
┌────────────────────┐
│ 4. 遍历右子树 │
└────────────────────┘
```
- 后序遍历
```
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
// 遍历左子树
postorderTraversal(root->left);
// 遍历右子树
postorderTraversal(root->right);
// 访问当前节点
visit(root);
}
```
流程图如下:
```
┌────────────────────┐
│ 1. 判断当前节点是否为空 │
└────────────────────┘
│
│ 是
▼
┌────────────────────┐
│ 2. 遍历左子树 │
└────────────────────┘
│
│
▼
┌────────────────────┐
│ 3. 遍历右子树 │
└────────────────────┘
│
│
▼
┌────────────────────┐
│ 4. 访问当前节点 │
└────────────────────┘
```
2. 二叉树的非递归遍历
- 先序遍历
```
void preorderTraversalIterative(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
visit(node);
if (node->right) s.push(node->right);
if (node->left) s.push(node->left);
}
}
```
流程图如下:
```
┌────────────────────┐
│ 1. 判断当前节点是否为空 │
└────────────────────┘
│
│ 是
▼
┌────────────────────┐
│ 2. 访问当前节点 │
└────────────────────┘
│
│
▼
┌────────────────────┐
│ 3. 将右子树入栈 │
└────────────────────┘
│
│
▼
┌────────────────────┐
│ 4. 将左子树入栈 │
└────────────────────┘
```
- 中序遍历
```
void inorderTraversalIterative(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();
visit(node);
node = node->right;
}
}
```
流程图如下:
```
┌────────────────────┐
│ 1. 判断当前节点是否为空 │
└────────────────────┘
│
│ 否
▼
┌────────────────────┐
│ 2. 将当前节点入栈 │
└────────────────────┘
│
│
▼
┌────────────────────┐
│ 3. 遍历左子树 │
└────────────────────┘
│
│
▼
┌────────────────────┐
│ 4. 访问当前节点 │
└────────────────────┘
│
│
▼
┌────────────────────┐
│ 5. 遍历右子树 │
└────────────────────┘
```
- 后序遍历
```
void postorderTraversalIterative(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> s1, s2;
s1.push(root);
while (!s1.empty()) {
TreeNode* node = s1.top();
s1.pop();
s2.push(node);
if (node->left) s1.push(node->left);
if (node->right) s1.push(node->right);
}
while (!s2.empty()) {
TreeNode* node = s2.top();
s2.pop();
visit(node);
}
}
```
流程图如下:
```
┌────────────────────┐
│ 1. 判断当前节点是否为空 │
└────────────────────┘
│
│ 否
▼
┌────────────────────┐
│ 2. 将当前节点入栈 │
└────────────────────┘
│
│
▼
┌────────────────────┐
│ 3. 将当前节点入栈s2 │
└────────────────────┘
│
│
▼
┌────────────────────┐
│ 4. 将左子树入栈s1 │
└────────────────────┘
│
│
▼
┌────────────────────┐
│ 5. 将右子树入栈s1 │
└────────────────────┘
```
流程图如下:
```
┌────────────────────┐
│ 1. 判断当前节点是否为空 │
└────────────────────┘
│
│ 否
▼
┌────────────────────┐
│ 2. 访问当前节点 │
└────────────────────┘
│
│
▼
┌────────────────────┐
│ 3. 将当前节点出栈s2 │
└────────────────────┘
```