代码有点混乱，C/C++不分，主要集中在createtree的 int &size形参上，其实最好是建个类存储当前层的SIZE，或者其他办法。因时间问题，不再更改。

#include <iostream>
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  findSecond
 *  Description:  算法导论练习 9.1-1
 *  证明：在最坏情况下，利用n + lgn -2次比较，，即可找到n个元素中的第2个小元素
 *  （提示：同时找最小元素）
 *  限制：需要支持随机迭代
 *  思路：起先想到用分治算法，但设计不出，还是忍不住看了算法导论的答案：
 *
 * To find the smallest element construct a tournament as follows:
 * Compare all the numbers in pairs.
 * Only the smallest number of each pair is potentially the
 smallest of all so the problem is reduced to size n/2 .
 * Continuing in this fashion until there is only one left clearly solves the problem.
 * Exactly n − 1 comparisons are needed since the tournament can be drawn as an n-leaf binary
tree
  which has n − 1 internal nodes (show by induction on n).
 * Each of these nodes correspond to a comparison.
 * We can use this binary tree to also locate the second
 * smallest number. The path from the root to the smallest element
 * (of height lg n ) must contain the second smallest element. Conducting
 * a tournament among these uses lg n − 1 comparisons.
 * The total number of comparisons are: n − 1 + lg n − 1 = n + lg n − 2.
 * =====================================================================================
 */

bool compInt(const int &a, const int &b)
{
  return a < b;
}

template <typename T>
class findSecondNode {
public:
  findSecondNode() : element(0), compareElement(0), child(0) { }
  findSecondNode(const T *elementArg, const T *compareElementArg, const findSecondNode<T> *childArg)
    : element(elementArg), compareElement(compareElementArg), child(childArg) { }
  const T *element;          /* 本元素指针 */
  const T *compareElement;   /* 与本元素比较的元素指针 */
  const findSecondNode<T> *child;            /* 二叉树子节点，与本元素同值 */
};

template <typename T, typename compFunc>
const findSecondNode<T> *createTree(const findSecondNode<T> *array, int &size, compFunc func);

template <typename T, typename compFunc>
const T *findSecond(T *array, int size, compFunc func);

#include <iostream>
#include <vector>
#include "find2nd.h"

// 如果失败，返回0值。
template <typename T, typename compFunc>
const findSecondNode<T> *createTree(const findSecondNode<T> *array, int &size,
compFunc func)
{
  if (size <= 0) {
    size = 0;
    return static_cast<findSecondNode<T> *>(0);
    }
  if (size == 1){
    size = 0;
    return array;
    }

  bool isEvenSize;
  int rowSize;
  if ((size % 2) != 0) {
    isEvenSize = false;
    rowSize = size / 2 + 1;
  } else {
    isEvenSize = true;
    rowSize = size / 2;
  }

  findSecondNode<T> *row = new findSecondNode<T>[rowSize];
  int i;
  for (i = 0; i < size -1; i += 2)
    if (func(*(array[i].element), *(array[i + 1].element))) {
      row[i / 2] = findSecondNode<T>(array[i].element, array[i + 1].element, array + i);
    } else {
      row[i / 2] = findSecondNode<T>(array[i + 1].element, array[i].element, array
+ i + 1);
    }

  if (!isEvenSize) {
    row[rowSize - 1] = findSecondNode<T>(array[i].element,
static_cast<T *>(0), array +
i - 1);
  }
  size = rowSize;
  return row;
}

template <typename T, typename compFunc>
const T *findSecond( T *array, int size, compFunc func)
{
  if (size <= 1)
    return 0;
  if (size == 2)
    return func(array[0], array[1]) ? array : array + 1;
  findSecondNode<T> *row;

  bool evenNumSize;
  int rowSize;
  if ((size % 2) != 0) {
    evenNumSize = false;
    rowSize = size / 2 + 1;
  } else {
    evenNumSize = true;
    rowSize = size / 2;
  }

  row = new findSecondNode<T>[rowSize];

  int i;
  for (i = 0; i < size -1; i += 2)
    if (func(array[i], array[i + 1])) {
      row[i / 2] = findSecondNode<T>(array + i, array +i + 1,
static_cast<findSecondNode<T> *>(0));
    } else {
      row[i / 2] = findSecondNode<T>(array + i + 1, array + i,
static_cast<findSecondNode<T> *>(0));
    }

  if (!evenNumSize)
    row[rowSize -1] = findSecondNode<T>(array + i, static_cast<T *>(0),
static_cast<findSecondNode<T> *>(0));

  std::vector<const findSecondNode<T> *> destructor;
  destructor.push_back(row);
  const findSecondNode<T> *ptr = row;

  while ((ptr = createTree(ptr, rowSize, func)) !=
         static_cast<const findSecondNode<T> *>(0))
      destructor.push_back(ptr);
  destructor.pop_back();
  ptr = destructor.at(destructor.size() - 1);
  const T *maySecond = ptr->compareElement;
  const T *tmp;
  while (ptr->child) {
    tmp = ptr->child->compareElement;
    if (tmp != 0 && func(*tmp, *maySecond))
      maySecond = tmp;
    ptr = ptr->child;
  }
  for (int i = destructor.size() - 1; i >= 0; i--)
    delete [] destructor.at(i);
  return maySecond;
}

//最好不要比较double值，不精确，此处只是展示
bool compDouble(const double &a, const double &b)
{
  return a < b;
}
int main ( int argc, char *argv[] )
{

  int a[10] = {90, 234, 234, 11, 5435, 89, 2423, 122, 99, 99};

  const int *tmp = findSecond(a, 10, compInt);
  std::cout << *tmp << std::endl;

  double b[9] = {23.33, 2342.22, 12.33, 2134.222, 5555.33, 242.2, 888,
                 1.333, 2342.222};

//最好不要比较double值，不精确，此处只是展示
  const double *tmpDouble = findSecond(b, 9, compDouble);
  std::cout << *tmpDouble << std::endl;
  return 0;
}       /* ----------  end of function main  ---------- */