2.编写C语言程序实现在二叉树的中序遍历和后序遍历 递归和非递归算法并运行
时间: 2024-05-04 15:15:59 浏览: 10
非常抱歉,作为一名 AI 语言模型,并没有能力直接进行编程和运行程序。但是,我可以为您提供一些基础知识与思路,希望可以帮助您解决问题。
在二叉树中,中序遍历、前序遍历和后序遍历是最基本且重要的三种遍历方式,其中后序遍历指的是先访问左孩子结点,再访问右孩子结点,最后访问根结点。下面分别介绍二叉树中序遍历和后序遍历的递归和非递归算法实现。
二叉树中序遍历递归算法:
```c
void inorderTraversal(TreeNode* root) {
if (root != NULL) {
inorderTraversal(root->left); // 访问左子树
printf("%d ", root->val); // 访问根节点
inorderTraversal(root->right); // 访问右子树
}
}
```
二叉树中序遍历非递归算法:使用栈来实现中序遍历
```c
void inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* p = root;
while (p != NULL || !st.empty()) {
if (p != NULL) {
st.push(p);
p = p->left;
} else {
p = st.top();
st.pop();
printf("%d ", p->val);
p = p->right;
}
}
}
```
二叉树后序遍历递归算法:
```c
void postorderTraversal(TreeNode* root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
}
```
二叉树后序遍历非递归算法:使用一个栈和两个指针来实现后序遍历
```c
void postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* p = root;
TreeNode* last = NULL; // 上次访问的结点
while (p != NULL || !st.empty()) {
if (p != NULL) {
st.push(p);
p = p->left;
} else {
TreeNode* top = st.top();
if (top->right != NULL && top->right != last) { // 如果右子树存在,且未被访问
p = top->right;
} else { // 否则,访问该节点
st.pop();
printf("%d ", top->val);
last = top;
}
}
}
}
```
希望以上的内容可以对您编写程序有所帮助,如果还有其他问题请随时提出。