如何遍历一棵完全二叉树到指定的第k层的从左到右第i个节点？请高手赐教。

采用什么存储结构来存储这个完全二叉树?

用链表存储。其实我是想用链表存储一个最大堆。提供插入,删除最大节点和初始化功能。

你说的这个问题,我用一个递归解决了,刚写好的代码如下,已经测试通过了:
/////////////////////////////////////////////////
//Locateki()公有成员函数
//递归:得到当前链表式的完
//全二叉树subTree的第k层的第i个结点
/////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::Locateki(
           BinTreeNode<T>* subTree,int k,int i)
{
    if(k==1)                //递归结束的条件
        return subTree;
    else
    {
        int n=pow(2,k-1);   //首先计算k层上应该具有的满结点数
        int s=n/2;
        if(i<=s)            //如果在右半边从左子树递归
            return Locateki(
            subTree->leftChild
               ,k-1,i);
        else                //如果在左半边从右子树递归
            return Locateki(
            subTree->rightChild
               ,k-1,i-s);
    };
};
///////////////////////////////Locateki()函数结束
主要的思想是,左右分支的界定，你可以看我写的注释，

PS:我觉得最大堆没有必要用链式来存储吧？如果用链式的话最多递归代码比较好写，可是时间复杂度好像不如用线性表...

我写的是自顶向下的递归，你也可以用堆栈写自底向上的方法，都是可以的，只是递归可以一幕了然.当然自顶向下也可以使用循环，每次判断一下走左边还是走右边，总之方法是多种多样的。

[[it] 本帖最后由 geninsf009 于 2008-12-13 22:59 编辑 [/it]]

谢谢！你的方法我已经用在插入算法中了。
template<class T>
MaxHeap<T>& MaxHeap<T>::Insert(const T& x) {//把x插入到最大堆中
    int k = (int) (log(state) / log(2)) + 1;//树的层数，state是当前堆的节点数目
    int index = state - (int) (pow(2, k - 1) - 1);//最后节点的位置
    int p_index = index / 2 + 1;//父节点从左至右的位置
    BinaryTreeNode<T> *temp = new BinaryTreeNode<T> (x);
    last = temp;//last指针指向最后一个节点
    if (index == (int) (pow(2, k - 1))) {//当前层已满
        p_index = 1;//父节点设为当前层的第一个节点
        ConditionOrder(root, k, p_index, temp);
    } else
        ConditionOrder(root, k - 1, p_index, temp);
    return *this;
}

template<class T>
void MaxHeap<T>::ConditionOrder(BinaryTreeNode<T> *u, int k, int i,
        BinaryTreeNode<T> *temp) { //根据参数条件遍历堆
    //如果当前节点的子树有一为空，把temp设为其子树
    int half = (int) pow(2, k - 2);//堆的第k层应有节点总数的一半
    if (u->data < temp->data) {//要插入的元素比当前节点大
        Swap(u->data, temp->data);
    }
    if (!u->LeftChild || !u->RightChild) {//左右子树有一为空,在此加入节点
        if (!u->LeftChild) {//左子树为空
            u->LeftChild = temp;//加入新节点
            state++;//节点数目加1
        } else {//右子树为空
            u->RightChild = temp;
            state++;//节点数目加1
        }
    } else {
        if (i <= half)//左子树
            ConditionOrder(u->LeftChild, k - 1, i, temp);
        else
            //右子树
            ConditionOrder(u->RightChild, k - 1, i - half, temp);
    }
}

但是删除最大节点和初始化怎么实现呢？
对于删除最大节点，我定义了一个last指针，指向最后一个插入的节点，但是删除一次后，last指针的定位问题就不好办了...
哎... 我也知道最大堆用公式化描述更好些，可是规定用链表存储，没办法啊...

还是用你的Locateki()函数来确定last指针的位置吧.
我觉得你应该在你的MaxHeap<T>中增加两个数据成员
int lk,li;分别用于表示当前的最大堆的最后一个结
点的所在的层次,以及在该层中的位置,然后再通过前
面的Locateki()函数来确定删除后的最后一个结点的
指针的位置.

或者在你的MaxHeap<T>中设置一个表示总结点数的数
据成员n,每次删除后通过n计算最后一个结点的层次
和在当前层次的位置，再用Locateki()函数来确定last
指针的位置也可以.

[[it] 本帖最后由 geninsf009 于 2008-12-14 15:22 编辑 [/it]]