C语言用非递归算法中序遍历二叉树,输出其中序序列,写出完整代码
时间: 2023-06-11 16:08:14 浏览: 59
假设二叉树的结构体定义如下:
```c
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
```
非递归中序遍历二叉树的基本思路是使用栈来模拟递归过程,这里给出完整代码实现:
```c
void inorderTraversal(TreeNode* root) {
if (root == NULL)
return;
TreeNode* stack[1000];
int top = -1;
TreeNode* p = root;
while (p != NULL || top != -1) {
// 将当前节点的左子树全部压入栈中
while (p != NULL) {
stack[++top] = p;
p = p->left;
}
// 弹出栈顶元素并输出
p = stack[top--];
printf("%d ", p->val);
// 移动到右子树
p = p->right;
}
}
```
在主函数中调用该函数即可输出二叉树的中序序列。
相关问题
c语言代码输入字符序列,建立二叉树;按先序、中序、后序遍历二叉树(三种递归算法和中序遍历的非递归算法
以下是C语言代码实现输入字符序列,建立二叉树,以及按先序、中序、后序遍历二叉树(三种递归算法和中序遍历的非递归算法):
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct node{
char data;
struct node *lchild, *rchild;
}Node, *BiTree;
// 创建二叉树
void CreateBiTree(BiTree *T){
char ch;
scanf("%c", &ch);
if(ch == '#'){ // '#' 表示空节点
*T = NULL;
}
else{
*T = (BiTree)malloc(sizeof(Node));
(*T)->data = ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
// 先序遍历(递归)
void PreOrderTraverse(BiTree T){
if(T){
printf("%c ", T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
// 中序遍历(递归)
void InOrderTraverse(BiTree T){
if(T){
InOrderTraverse(T->lchild);
printf("%c ", T->data);
InOrderTraverse(T->rchild);
}
}
// 后序遍历(递归)
void PostOrderTraverse(BiTree T){
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c ", T->data);
}
}
// 中序遍历(非递归)
void InOrderTraverseNonRecursion(BiTree T){
BiTree stack[MAXSIZE];
int top = -1;
BiTree p = T;
while(p || top != -1){
if(p){
stack[++top] = p;
p = p->lchild;
}
else{
p = stack[top--];
printf("%c ", p->data);
p = p->rchild;
}
}
}
int main(){
BiTree T = NULL;
printf("请输入字符序列,#表示空节点:\n");
CreateBiTree(&T);
printf("先序遍历结果:");
PreOrderTraverse(T);
printf("\n");
printf("中序遍历结果:");
InOrderTraverse(T);
printf("\n");
printf("后序遍历结果:");
PostOrderTraverse(T);
printf("\n");
printf("中序遍历(非递归)结果:");
InOrderTraverseNonRecursion(T);
printf("\n");
return 0;
}
```
这里我们定义了一个结构体 `Node`,包含数据域 `data` 和指向左右子树的指针 `lchild` 和 `rchild`;另外定义了 `BiTree` 作为二叉树类型的别名。
`CreateBiTree` 函数用于输入字符序列,建立二叉树,其中 '#' 表示空节点。
`PreOrderTraverse`、`InOrderTraverse` 和 `PostOrderTraverse` 函数分别用于先序、中序和后序遍历二叉树,这里采用递归算法。
`InOrderTraverseNonRecursion` 函数用于中序遍历的非递归算法,利用栈实现。
在 `main` 函数中,先输入字符序列,建立二叉树,然后按不同方式遍历二叉树并输出结果。
请用C语言写出程序:输入字符序列,建立二叉树;按先序中序后序遍历二叉树(三种递归算法和中序遍历的非递归算法)
```c
#include <stdio.h>
#include <stdlib.h>
//定义二叉树结构体
struct TreeNode {
char data;
struct TreeNode* left;
struct TreeNode* right;
};
//根据输入的字符序列建立二叉树
struct TreeNode* createBinaryTree() {
char ch;
scanf("%c", &ch);
if (ch == '#') {
return NULL;
}
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->data = ch;
root->left = createBinaryTree();
root->right = createBinaryTree();
return root;
}
//先序遍历二叉树(递归算法)
void preOrderTraversalRecursive(struct TreeNode* root) {
if (root == NULL) {
return;
}
printf("%c ", root->data);
preOrderTraversalRecursive(root->left);
preOrderTraversalRecursive(root->right);
}
//中序遍历二叉树(递归算法)
void inOrderTraversalRecursive(struct TreeNode* root) {
if (root == NULL) {
return;
}
inOrderTraversalRecursive(root->left);
printf("%c ", root->data);
inOrderTraversalRecursive(root->right);
}
//后序遍历二叉树(递归算法)
void postOrderTraversalRecursive(struct TreeNode* root) {
if (root == NULL) {
return;
}
postOrderTraversalRecursive(root->left);
postOrderTraversalRecursive(root->right);
printf("%c ", root->data);
}
//中序遍历二叉树(非递归算法)
void inOrderTraversal(struct TreeNode* root) {
struct TreeNode* stack[100];
int top = -1;
struct TreeNode* p = root;
while (p != NULL || top != -1) {
if (p != NULL) {
stack[++top] = p;
p = p->left;
} else {
p = stack[top--];
printf("%c ", p->data);
p = p->right;
}
}
}
int main() {
printf("请输入字符序列,以#表示空节点:\n");
struct TreeNode* root = createBinaryTree();
printf("先序遍历结果:");
preOrderTraversalRecursive(root);
printf("\n中序遍历结果:");
inOrderTraversalRecursive(root);
printf("\n后序遍历结果:");
postOrderTraversalRecursive(root);
printf("\n中序遍历结果(非递归算法):");
inOrderTraversal(root);
return 0;
}
```