질서정연한 정수 그룹을 두 갈래 나무에 놓다
#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
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.