二叉树的构建及遍历

太过爱你忘了你带给我的痛 2023-10-14 19:39 47阅读 0赞

题目链接:[https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking][https_www.nowcoder.com_practice_4b91205483694f449f94c179883c1fef_tpId_60_tqId_29483_rp_1_ru_activity_oj_qru_ta_tsing-kaoyan_question-ranking]

--------------------

#### 题目 ####

> **编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC\#\#DE\#G\#\#F\#\#\# 其中“\#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。**

#### **输入描述：** ####

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

#### 输出描述： ####

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

#### **示例** ####

> **输入：abc\#\#de\#g\#\#f\#\#\#** 
> 
> **输出：c b e g d f a**

--------------------

### 解题 ###

#### **对题目的理解** ####

**由先序遍历字符串： ABC\#\#DE\#G\#\#F\#\#\#**

**构建的二叉树如图:**

![e931d460e9de42b3b3b2baaa2f66da08.png][]

**注:前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。**

--------------------

#### 代码展开 ####

由于博客中图片清晰度不够,本博主以摆烂

高清的代码展开图片可自行下载后观看

[https://pan.baidu.com/s/1SDV2MHfMz855kLQV68XquA?pwd=0213][https_pan.baidu.com_s_1SDV2MHfMz855kLQV68XquA_pwd_0213]

![c4557c8e44384d1ea4d172d19ad75cbe.png][]

左上方

![3208311d2844442a8db4e324284a02c6.png][]

左下方

![4b0d5ff004734849b8d6d67f6211d700.png][]

右上方![35b3e0d7fadc49bea9eed723740d0dd7.png][]

右下方

![6613561ef0164bf1a87c52bdc852a2d3.png][]

![d15511837ba34bb0bd21c26b28e1bcbe.png][]

![bb44ac1e40894afaa61cf3bf8c90f8e0.png][]

--------------------

#### 解题代码 ####

import java.util.Scanner;
    class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val){
            this.val=val;
        }
    }
    // 注意类名必须为 Main, 不要有任何 package xxx 信息
    public class Main {
        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);//中序遍历
                i=0;//置零,为下一次读取做准备
            }
        }
        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);//右子树
        }
    }

#### 运行结果 ####

![b3edc7b90a59459fac2efdb402318a62.png][]

[https_www.nowcoder.com_practice_4b91205483694f449f94c179883c1fef_tpId_60_tqId_29483_rp_1_ru_activity_oj_qru_ta_tsing-kaoyan_question-ranking]: https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
[e931d460e9de42b3b3b2baaa2f66da08.png]: https://img-blog.csdnimg.cn/e931d460e9de42b3b3b2baaa2f66da08.png
[https_pan.baidu.com_s_1SDV2MHfMz855kLQV68XquA_pwd_0213]: https://pan.baidu.com/s/1SDV2MHfMz855kLQV68XquA?pwd=0213
[c4557c8e44384d1ea4d172d19ad75cbe.png]: https://img-blog.csdnimg.cn/c4557c8e44384d1ea4d172d19ad75cbe.png
[3208311d2844442a8db4e324284a02c6.png]: https://img-blog.csdnimg.cn/3208311d2844442a8db4e324284a02c6.png
[4b0d5ff004734849b8d6d67f6211d700.png]: https://img-blog.csdnimg.cn/4b0d5ff004734849b8d6d67f6211d700.png
[35b3e0d7fadc49bea9eed723740d0dd7.png]: https://img-blog.csdnimg.cn/35b3e0d7fadc49bea9eed723740d0dd7.png
[6613561ef0164bf1a87c52bdc852a2d3.png]: https://img-blog.csdnimg.cn/6613561ef0164bf1a87c52bdc852a2d3.png
[d15511837ba34bb0bd21c26b28e1bcbe.png]: https://img-blog.csdnimg.cn/d15511837ba34bb0bd21c26b28e1bcbe.png
[bb44ac1e40894afaa61cf3bf8c90f8e0.png]: https://img-blog.csdnimg.cn/bb44ac1e40894afaa61cf3bf8c90f8e0.png
[b3edc7b90a59459fac2efdb402318a62.png]: https://img-blog.csdnimg.cn/b3edc7b90a59459fac2efdb402318a62.png