Algorithms(线段树)

线段树

#ifndef LINETREE_H_INCLUDED
#define LINETREE_H_INCLUDED


typedef struct Node
{
    int i, j;                       // 表示线段树区间[i, j]
    int cover;                      // 表示区间被覆盖的次数
    struct Node *left, *right;      // 左右儿子的节点

}LTree;



/*
** 创建线段树
*/
LTree* create(int i, int j);


/*
** 插入一个区间
*/
void insert(LTree* tree, int i, int j);


/*
** 删除一个区间
*/
void deletee(LTree* tree, int i, int j);


/*
** 输出线段树
*/
void print(LTree* tree, int depth);


/*
** 释放线段树
*/
void destroy(LTree* tree);





#endif // LINETREE_H_INCLUDED

/*--------------------------------------------------------------------------
 * Project: LineTree.cpp
 * Name: zwp
 * Date: 2014/4
 *----------------------------------------------------------------------------*/




 #include 
  
   
 #include 
   
     #include 
    
      #include "LineTree.h" /* ** 创建线段树 */ LTree* create(int i, int j) { if(i > j) return NULL; LTree* pNode = NULL; pNode = (LTree*)malloc(sizeof(LTree)); /* 初始化 */ pNode->i = i; pNode->j = j; pNode->cover = 0; if(j-i > 1) { int mid = i + (j - i)/2; pNode->left = create(i, mid); pNode->right = create(mid, j); } else { pNode->left = pNode->right = NULL; } return pNode; } /* ** 插入一个区间 */ void insert(LTree* tree, int i, int j) { if(i > j) return ; if(i <= tree->i && tree->j <= j) { tree->cover++; // 若小于区间则说明在覆盖区 } else { int mid = tree->i + (tree->j - tree->i)/2; if(j <= mid) { insert(tree->left, i, j); } else if(mid <= i) { insert(tree->right, i, j); } else { insert(tree->left, i, mid); insert(tree->right, mid, j); } } } /* ** 删除一个区间 */ void deletee(LTree* tree, int i, int j) { if(i > j) return; if(i <= tree->i && tree->j <= j) tree->cover--; else { int mid = tree->i + (tree->j - tree->i)/2; if(j <= mid) { deletee(tree->left, i, j); } else if(i >= mid) { deletee(tree->right, i, j); } else { deletee(tree->left, i, mid); deletee(tree->right, mid, j); } } } /* ** 输出线段树 */ void print(LTree* tree, int depth) { if(tree) { int i; for(i = 0; i < depth; ++ i) printf(" "); printf("[%d, %d]:%d\n", tree->i, tree->j, tree->cover); print(tree->left, depth+1); print(tree->right, depth+1); } } /* ** 释放线段树 */ void destroy(LTree* tree) { if(tree) { LTree* pNode = tree; destroy(tree->left); // free left destroy(tree->right); // free right free(pNode); } } 
     
/*---------------------------------------------------------------------
 * Project: Main.cpp
 *Name: zwp
 * Date:2014/5--------------------------------------------------------*/




 #include "LineTree.h"
 #include 
      
       
 #include 
       
         int main(int argc, char* argv[]) { LTree* root = create(1, 10); print(root, 2); insert(root, 3, 6); deletee(root, 3, 5); destroy(root); system("pause"); }