2023华为od统一考试B卷【二叉树中序遍历】

前言

博主刷的华为机考题，代码仅供参考，因为没有后台数据，可能有没考虑到的情况

如果感觉对你有帮助，请点点关注点点赞吧，谢谢你！

题目描述

思路

0.用Character数组存储树，index下标的左右子树下标是index*2+1，index*2+2

1.用一个栈来保存父亲节点：在操作{}内部的数据时入栈（也就是碰到“{”时）

2.遇到 {, 的情况就是直接是index的左子树为空，右子树存在index=index*2+2

3.遇到 { 情况，（没有和 , 连接）index的左子树index=index*2+1

4.遇到 ， 的情况：如果是左右两个子树都存在，index指向左子树，index++就ok

5. 遇到 } 出栈 index=出栈元素也就是父亲节点

6. 遇到节点字符（字母）写入Character数组

7.中序遍历（比较简单，递归实现）

8. 这道题难在处理字符串构建二叉树

代码

import java.util.Scanner;
import java.util.Stack;/*
a{b{d,e{g,h{,I}}},c{f}}*/
public class Main {public static void main(String[] args) {Scanner in=new Scanner(System.in);String str=in.nextLine();Character[] arr=new Character[202];int index=0;Stack<Integer>stack=new Stack<>();for (int i = 0; i < str.length();i++) {if(str.charAt(i)=='{'){stack.push(index);if(str.charAt(i+1)==','){index=index*2+2;}else{index=index*2+1;}}else if(str.charAt(i)==','){if(str.charAt(i+1)!='}'&&str.charAt(i-1)!='{'){index++;}}else if(str.charAt(i)=='}'){index=stack.peek();stack.pop();}else{arr[index]=str.charAt(i);}}ZX(arr,0);}private static void ZX(Character[] arr,int index){if(arr[index]==null)return;ZX(arr,index*2+1);System.out.print(arr[index]);ZX(arr,index*2+2);}
}