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 = Line();

TreeNode root = createTestTree(s);

binaryTreeInOrder(root);

}

}

}

Java语言实现二叉树遍历：编一个程序，读入用户输入的一串先序遍相关教程