好久没有看过了，基本上也是忘的差不多了…………（貌似一开始就没有弄懂……）

我可以写非递归的算法吗？

//////////////////////////////////////////////////
//公有成员函数preOrder()
//非递归求前序遍历中第k个结点指针的算法
//////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::preOrder(int k)
{
    //回溯用的堆栈
    LinkedStack<BinTreeNode<T>* > LS;
    //结点遍历指针
    BinTreeNode<T>* p=root;
    //先把空指针入堆栈
    LS.Push(NULL);
    //遍历的过程
    int  count=0;         //计数器
    while(p!=NULL)
    {
    count++;         //访问当前结点
         if(count==k)     //找到第k个结点
              return p;
    if(p->rightChild!=NULL)      //如果右子结点不空
         LS.Push(p->rightChild); //把由子结点指针入栈
    if(p->leftChild!=NULL)       //如果左子结点不空
         p=p->leftChild;         //进入左子树
    else                         //如果左子树为空
         LS.Pop(p);              //回溯到右子树
    }
        return NULL;                  //没有找到
};
///////////////////////////////preOrder()函数结束

看看了你的题目，刚刚写的程序，在我写的BinaryTree<T>类模板里添加了一个这个刚写的成员函数，供你参考，
另外LinkedStack<T>是我写的一个链栈的类模板，这里定义的栈是BinTreeNode<T>*类型的堆栈.

该题目的递归算法，我还在思考中，小弟不才，能力有限，,等想得有头绪了，再发代码一起讨论...

[[it] 本帖最后由 geninsf009 于 2008-8-23 00:05 编辑 [/it]]

好啦，替你搞定了，刚写的递归算法：

//////////////////////////////////////////////////
//SearchpreOrder()私有成员函数
//得到前序序列中第k个结点的指针
//////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::SearchpreOrder(int k,BinTreeNode<T>* subTree)
{
    if(subTree!=NULL)
    {
        int T=Size(subTree);             //树的总结点数
        int TL=Size(subTree->leftChild); //树的左子树结点数
        int TR=Size(subTree->rightChild);//树的右子树结点数

        if(k==1)               //如果k=1,那要找的就是子树根结点
            return subTree;
        else if((k-1)<=TL)        //如果在左子树中
            return SearchpreOrder(k-1,subTree->leftChild);
        else if((k-1)>TL && k<=T) //如果在右子树中
            return SearchpreOrder(k-1-TL,subTree->rightChild);
        else                      //如果超过树的总结点数
            return NULL;
    }
    else
        return NULL;
};
/////////////////////////私有SearchOrder()函数结束

其中用到的Size()也是个私有递归函数，定义如下：

//////////////////////////////////////////////////
//私有成员函数Size()
//得到二叉树的总接点的个数
//////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::Size(BinTreeNode<T>* subTree)
{
    //子树为空,则结点数为0
    if(subTree==NULL)
         return 0;
    else
         return 1+Size(subTree->leftChild)+Size(subTree>rightChild);
};
////////////////////////////////////Size()函数结束

[[it] 本帖最后由 geninsf009 于 2008-8-23 20:09 编辑 [/it]]

我是又为我的BinaryTree<T>增加了一个新的成员函数，
你可能不太好直接调试，不过你可以照着我的思想自己再编写的，
我已经调试过了，结果是正确的.

我都是经过自己的思考给别人写顶帖，
希望自己好心有好报...