根据一个数组，创建一个Segment Tree(线段树)

线段树的特点

线段树的优势

线段树的构造过程

（0，5）37：数组元素下标0~5的元素之和是37
（0，2）21：数组元素下标0~2的元素之和是21

线段树的基本数据结构（结点结构由五个分量组成）

运行结果

（C语言代码）递归的创建一颗线段树，然后中序、先序、后序遍历这个结点

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct TNode{
	/*线段树的结点结构*/
	int lidx, ridx;
	struct TNode *left, *right;
	int sum;
} TNode, *SegmentTree;

typedef struct QNode{
	/*队列的结点结构，队列用于层序遍历线段树*/
	TNode* ptr2TNode;
	struct QNode *next;
} QNode, *Queue;

SegmentTree build(int* arr, int l, int r);
void inOrder(SegmentTree T);
void preOrder(SegmentTree T);
void postOrder(SegmentTree T);
void levelOrder(SegmentTree T, Queue queue);
void visit(TNode* Node);
Queue initQueue();
TNode* delete(Queue queue);
void add(Queue queue, TNode* Node);
bool isEmpty(Queue queue);

int main(int argc, char* argv[]) {
	int arr[] = {8, 4, 9, 11, 3, 2};
	SegmentTree SegTree = build(arr, 0, 5);
	
	/*中序遍历线段树*/
	printf("InOrder   : ");
	inOrder(SegTree);
	printf("\n");

	/*先序遍历线段树*/
	printf("PreOrder  : ");
	preOrder(SegTree);
	printf("\n");

	/*后序遍历线段树*/
	printf("PostOrder : ");
	postOrder(SegTree);
	printf("\n");

	/*层序遍历线段树*/
	printf("LevelOrder: ");
	Queue queue = initQueue();
	levelOrder(SegTree, queue);

	return 0;
}

SegmentTree build(int* arr, int l, int r) {
    /*创建一颗线段树*/
	TNode* T = (TNode*)malloc(sizeof(TNode));
	T->lidx = l, T->ridx = r;
    /*叶子节点的left和right指针都是空
      叶子结点的sum域对应于数组的元素
      非叶子节点的left和right指针需要递归创建
      非叶子节点的sum域等于左右孩子的sum域之和
    */
	if (l < r) {
		T->left = build(arr, l, (l+r)/2);
		T->right = build(arr, (l+r)/2 + 1, r);
		T->sum = T->left->sum + T->right->sum;
	} else if(l == r) {
		T->left = NULL, T->right = NULL;
		T->sum = arr[l];
	}
	return T;
}

void inOrder(SegmentTree T) {
    /*先序遍历线段树*/
	if (T != NULL) {
		inOrder(T->left);
		visit(T);
		inOrder(T->right);
	}
}

void visit(TNode* Node) {
    /*访问线段树的结点*/
	printf("%2d ", Node->sum);
}

void preOrder(SegmentTree T) {
    /*先序遍历线段树*/
	if (T != NULL) {
		visit(T);
		preOrder(T->left);
		preOrder(T->right);
	}
}
void postOrder(SegmentTree T) {
    /*后序遍历线段树*/
	if (T != NULL) {
		postOrder(T->left);
		postOrder(T->right);
		visit(T);
	}	
}

Queue initQueue() {
    /*初始化一个空队列*/
	Queue q = (Queue)malloc(sizeof(QNode));
	q->ptr2TNode = NULL;
	q->next = NULL;
	return q;
}

TNode* delete(Queue queue) {
    /*队头元素出队*/
	if (!isEmpty(queue)) {
		QNode* temp = queue->next;
		queue->next = temp->next;		
		TNode* ret = temp->ptr2TNode;
		free(temp);
		return ret;
	}
	return NULL;
}

void add(Queue queue, TNode* Node) {
    /*元素在队尾入队*/
	QNode* temp = queue;
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->ptr2TNode = Node;
	newnode->next = NULL;
	while (temp->next != NULL) {
		temp = temp->next;
	}
	temp->next = newnode;
}
bool isEmpty(Queue queue) {
	/*判断队列是否为空*/
	return queue->next == NULL;
}
void levelOrder(SegmentTree T, Queue queue) {
    /*层序遍历线段树*/
	add(queue, T);
	while (!isEmpty(queue)) {
		TNode* node = delete(queue);
		visit(node);
		if (node->left != NULL) add(queue, node->left);
		if (node->right !=NULL) add(queue, node->right);
	}
}