利用JAVA 先序建立二叉树 #表示空树。例如输入ABC##DE#G##F### 先序遍历输出ABCDEGF 我写的程序不能输出

Question

import java.util.*;
class Node{
Node left;
Node Right;
char data;//节点数据
void print()
{
System.out.println(data+"");
}
public Node()
{
this.left=null;
this.Right=null;
}
public Node(char data){
this.left=null;
this.Right=null;
this.data=data;

}

}

class BTree {
static Node root=new Node();//为根节点分配空间
static char ch[];//输入的字符串

static void CreateTree(Node node)//先序建立二叉树
{
int i=0;

if(ch[i]=='#')
{
node=null;
i++;
}

else
{
node=new Node(ch[i]);i++;
CreateTree(node.left);
CreateTree(node.Right);

}
}
static public void preorder(Node node)//先序遍历二叉树
{
if(node!=null){
node.print();
preorder(node.left);
preorder(node.Right);
}
else{
System.out.println("Tree node is empty");
}

}
}
public class Tree{
public static void main(String args[])
{
Scanner reader=new Scanner(System.in);
char ch[]=new char[10];
ch[0]='a';
for(int i=0;ch[i]!='*';i++)//读取输入字符数组，以*结尾
ch[i]=reader.next().charAt(0);
BTree.CreateTree(BTree.root);
BTree.preorder(BTree.root);
}
}

Answer 1

你的程序有诸多问题，你的程序运行时候应该也会报错的吧？
这个写法不是很通用，不过我还是按照你的源码修改成了你想要的结果。
结构上基本一致，可实现基本已经面目全非了。
我用字符串代替了手工输入，你要是喜欢手工输入，你可以把我那个注释掉，用你自己的……
以下是修改后可用的代码：

import java.util.*;

class Node {
Node left;
Node Right;
char data;// 节点数据

void print() {
System.out.println(data + "");
}

public Node() {
this.left = null;
this.Right = null;
}

public Node(char data) {
this.left = null;
this.Right = null;
this.data = data;

}

}

class BTree {
static Node root = new Node();// 为根节点分配空间
static char ch[];// 输入的字符串
static int i = 0;

static Node CreateTree()// 先序建立二叉树
{
Node node = null;
if (ch[i] == '#') {
node = null;
i++;
}else {
node = new Node();
node.data = ch[i];
i++;
node.left = CreateTree();
node.Right = CreateTree();

}
return node;
}

static public void preorder(Node node)// 先序遍历二叉树
{
if (node != null) {
node.print();
preorder(node.left);
preorder(node.Right);
} else {
System.out.println("Tree node is empty");
}

}
}

public class Tree {
public static void main(String args[]) {
Scanner reader = new Scanner(System.in);
BTree.ch = new char[16];
BTree.ch[0] = 'a';
// 读取输入字符数组，以*结尾
BTree.ch = "ABC##DE#G##F###".toCharArray();
//for (int i = 0; (BTree.ch[i] = reader.next().charAt(0)) != '*'; i++){}
BTree.root = BTree.CreateTree();
BTree.preorder(BTree.root);
}
}追问

static Node CreateTree()// 先序建立二叉树
{
Node node = null;
if (ch[i] == '#') {
node = null;
i++;
}else {
node = new Node();
node.data = ch[i];
i++;
node.left = CreateTree();
node.Right = CreateTree();

}
return node;
}

递归看不太明白，我看别人都是把节点当做参数传进递归函数里CreateTree(node.left); 你用赋值的话节点之间怎么联系起来啊？

追答

“别人”你指的应该是其他编程语言吧？java传递的时候传递的是引用，而且你的node没有父节点的引用，你传入node.left的时候，node.left可值可是null哦，所以，node.left一直是null
你在方法里面new的node只是局部变量，为了得到这个临时生成的node，只能通过方法return来转换一下思路，得到这个node的引用，赋值给node.left，这就是这里这个写法的原因
而没有使用void

本回答被提问者采纳