实现某二叉树的中序遍历算法,输出中序遍历序列
时间: 2023-12-23 09:25:59 浏览: 39
以下是实现二叉树中序遍历的非递归算法,使用了栈的数据结构:
```python
def inorderTraversal(root):
if not root:
return []
stack = []
res = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
res.append(root.val)
root = root.right
return res
```
其中,root代表当前节点,stack代表栈,res代表最终的中序遍历序列。具体实现过程为:首先将根节点入栈,然后将左子树的所有节点入栈,直到左子树为空。此时弹出栈顶元素,将其值加入到结果序列中,并将root指向右子树,重复上述过程,直到栈为空。
相关问题
用C语言编程实现二叉树中序遍历和后续遍历的递归算法和非递归算法。
下面是C语言实现二叉树中序遍历和后序遍历的递归算法和非递归算法的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXSIZE 100
// 二叉树结构体
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode, *PtrToNode;
// 栈结构体
typedef struct Stack {
PtrToNode data[MAXSIZE];
int top;
} Stack, *PtrToStack;
// 初始化栈
void InitStack(PtrToStack S) {
S->top = -1;
}
// 判断栈是否为空
bool IsEmpty(PtrToStack S) {
return S->top == -1;
}
// 判断栈是否已满
bool IsFull(PtrToStack S) {
return S->top == MAXSIZE - 1;
}
// 入栈
void Push(PtrToStack S, PtrToNode X) {
if (IsFull(S)) {
printf("栈已满\n");
return;
}
S->data[++S->top] = X;
}
// 出栈
PtrToNode Pop(PtrToStack S) {
if (IsEmpty(S)) {
printf("栈已空\n");
return NULL;
}
return S->data[S->top--];
}
// 中序遍历递归算法
void InOrderTraversal(PtrToNode root) {
if (root) {
InOrderTraversal(root->left);
printf("%d ", root->data);
InOrderTraversal(root->right);
}
}
// 中序遍历非递归算法
void InOrderTraversal2(PtrToNode root) {
Stack S;
InitStack(&S);
PtrToNode p = root;
while (p || !IsEmpty(&S)) {
if (p) {
Push(&S, p);
p = p->left;
} else {
p = Pop(&S);
printf("%d ", p->data);
p = p->right;
}
}
}
// 后序遍历递归算法
void PostOrderTraversal(PtrToNode root) {
if (root) {
PostOrderTraversal(root->left);
PostOrderTraversal(root->right);
printf("%d ", root->data);
}
}
// 后序遍历非递归算法
void PostOrderTraversal2(PtrToNode root) {
Stack S;
InitStack(&S);
PtrToNode p = root;
PtrToNode r = NULL;
while (p || !IsEmpty(&S)) {
if (p) {
Push(&S, p);
p = p->left;
} else {
p = S.data[S.top];
if (p->right && p->right != r) {
p = p->right;
Push(&S, p);
p = p->left;
} else {
p = Pop(&S);
printf("%d ", p->data);
r = p;
p = NULL;
}
}
}
}
// 创建二叉树
void CreateTree(PtrToNode *root) {
int data;
scanf("%d", &data);
if (data == -1) {
*root = NULL;
} else {
*root = (PtrToNode)malloc(sizeof(TreeNode));
(*root)->data = data;
CreateTree(&((*root)->left));
CreateTree(&((*root)->right));
}
}
int main() {
PtrToNode root;
printf("请输入二叉树的前序遍历序列,-1表示空节点:\n");
CreateTree(&root);
printf("中序遍历递归算法:");
InOrderTraversal(root);
printf("\n中序遍历非递归算法:");
InOrderTraversal2(root);
printf("\n后序遍历递归算法:");
PostOrderTraversal(root);
printf("\n后序遍历非递归算法:");
PostOrderTraversal2(root);
printf("\n");
return 0;
}
```
其中,CreateTree函数用于创建二叉树,InOrderTraversal和PostOrderTraversal函数分别是中序遍历和后序遍历的递归算法,InOrderTraversal2和PostOrderTraversal2函数分别是中序遍历和后序遍历的非递归算法。在非递归算法中,我们使用了栈来模拟递归的过程。
编写一算法,输出二叉树的中序遍历序列。
中序遍历是指先遍历左子树,然后访问根节点,最后遍历右子树。因此,我们可以使用递归的方式实现中序遍历。
具体实现如下:
```
void inorderTraversal(TreeNode* root, vector<int>& res) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left, res);
res.push_back(root->val);
inorderTraversal(root->right, res);
}
```
其中,`TreeNode` 是二叉树节点的结构体,包含 `val`、`left` 和 `right` 三个成员变量,分别表示节点的值、左子节点和右子节点。
我们可以定义一个 `vector<int>` 类型的变量 `res`,用来存储中序遍历的结果。然后调用 `inorderTraversal` 函数,将根节点和 `res` 作为参数传递进去,函数会递归遍历左子树、访问根节点和递归遍历右子树,并将访问的节点值存储到 `res` 中。
以下是完整代码实现:
```
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void inorderTraversal(TreeNode* root, vector<int>& res) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left, res);
res.push_back(root->val);
inorderTraversal(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorderTraversal(root, res);
return res;
}
```
调用 `inorderTraversal` 函数,并输出结果:
```
int main() {
TreeNode* root = new TreeNode(1);
root->right = new TreeNode(2);
root->right->left = new TreeNode(3);
vector<int> res = inorderTraversal(root);
for (int i = 0; i < res.size(); i++) {
cout << res[i] << " ";
}
cout << endl;
return 0;
}
```
输出:
```
1 3 2
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)