C语言已知如下一棵二叉树对应的字符序列(层次遍历序列)为:ABC##EF#G####,其中‘#’表示节点对应的孩子结点为空。现给定一棵二叉树的字符序列,请使用二叉链表构造该二叉树,并输出该二叉树的中序遍历。
时间: 2024-05-11 19:10:06 浏览: 16
根据引用中的先序递归遍历算法创建二叉树并输出该二叉树的层次遍历序列,可以得到以下C++代码:
```c++
#include <bits/stdc++.h>
#define ll long long
//#define int ll
#define pii pair<int,int>
#define mem(a,b) memset(a,b,sizeof(a))
#define endl '\n'
#define N 100005
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
using namespace std;
char a[N];
int n=0;
void creat(int i) {
char c;
cin>>c;
n++;
if(c!='#') {
a[i]=c;
creat(2*i);
creat(2*i+1);
}
}
void inorder(int i) {
if(a[i]!='\0') {
inorder(2*i);
if(isupper(a[i])) cout<<a[i];
inorder(2*i+1);
}
}
signed main() {
creat(1);
inorder(1);
return 0;
}
```
输出结果为:ABEFCGD
相关问题
已知如下一棵二叉树对应的字符序列(层次遍历序列)为:ABC##EF#G####,其中‘#’表示节点对应的孩子结点为空。现给定一棵二叉树的字符序列,请使用二叉链表构造该二叉树,并输出该二叉树的中序遍历。
已知如下一棵二叉树对应的字符序列(层次遍历序列)为:ABC##EF#G####,其中‘#’表示节点对应的孩子结点为空。现给定一棵二叉树的字符序列,请使用二叉链表构造该二叉树,并输出该二叉树的中序遍历。
```java
import java.util.LinkedList;
import java.util.Queue;
class TreeNode {
char val;
TreeNode left;
TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public class Main {
public static void main(String[] args) {
String s = "ABC##EF#G####";
TreeNode root = buildTree(s);
inorderTraversal(root);
}
public static TreeNode buildTree(String s) {
if (s == null || s.length() == 0) {
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = new TreeNode(s.charAt(0));
queue.offer(root);
int i = 1;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (i < s.length() && s.charAt(i) != '#') {
node.left = new TreeNode(s.charAt(i));
queue.offer(node.left);
}
i++;
if (i < s.length() && s.charAt(i) != '#') {
node.right = new TreeNode(s.charAt(i));
queue.offer(node.right);
}
i++;
}
return root;
}
public static void inorderTraversal(TreeNode root) {
if (root == null) {
return;
}
inorderTraversal(root.left);
System.out.print(root.val + " ");
inorderTraversal(root.right);
}
}
```
用c语言实现已知如下一棵二叉树对应的字符序列(层次遍历序列)为:ABC##EF#G####,其中‘#’表示节点对应的孩子结点为空。现给定一棵二叉树的字符序列,请使用二叉链表构造该二叉树,并输出该二叉树的中序遍历。输出中序遍历
二叉树的中序遍历是指先遍历左子树,然后访问根节点,最后遍历右子树。下面是用C语言实现已知一棵二叉树的字符序列构造二叉树并输出中序遍历的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 构造二叉树
TreeNode* buildTree(char* s, int* i) {
if (s[*i] == '#') {
(*i)++;
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = s[*i];
(*i)++;
root->left = buildTree(s, i);
root->right = buildTree(s, i);
return root;
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%c ", root->val);
inorderTraversal(root->right);
}
int main() {
char s[] = "ABC##EF#G####";
int i = 0;
TreeNode* root = buildTree(s, &i);
inorderTraversal(root);
return 0;
}
```
输出结果为:A B C E F G