简单数据结构---二叉树的建树问题：递归建树无法进入第二层，求解

0 0

简单数据结构---二叉树的建树问题：递归建树无法进入第二层，求解5

小弟刚刚学习数据结构，遇到了一个问题，代码如下

/**
 * 二叉树的节点类
 * @author se7en
 *
 */
public class JTreeNode {
	private int nValue;//节点的值
	private JTreeNode leftChild;//节点的左指针
	private JTreeNode rightChild;//节点的右指针
	public JTreeNode(int nValue){
		this.nValue = nValue;
	}
	public void setnValue(int nValue) {
		this.nValue = nValue;
	}
	public int getnValue() {
		return nValue;
	}
	public void setRightChild(JTreeNode rightChild) {
		this.rightChild = rightChild;
	}
	public JTreeNode getRightChild() {
		return rightChild;
	}
	public void setLeftChild(JTreeNode leftChild) {
		this.leftChild = leftChild;
	}
	public JTreeNode getLeftChild() {
		return leftChild;
	}
}

public class JTree {
	private JTreeNode root;//根节点
	public void add(int nValue){
		JTreeNode tem = new JTreeNode(nValue);
		add(root,tem);
	}
	private void add(JTreeNode root,JTreeNode node){
		//若树为空
		if(root==null){
			root = node;
			return;
		}
		//若树不为空，则比该较节点与根节点的大小
		else{
			//若小于等于，则递归遍历左子树
			if(node.getnValue()<=root.getnValue()){
				add(root.getLeftChild(),node);
			}
			//若大于，则递归遍历右子树
			else{
				add(root.getRightChild(),node);
			}
		}
	}
	//中序遍历：根左右
	public void middleTravel(JTreeNode root){
		if(root == null){
			System.out.println(root.getnValue()+" ");
		}
		else{
			middleTravel(root.getLeftChild());
			middleTravel(root.getRightChild());
		}
	}
}

出问题的地方是在这个方法

private void add(JTreeNode root,JTreeNode node){
		//若树为空
		if(root==null){
			root = node;
			return;
		}
		//若树不为空，则比该较节点与根节点的大小
		else{
			//若小于等于，则递归遍历左子树
			if(node.getnValue()<=root.getnValue()){
				add(root.getLeftChild(),node);
			}
			//若大于，则递归遍历右子树
			else{
				add(root.getRightChild(),node);
			}
		}
	}

我的想法是这样的：第一个传入参数，root为空，直接将node赋给root，第二次传入参数时，root不为空，则比较大小，进入第二层的递归。
问题就来了，不管我第几次传入参数，测试时，root的值都为空，也就是说每次递归都是只停留在第一次，一直无法进入二层递归，这是为什么？

数据结构递归二叉树中序遍历

2013年11月21日 13:06

蓝杰Seven
26
0 0 3

2个答案按时间排序按投票排序

0 0

采纳的答案

我改了一下，可以通过了。很多都是空指针问题。

public class JTree {
public JTreeNode root;//根节点
public void add(int nValue){
JTreeNode tem = new JTreeNode(nValue);
if (root == null) {
    root = tem;
} else {
    add(root,tem);
}
}
private void add(JTreeNode root,JTreeNode node){
//若树为空
if(root==null){
root = node;
return;
}
//若树不为空，则比该较节点与根节点的大小
else{
//若小于等于，则递归遍历左子树
if(node.getnValue()<=root.getnValue()){
    JTreeNode child = root.getLeftChild();
    if (child == null) {
                    root.setLeftChild(node);
    } else {
        add(child,node);
    }
}
//若大于，则递归遍历右子树
else{
                JTreeNode child = root.getRightChild();
                if (child == null) {
                    root.setRightChild(node);
                } else {
                    add(child,node);
                }
}
}
}
//中序遍历：根左右
public void middleTravel(JTreeNode root){
if(root != null){
System.out.println(root.getnValue()+" ");
            middleTravel(root.getLeftChild());
            middleTravel(root.getRightChild());
}
}

public static void main(String[] args) {
    JTree tree = new JTree();
    tree.add(5);
        tree.add(2);
        tree.add(8);
        tree.middleTravel(tree.root);
}
}