首页 > 试题广场 >

二叉树遍历

[编程题]二叉树遍历
  • 热度指数：56091 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述:
输入包括1行字符串，长度不超过100。


输出描述:
可能有多组测试数据，对于每组数据，
输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。
每个输出结果占一行。
示例1

输入

abc##de#g##f###

输出

c b e g d f a
算法知识视频讲解
开通博客
头像 basketball616
发表于 2019-10-09 19:05:05
分析：这是一道数据结构中树的基础题，主要考察二叉树的建立与遍历，可以用数组与指针两种方法实现。 方法一：数组模拟二叉树 说明：在测试数据较弱的情况下推荐使用这种方法 根据二叉树的性质可以得出：若父亲节点编号为X，则做左儿子节点编号为2X，右儿子节点编号为2X+1. #include<stdio 展开全文
去ta的博客 赞 (33) 回复(2) 收起
头像 KissKernel
发表于 2022-06-12 08:05:06
思路：分治思想，递归构建二叉树，构建二叉树先malloc出根节点然后再构建左子树，右子树即可。因为字符串需要构建之后指针向后移动找到下一个字符，所以需要一个count指针标记字符位置，构建之后指针向后移动，指针指向’#‘或者'\0'代表到了空节点了完成返回NULL即可 构建完成之后就中序遍历就好。 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 dzy秀啊
发表于 2022-03-09 15:07:11
1.树的样子 代码 有部分是看别人的 ">using namespace std; char s[100]; int pos; struct Tnode{ char val; Tnode* left; Tnode* right; Tnode(char c): va 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 罅隙xia
发表于 2021-08-14 00:42:38
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static class TreeNode{ char val; 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 崔崔崔崔狗蛋啊
发表于 2021-11-05 20:51:11
import java.util.*; public class Main {     //输入的是一串先序遍历的字符串，根据此字符串建立二叉树，然后在对二叉树输出中序遍历结果     //1.先定义一下二叉树类      pub 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 041444
发表于 2021-11-08 15:32:13
容易理解的递归创建方式 import java.util.Scanner; class TreeNode1{ public char val; public TreeNode1 left; public TreeNode1 right; public TreeN 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 我谢谢你哦
发表于 2022-12-28 17:52:59
#include <stdio.h> #include<stdlib.h> typedef struct tnode { char data; struct tnode* left; struct tnode* right; } tnode; tn 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 健康快乐最重要
发表于 2020-03-27 14:34:00
水题，直接构造就行。因为是一棵完全二叉树 #include<iostream> #include<string> using namespace std; struct Node{ Node *left; Node *right; char val; 展开全文
去ta的博客 赞 (2) 回复(2) 收起
头像 牛客588682307号
发表于 2024-03-11 19:03:28
#include<iostream> # include<stdio.h> # include<malloc.h> typedef struct btnode { char data; struct btnode* left, *right; } 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Coming680
发表于 2022-03-26 17:27:44
按照先序建立二叉树即可，然后再按照中序输出。 #include<iostream> using namespace std; typedef struct node{ char val; struct node *left,*right; }*TreeNode,Node; 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

搜索 树
难度：
195条回答 25876浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号