本文主要是介绍java 键盘输入二叉树_Java语言实现二叉树遍历:编一个程序,读入用户输入的一串先序遍...,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Java语言实现二叉树遍历:编一个程序,读入用户输入的一串先序遍
Java语言实现二叉树遍历:编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。
目录
1 题目描述
2 解题思路
3 代码实现
1 题目描述
编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。
2 解题思路
将根据输入的先序遍历字符串创建一个二叉树,之后对该二叉树进行中序遍历即可。
在先序遍历的过程中,如果没有遇到“#”,则将该结点存储到root结点的位置,再通过递归的方法判断该左子树是否为空,同样的,用递归判断右子树,直到root为null为止。
在中序遍历的过程中,先将二叉树一直向左走到“尽头”,再进行输出,同样也需要调用递归函数~
3 代码实现
import java.util.*;
//定义节点类,保存结点值以及左右孩子的地址
class TreeNode{
char value;
TreeNode right;
TreeNode left;
public TreeNode(char value){
this.value = value;
}
}
public class Main{
//中序遍历
public static void binaryTreeInOrder(TreeNode root) {
if (root == null){
return;
}
binaryTreeInOrder(root.left);
System.out.print(root.value+" ");
binaryTreeInOrder(root.right);
}
//定义全局变量
public static int i = 0;
//根据输入的先序遍历字符串创建二叉树
public static TreeNode createTestTree(String s){
TreeNode root = null;
if (s.charAt(i) != '#'){
//创建新的结点,并递归链接左右孩子结点
root = new TreeNode(s.charAt(i));
i++;
root.left = createTestTree(s);
root.right = createTestTree(s);
}else {
//若遇到'#',则向后遍历字符串
i++;
}
//返回根节点
return root;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()){
String s = scanner.nextLine();
TreeNode root = createTestTree(s);
binaryTreeInOrder(root);
}
}
}
Java语言实现二叉树遍历:编一个程序,读入用户输入的一串先序遍相关教程
这篇关于java 键盘输入二叉树_Java语言实现二叉树遍历:编一个程序,读入用户输入的一串先序遍...的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!