질서정연한 정수 그룹을 두 갈래 나무에 놓다

2806 단어
질서수 그룹에 대해 중간 노드를 루트 노드로 하고 수조를 두 부분으로 나누며 수조의 두 부분을 귀속시켜 좌우 트리를 구축한다
#include <stdio.h>
#include <stdlib.h>
#include <queue>
template<typename T>
class TreeNode {
 public:
  TreeNode() : left_(NULL), right_(NULL) {}
  T value_;
  TreeNode* left_;
  TreeNode* right_;
  bool operator<(const TreeNode& right) {
    return value_ < right.value_;
  }
};
template<typename T>
void Swap(T& left, T& right) {
  T tmp = left;
  left = right;
  right = tmp;
}
template<typename T>
int Partition(T array[], int begin, int end) {
  int i = begin - 1;
  T x = array[end];
  for (int j = begin; j < end; ++j) {
    if (array[j] < x) {
      Swap(array[i + 1] , array[j]);
      i++;
    }
  }
  Swap(array[i + 1], array[end]);
  return i + 1;
}
template<typename T>
void QuickSort(T array[], int begin, int end) {
  if (end > begin) {
    int position = Partition(array, begin, end);
    QuickSort(array, begin, position - 1);
    QuickSort(array, position + 1, end);
  }
}
template<typename T>
TreeNode<T>* BuildTree(TreeNode<T> array[], int begin, int end) {
  if (begin < end) {
    int middle = begin + (end - begin + 1) / 2;
    array[middle].left_ = BuildTree(array, begin, middle - 1);
    array[middle].right_ = BuildTree(array, middle + 1, end);
    return array + middle;
  } else if(begin == end) {
    return array + begin;
  } else {
    return NULL;
  }
}
template<typename T, typename VisitFun>
void PreOrderVisit(TreeNode<T>* current, VisitFun visit_fun) {
  if (current) {
    visit_fun(current->value_);
    PreOrderVisit(current->left_, visit_fun);
    PreOrderVisit(current->right_, visit_fun);
  }
}
template<typename T, typename VisitFun>
void VisitTree(TreeNode<T>* current, VisitFun visit_fun) {
  std::queue<TreeNode<T>*> node_queue;
  node_queue.push(current);
  while (!node_queue.empty()) {
    current = node_queue.front();
    visit_fun(current->value_);
    node_queue.pop();
    if (current->left_) {
      node_queue.push(current->left_);
    }
    if (current->right_) {
      node_queue.push(current->right_);
    }
  }
}
void PrintInt(int value) {
  printf("%d ", value);
}
int main(int argc, char** argv) {
  const int kNodeAmount = 1;
  TreeNode<int> tree[kNodeAmount];
  for (int i = 0; i < kNodeAmount; ++i) {
    tree[i].value_ = rand() % 100;
  }
  QuickSort(tree, 0, kNodeAmount - 1);
  for (int i = 0; i < kNodeAmount; ++i) {
    printf("%d ", tree[i].value_);
  }
  printf("
"); TreeNode<int>* head = BuildTree(tree, 0, kNodeAmount - 1); VisitTree(head, PrintInt); //PreOrderVisit(head, PrintInt); }

참고: 구축 과정에서 begin ==end와 end

좋은 웹페이지 즐겨찾기