线段树的特点
线段树的优势
线段树的构造过程
线段树的基本数据结构（结点结构由五个分量组成）
运行结果
（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);
}
}