求构造先序后序线索二叉树方法，并求解释

Question

本帖最后由 hhugoo 于 2013-03-12 17:11:31 编辑

Answer 1

public class ThreadBinaryTree<T>                 //先序线索二叉树类，泛型T指定结点的元素类型
{
    public ThreadNode<T> root;    public ThreadBinaryTree()                    //构造空先序线索二叉树
    {
        this.root = null;
    }    public boolean isEmpty()                     //判断先序线索二叉树是否空
    {
        return root==null;
    }    public ThreadBinaryTree(T[] prelist)         //以标明空子树的先根序列构造二叉树并进行先序线索化
    {
        this.root = create(prelist);
        preorderThread(this.root);
    }
    //以标明空子树的先根序列构造一棵子二叉树，子树的根值是prelist[i]，返回所创建子树的根结点
    private int i=0;
    private ThreadNode<T> create(T[] prelist)
    {
        ThreadNode<T> p = null;
        if (i<prelist.length)
        {
            T elem=prelist[i++];
            if (elem!=null)
            {
                p = new ThreadNode<T>(elem);
                p.left = create(prelist);
                p.right = create(prelist);
            }
        }
        return p;
    }
  //先序线索化以p结点为根的子树，p的前驱结点是front
    private ThreadNode<T> front=null;
   
    private void preorderThread(ThreadNode<T> p)
    {
        if (p!=null)
        {
        
            if (p.left==null)                    //若p的左子树为空
            {
                p.ltag=1;                        //设置左线索标记
                p.left=front;                    //设置p.left为指向前驱front的线索
            }
            if (p.right==null)                   //若p的右子树为空
                p.rtag=1;                        //设置右线索标记
            if (front!=null && front.rtag==1) 
                front.right=p;                   //设置前驱front.right为指向后继p的线索
            front=p;
            preorderThread(p.left);               //先序线索化p的左子树
             preorderThread(p.right);              //先序线索化p的右子树
           
        }
    }
}我想的结果是将中序中“preorderThread(p.left);”放到“preorderThread(p.right); ”前，但是总是异常
Exception in thread "main" java.lang.StackOverflowError
at ThreadBinaryTree.preorderThread(ThreadBinaryTree.java:56)

也就是preorderThread(p.left);这一行

Answer 2

能不能先条理化地文字描述一下这个方法的意图呢？
preorderThread(ThreadNode<T> p)