[编程题]二叉树遍历
- 热度指数：66866 时间限制：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
import java.util.Scanner;
class TreeNode{
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val){
this.val = val;
}
}
public class Main {
public static int i = 0;
public static TreeNode CreatBinaryTree(String str){
TreeNode root = null;
if(str.charAt(i)!='#'){
root = new TreeNode(str.charAt(i));
i++;
root.left = CreatBinaryTree(str);
root.right = CreatBinaryTree(str);
}else{
i++;
}
return root;
}
public static void Display(TreeNode root){
if(root == null){
return;
}
Display(root.left);
System.out.print(root.val+" ");
Display(root.right);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) {
TreeNode root = CreatBinaryTree( in.nextLine());
Display(root);
}
}
}
发表于 2025-01-03 20:27:32
回复(0)
不去模拟二叉树
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine();
char[] ch = s.toCharArray();
for (int i = 0; i < ch.length; i++) {
if (ch[i] == '#') {
ch[i] = '1';
while (i >= 0 && ch[i] == '1') {
i--;
}
if (i >= 0) {
System.out.printf("%c ",ch[i]);
ch[i] = '1';
}else {
i = 0;
}
}
}
}
}
编辑于 2024-01-29 15:55:28
回复(0)
import java.util.Scanner;
class TreeNode {
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) {
Main a=new Main();
String str=in.nextLine();
TreeNode root=a.createTree(str);
a.inOrder(root);
}
}
public int i=0;
public TreeNode createTree(String s){
TreeNode root=null;
if(s.charAt(i)!='#'){
root=new TreeNode(s.charAt(i));
i++;
root.left=createTree(s);
root.right=createTree(s);
}else{
i++;
}
return root;
}
public void inOrder(TreeNode root){
if(root==null){
return;
}
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
}
发表于 2022-09-30 08:39:47
回复(0)
import java.util.*;
class TreeNode {
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public class Main {
public static int i = 0;
public static TreeNode CreateBinaryTree(String str) {
if(str==null) {
return null;
}
TreeNode root = new TreeNode(str.charAt(i));
i++;
if(root.val!='#') {
if(root.left==null) {
root.left = CreateBinaryTree(str);
}
if(root.right==null) {
root.right =CreateBinaryTree(str);
}
}
return root;
}
public static void inOrder(TreeNode root) {
if(null == root) {
return;
}
inOrder(root.left);
if(root.val!='#') {
System.out.print(root.val+" ");
}
inOrder(root.right);
}
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNextLine()) {
String s = scanner.nextLine();
TreeNode treenode = CreateBinaryTree(s);
inOrder(treenode);
}
}
}
发表于 2022-07-14 16:34:30
回复(0)
import java.util.*;
class TreeNode{
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val){
this.val=val;
}
}
public class Main{
public static int i=0;
public static TreeNode createTree(String str){
TreeNode root=null;
if(str.charAt(i)!='#'){
root=new TreeNode(str.charAt(i));
i++;
root.left=createTree(str);
root.right=createTree(str);
}else{
i++;
}
return root;
}
public static void inOrder(TreeNode root){
if(root==null){
return;
}
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
while(scanner.hasNextLine()){
String str=scanner.nextLine();
TreeNode root=createTree(str);
inOrder(root);
}
}
}
发表于 2022-05-20 18:55:49
回复(0)
import java.util.*;
class TreeNode{
public char val;
public TreeNode left;//二叉树的左孩子
public TreeNode right;//二叉树的右孩子
public TreeNode(char val) {
this.val = val;
}
}
public class Main {
public static int i = 0;
public static TreeNode createTree(String str){
TreeNode root = null;
if(str.charAt(i) != '#'){
root = new TreeNode(str.charAt(i));
i++;
//所给字符串为先序遍历，顺序为根->左->右
root.left = createTree(str);
root.right = createTree(str);
}else{
//能走到这一步，说明下一个数为空
i++;
}
return root;
}
public static void inOrder(TreeNode root){
if (root == null){
return;
}
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextLine()) { // 注意 while 处理多个 case
String str = in.nextLine();
TreeNode root = createTree(str);
inOrder(root);
}
}
}
发表于 2022-02-11 17:29:47
回复(0)
此题最大的难点就在于如何把题目所给的 abc##de#g##f###转换为对应的二叉树，这个步骤涉及到一种经典算法，没接触过的 coder 理解模板代码即可（模板不唯一，但思想大致相同）
private static int index = 0;
private static Tree createTree(String str){
if(index >= str.length() || str.charAt(index)=='#') {
index++;
return null;
}
Tree treeNode = new Tree(str.charAt(index++));
treeNode.left = createTree(str);
treeNode.right = createTree(str);
return treeNode;
}tips:
部分 coder 初次接触时可能会有疑问：为什么仅凭前序遍历序列就能确定对应的二叉树呢？其实是因为此类前序序列以 '#' 的形式给出了空结点所在的位置，因此可以唯一确定此树形态，若缺少空结点的信息，则单个遍历序列不能唯一确定一颗二叉树，需以前+中，或中+后，或其他组合才能唯一确定树的形态。
当确定出树的结构后，进行简单的中序遍历即可得出答案。
private static void inorderPrintTree(Tree tree){
if(tree==null) return;
inorderPrintTree(tree.left);
System.out.print(tree.value+" ");
inorderPrintTree(tree.right);
}以下是完整代码
import java.util.*;
public class Main {
static class Tree{
Tree left;
Tree right;
char value;
Tree(char value){this.value = value;}
}
private static int index = 0;
private static Tree createTree(String str){
if(index >= str.length() || str.charAt(index)=='#') {
index++;
return null;
}
Tree treeNode = new Tree(str.charAt(index++));
treeNode.left = createTree(str);
treeNode.right = createTree(str);
return treeNode;
}
private static void inorderPrintTree(Tree tree){
if(tree==null) return;
inorderPrintTree(tree.left);
System.out.print(tree.value+" ");
inorderPrintTree(tree.right);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()){
String str = in.next();
Tree root = createTree(str);
inorderPrintTree(root);
}
}
}
发表于 2022-01-18 11:27:02
回复(0)
import java.util.*;
class TreeNode{
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val){
this.val=val;
}
}
public class Main{
public static int i=0;
public static TreeNode createTree(String str){
if(str==null) return null;
TreeNode root=null;
if(str.charAt(i)!='#'){
root=new TreeNode(str.charAt(i));
i++;
root.left=createTree(str);
root.right=createTree(str);
}else{
i++;
}
return root;
}
public static void inorder(TreeNode root){
if(root==null){
return;
}
inorder(root.left);
System.out.print(root.val+" ");
inorder(root.right);
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();
TreeNode root= createTree(str);
inorder(root);
}
}
发表于 2021-12-20 22:08:09
回复(0)
import java.util.*;
public class Main {
// 树节点结构
static class TreeNode {
char val;
TreeNode left;
TreeNode right;
public TreeNode() {
super();
}
public TreeNode(char val) {
this.val = val;
}
}
static int p = 0; // 指向字符串参数的当前字符
// 递归终止条件不再是 root == null, 而变为 str.charAt(p) = '#'
private static TreeNode createTree(String str) {
if(str == null || str.length() == 0)
return null;
char val = str.charAt(p);
p++;
if(val == '#') {
return null;
}
TreeNode root = new TreeNode(val);
root.left = createTree(str);
root.right = createTree(str);
return root;
}
public static void inOrder(TreeNode root) {
if(root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
TreeNode root = createTree(str);
inOrder(root);
}
}
发表于 2021-10-11 11:05:13
回复(0)
import java.util.Scanner;
class TreeNode {//定义节点
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val) {//提供构造方法
this.val = val;
}
}
public class Main{
public static int i = 0;
//这个函数的步骤是：先根，再左，再右
public static TreeNode creatTree(String str) {
TreeNode root = null;
if (str.charAt(i) != '#') {//创建的i下标的元素不为#
root = new TreeNode(str.charAt(i));//new一个不为#的，前进过程中每一个节点都是根
i++;
root.left = creatTree(str);
root.right = creatTree(str);
}else {//创建的i下标的元素为#
i++;
}
return root;
}
public static void inorder(TreeNode root) {//中序遍历
if (root == null) return;
inorder(root.left);
System.out.print(root.val+" ");
inorder(root.right);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);//注意在上面导入包
String str = scanner.nextLine();
TreeNode root = creatTree(str);//定义一个root节点
inorder(root);//用中序遍历把结果输出
}
}
发表于 2021-05-15 11:16:57
回复(0)
import java.util.Scanner;
class Node{
char val;
Node left;
Node right;
Node(char val){ this.val = val;}
}
public class Main{
private static int index = 0;
//用来建立树的函数
public static Node buildTree(String input){
if(input.charAt(index) == '#'){
index++;
return null;
}
Node node = new Node(input.charAt(index));
index++;
node.left = buildTree(input);
node.right = buildTree(input);
return node;
}
//中序遍历二叉树的代码
public static void inOrder(Node root){
if(root != null){
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
while(scanner.hasNextLine()){
String input = scanner.nextLine();
index = 0;
Node root = buildTree(input);
inOrder(root);
}
}
}
发表于 2020-04-24 12:04:04
回复(0)
import java.util.*;
public class Main{
private static List<Character> l = new ArrayList<>();
public static int index = 1;
private static class TreeNode{
char val;
TreeNode left;
TreeNode right;
public TreeNode(char val){
this.val = val;
}
}
public static void main(String[] args){
try(Scanner in = new Scanner(System.in)){
char[] a = in.nextLine().toCharArray();
TreeNode root = new TreeNode(a[0]);
generateTree(a,root);
inOrder(root);
for(int i = 0;i < l.size();i++){
System.out.print(l.get(i) + " ");
}
System.out.println();
}
}
public static void generateTree(char[] a,TreeNode r){
if(r.val != '#'){
r.left = new TreeNode(a[index++]);
generateTree(a,r.left);
r.right = new TreeNode(a[index++]);
generateTree(a,r.right);
}
}
public static void inOrder(TreeNode r){
if(r.val == '#') return;
inOrder(r.left);
l.add(r.val);
inOrder(r.right);
}
}
发表于 2019-01-13 22:43:16
回复(0)
//鄙人之见，一个栈可以做到。将输入转为字符数组，依次push入栈，遇到字符#不push而是pop //结果恰为中序遍历
import java.util.Scanner;
import java.util.Stack;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
char[] ch = sc.nextLine().toCharArray();
Stack<Character> st = new Stack<>();
st.push(ch[0]);
for(int i=1;i<ch.length-1;i++){
if(ch[i] == '#'){
System.out.print(st.pop()+" ");
}else{
st.push(ch[i]);
}
}
System.out.println();
}
}
}
发表于 2018-08-05 01:17:56
回复(2)
不用建树，直接用两个栈就可，思路类似于中缀表达式
import java.util.Scanner;
import java.util.Stack;
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
Stack<Character> st = new Stack<Character>();
Stack<Character> symbol = new Stack<Character>();
String line = in.nextLine();
for (int i = 0; i < line.length(); ++i) {
if (!(line.charAt(i) == '#')) {
while (symbol.size() > 0) {
symbol.pop();
System.out.print(st.peek() + " ");
st.pop();
}
st.push(line.charAt(i));
} else {
symbol.push(line.charAt(i));
}
}
while (st.size() > 0) {
System.out.print(st.peek() + " ");
st.pop();
}
}
}
}
发表于 2018-03-23 22:49:33
回复(1)
问题信息
难度：
17条回答
608收藏
29638浏览
通过挑战的用户
查看代码-
2023-03-14 16:46:21
-
2023-03-14 15:01:02
-
2023-03-13 19:12:25
-
2023-03-13 11:45:16
-
2023-03-12 17:58:02
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
