代码:输入字符序列,建立二叉树;按先序、中序、后序遍历二叉树(三种递归算法和中序遍历的非递归算法);
时间: 2024-05-26 14:10:44 浏览: 19
好的,这是一个关于数据结构与算法的问题,我可以为您提供一些帮助。 首先,根据输入的字符序列,您需要将其转换为二叉树的一个节点. 您可以选择使用递归或者迭代的方式来完成这个过程。 其次,您需要按照先序、中序和后序遍历二叉树。这可以用递归来实现,也可以使用非递归的方式来实现。对于中序遍历的非递归算法,您可以使用栈来辅助实现。如果您需要更详细的解释或者代码示例,我可以为您提供。
相关问题
请用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;
}
```
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` 函数中,先输入字符序列,建立二叉树,然后按不同方式遍历二叉树并输出结果。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)