[算法系列之二]二叉树各种遍历

【简介】

树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。

二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。

二叉树的链式存储结构是一类重要的数据结构，其形式定义如下：

[cpp] view
plaincopy

  1. //二叉树结点  
  2. typedef struct BiTNode{  
  3.     //数据  
  4.     char data;  
  5.     //左右孩子指针  
  6.     struct BiTNode *lchild,*rchild;  
  7. }BiTNode,*BiTree;  

或者

// 二叉树节点结构
struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

【二叉树的创建】

通过读入一个字符串，建立二叉树的算法如下：

[cpp] view
plaincopy

  1. //按先序序列创建二叉树  
  2. int CreateBiTree(BiTree &T){  
  3.     char data;  
  4.     //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树  
  5.     scanf("%c",&data);  
  6.     if(data == '#'){  
  7.         T = NULL;  
  8.     }  
  9.     else{  
  10.         T = (BiTree)malloc(sizeof(BiTNode));  
  11.         //生成根结点  
  12.         T->data = data;  
  13.         //构造左子树  
  14.         CreateBiTree(T->lchild);  
  15.         //构造右子树  
  16.         CreateBiTree(T->rchild);  
  17.     }  
  18.     return 0;  
  19. }  

或者

// 1.创建二叉树
void CreateTree(TreeNode* &root){
    int val;
    //按先序次序输入二叉树中结点的值,‘-1’表示空树
    cin>>val;
    // 空节点
    if(val == -1){
        root = nullptr;
        return;
    }//if
    root = new TreeNode(val);
    //构造左子树
    CreateTree(root->left);
    //构造右子树
    CreateTree(root->right);
}

层次建立二叉树：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 创建二叉树
TreeNode* CreateTreeByLevel(vector<char> num){
    int len = num.size();
    if(len == 0){
        return NULL;
    }//if
    queue<TreeNode*> queue;
    int index = 0;
    // 创建根节点
    TreeNode *root = new TreeNode(num[index++]);
    // 入队列
    queue.push(root);
    TreeNode *p = NULL;
    while(!queue.empty() && index < len){
        // 出队列
        p = queue.front();
        queue.pop();
        // 左节点
        if(index < len && num[index] != -1){
            // 如果不空创建一个节点
            TreeNode *leftNode = new TreeNode(num[index]);
            p->left = leftNode;
            queue.push(leftNode);
        }
        index++;
        // 右节点
        if(index < len && num[index] != -1){
            // 如果不空创建一个节点
            TreeNode *rightNode = new TreeNode(num[index]);
            p->right = rightNode;
            queue.push(rightNode);
        }
        index++;
    }//while
    return root;
}

-1代表NULL

创建如上二叉树输入：

15 11 20 8 14 -1 -1 -1 -1 13 -1

【二叉树的遍历】

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

【递归算法】

[cpp] view
plaincopy

  1. //输出  
  2. void Visit(BiTree T){  
  3.     if(T->data != '#'){  
  4.         printf("%c ",T->data);  
  5.     }  
  6. }  
  7. //先序遍历  
  8. void PreOrder(BiTree T){  
  9.     if(T != NULL){  
  10.         //访问根节点  
  11.         Visit(T);  
  12.         //访问左子结点  
  13.         PreOrder(T->lchild);  
  14.         //访问右子结点  
  15.         PreOrder(T->rchild);  
  16.     }  
  17. }  
  18. //中序遍历  
  19. void InOrder(BiTree T){  
  20.     if(T != NULL){  
  21.         //访问左子结点  
  22.         InOrder(T->lchild);  
  23.         //访问根节点  
  24.         Visit(T);  
  25.         //访问右子结点  
  26.         InOrder(T->rchild);  
  27.     }  
  28. }  
  29. //后序遍历  
  30. void PostOrder(BiTree T){  
  31.     if(T != NULL){  
  32.         //访问左子结点  
  33.         PostOrder(T->lchild);  
  34.         //访问右子结点  
  35.         PostOrder(T->rchild);  
  36.         //访问根节点  
  37.         Visit(T);  
  38.     }  
  39. }  
【非递归算法】
【先序遍历】

【思路】：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。

[cpp] view
plaincopy

  1. /* 先序遍历(非递归) 
  2.    思路：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。 
  3. */  
  4. void PreOrder2(BiTree T){  
  5.     stack<BiTree> stack;  
  6.     //p是遍历指针  
  7.     BiTree p = T;  
  8.     //栈不空或者p不空时循环  
  9.     while(p || !stack.empty()){  
  10.         if(p != NULL){  
  11.             //存入栈中  
  12.             stack.push(p);  
  13.             //访问根节点  
  14.             printf("%c ",p->data);  
  15.             //遍历左子树  
  16.             p = p->lchild;  
  17.         }  
  18.         else{  
  19.             //退栈  
  20.             p = stack.top();  
  21.             stack.pop();  
  22.             //访问右子树  
  23.             p = p->rchild;  
  24.         }  
  25.     }//while  
  26. }  
// 先序遍历
void PreOrder(TreeNode* root){
    if(root == NULL){
        return;
    }
    stack<TreeNode*> stack;
    stack.push(root);
    TreeNode *p = NULL;
    while(!stack.empty()){
        p = stack.top();
        stack.pop();
        cout<<p->val<<endl;
        // 右子节点不空压入栈中
        if(p->right){
            stack.push(p->right);
        }
        // 左子节点不空压入栈中
        if(p->left){
            stack.push(p->left);
        }
    }//while
}
【中序遍历】

【思路】：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
         先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。

[cpp] view
plaincopy

  1. void InOrder2(BiTree T){  
  2.     stack<BiTree> stack;  
  3.     //p是遍历指针  
  4.     BiTree p = T;  
  5.     //栈不空或者p不空时循环  
  6.     while(p || !stack.empty()){  
  7.         if(p != NULL){  
  8.             //存入栈中  
  9.             stack.push(p);  
  10.             //遍历左子树  
  11.             p = p->lchild;  
  12.         }  
  13.         else{  
  14.             //退栈，访问根节点  
  15.             p = stack.top();  
  16.             printf("%c ",p->data);  
  17.             stack.pop();  
  18.             //访问右子树  
  19.             p = p->rchild;  
  20.         }  
  21.     }//while  
  22. }  
【后序遍历】

【思路】：T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。

[cpp] view
plaincopy

  1. //后序遍历(非递归)  
  2. typedef struct BiTNodePost{  
  3.     BiTree biTree;  
  4.     char tag;  
  5. }BiTNodePost,*BiTreePost;  
  6.   
  7. void PostOrder2(BiTree T){  
  8.     stack<BiTreePost> stack;  
  9.     //p是遍历指针  
  10.     BiTree p = T;  
  11.     BiTreePost BT;  
  12.     //栈不空或者p不空时循环  
  13.     while(p != NULL || !stack.empty()){  
  14.         //遍历左子树  
  15.         while(p != NULL){  
  16.             BT = (BiTreePost)malloc(sizeof(BiTNodePost));  
  17.             BT->biTree = p;  
  18.             //访问过左子树  
  19.             BT->tag = 'L';  
  20.             stack.push(BT);  
  21.             p = p->lchild;  
  22.         }  
  23.         //左右子树访问完毕访问根节点  
  24.         while(!stack.empty() && (stack.top())->tag == 'R'){  
  25.             BT = stack.top();  
  26.             //退栈  
  27.             stack.pop();   
  28.             printf("%c ",BT->biTree->data);  
  29.         }  
  30.         //遍历右子树  
  31.         if(!stack.empty()){  
  32.             BT = stack.top();  
  33.             //访问过右子树  
  34.             BT->tag = 'R';  
  35.             p = BT->biTree;  
  36.             p = p->rchild;  
  37.         }  
  38.     }//while  
  39. }  

或者

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> result;
        if(root == nullptr){
            return result;
        }//if
        stack<TreeNode*> s;
        s.push(root);
        TreeNode *node;
        while(!s.empty()){
            node = s.top();
            s.pop();
            result.insert(result.begin(),node->val);
            // 左子树
            if(node->left){
                s.push(node->left);
            }//if
            // 右子树
            if(node->right){
                s.push(node->right);
            }//if
        }//while
        return result;
    }
【层次遍历】

【思路】：按从顶向下，从左至右的顺序来逐层访问每个节点，层次遍历的过程中需要用队列。

[cpp] view
plaincopy

  1. //层次遍历  
  2. void LevelOrder(BiTree T){  
  3.     BiTree p = T;  
  4.     //队列  
  5.     queue<BiTree> queue;  
  6.     //根节点入队  
  7.     queue.push(p);  
  8.     //队列不空循环  
  9.     while(!queue.empty()){  
  10.         //对头元素出队  
  11.         p = queue.front();  
  12.         //访问p指向的结点  
  13.         printf("%c ",p->data);  
  14.         //退出队列  
  15.         queue.pop();  
  16.         //左子树不空，将左子树入队  
  17.         if(p->lchild != NULL){  
  18.             queue.push(p->lchild);  
  19.         }  
  20.         //右子树不空，将右子树入队  
  21.         if(p->rchild != NULL){  
  22.             queue.push(p->rchild);  
  23.         }  
  24.     }  
  25. }  

【测试】

输入：（先序）

15 11 8 -1 -1 14 13 -1 -1 -1 20 -1 -1

输出：

代码一：

    /*-------------------------------------
    *   日期：2015-03-25
    *   作者：SJF0115
    *   题目: 二叉树各种遍历
    *   来源：
    *   博客：
    ------------------------------------*/
    #include <iostream>
    #include <vector>
    #include <stack>
    #include <queue>
    using namespace std;

    // 二叉树节点结构
    struct TreeNode{
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x):val(x),left(nullptr),right(nullptr){}
    };
    // 1.创建二叉树
    void CreateTree(TreeNode* &root){
        int val;
        //按先序次序输入二叉树中结点的值,‘-1’表示空树
        cin>>val;
        // 空节点
        if(val == -1){
            root = nullptr;
            return;
        }//if
        root = new TreeNode(val);
        //构造左子树
        CreateTree(root->left);
        //构造右子树
        CreateTree(root->right);
    }
    // 2.1 递归先序遍历
    void PreOrder(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        result.push_back(root->val);
        // 左子树
        PreOrder(root->left,result);
        // 右子树
        PreOrder(root->right,result);
    }
    // 2.2 非递归先序遍历
    void PreOrder2(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        stack<TreeNode*> s;
        s.push(root);
        TreeNode *node;
        while(!s.empty()){
            node = s.top();
            s.pop();
            result.push_back(node->val);
            // 右子树
            if(node->right){
                s.push(node->right);
            }//if
            // 左子树
            if(node->left){
                s.push(node->left);
            }//if
        }//while
    }
    // 3.1 递归中序遍历
    void InOrder(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        // 左子树
        InOrder(root->left,result);
        result.push_back(root->val);
        // 右子树
        InOrder(root->right,result);
    }
    // 3.2 非递归中序遍历
    void InOrder2(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        stack<TreeNode*> s;
        TreeNode *node = root;
        while(node != nullptr || !s.empty()){
            // 左子树
            if(node != nullptr){
                s.push(node);
                node = node->left;
            }//if
            // 右子树
            else{
                node = s.top();
                s.pop();
                result.push_back(node->val);
                node = node->right;
            }
        }//while
    }
    // 4.1 递归后序遍历
    void PostOrder(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        // 左子树
        PostOrder(root->left,result);
        // 右子树
        PostOrder(root->right,result);
        result.push_back(root->val);
    }
    // 4.2 非递归后序遍历
    void PostOrder2(TreeNode *root,vector<int> &result) {
        if(root == nullptr){
            return;
        }//if
        stack<TreeNode*> s;
        s.push(root);
        TreeNode *node;
        while(!s.empty()){
            node = s.top();
            s.pop();
            result.insert(result.begin(),node->val);
            // 左子树
            if(node->left){
                s.push(node->left);
            }//if
            // 右子树
            if(node->right){
                s.push(node->right);
            }//if
        }//while
    }
    // 5 层次遍历
    void LevelOrder(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        queue<TreeNode*> queue;
        queue.push(root);
        TreeNode *node;
        while(!queue.empty()){
            node = queue.front();
            queue.pop();
            result.push_back(node->val);
            // 左子树
            if(node->left){
                queue.push(node->left);
            }//if
            // 右子树
            if(node->right){
                queue.push(node->right);
            }//if
        }//while
    }
    // 输出结果
    void Print(vector<int> result){
        int size = result.size();
        for(int i = 0;i < size;++i){
            cout<<result[i]<<" ";
        }//for
        cout<<endl;
    }
    int main(){
        freopen("C:\\Users\\Administrator\\Desktop\\c++.txt", "r", stdin);
        TreeNode* root = nullptr;
        vector<int> result;
        // 创建二叉树
        cout<<"1. 创建二叉树"<<endl;
        CreateTree(root);
        cout<<"-----------------------------"<<endl;

        cout<<"2.1 递归先序遍历"<<endl;
        PreOrder(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"2.2 非递归先序遍历"<<endl;
        PreOrder2(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"3.1 递归中序遍历"<<endl;
        InOrder(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"3.2 非递归中序遍历"<<endl;
        InOrder2(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"4.1 递归后序遍历"<<endl;
        PostOrder(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"4.2 非递归后序遍历"<<endl;
        PostOrder2(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"5 层次遍历"<<endl;
        LevelOrder(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;
        return 0;
    }

测试用例：

输入：

ABC##DE#G##F###

输出：

代码二：

[cpp] view
plaincopy

  1. #include<iostream>  
  2. #include<stack>  
  3. #include<queue>  
  4. using namespace std;  
  5.   
  6. //二叉树结点  
  7. typedef struct BiTNode{  
  8.     //数据  
  9.     char data;  
  10.     //左右孩子指针  
  11.     struct BiTNode *lchild,*rchild;  
  12. }BiTNode,*BiTree;  
  13.   
  14. //按先序序列创建二叉树  
  15. int CreateBiTree(BiTree &T){  
  16.     char data;  
  17.     //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树  
  18.     scanf("%c",&data);  
  19.     if(data == '#'){  
  20.         T = NULL;  
  21.     }  
  22.     else{  
  23.         T = (BiTree)malloc(sizeof(BiTNode));  
  24.         //生成根结点  
  25.         T->data = data;  
  26.         //构造左子树  
  27.         CreateBiTree(T->lchild);  
  28.         //构造右子树  
  29.         CreateBiTree(T->rchild);  
  30.     }  
  31.     return 0;  
  32. }  
  33. //输出  
  34. void Visit(BiTree T){  
  35.     if(T->data != '#'){  
  36.         printf("%c ",T->data);  
  37.     }  
  38. }  
  39. //先序遍历  
  40. void PreOrder(BiTree T){  
  41.     if(T != NULL){  
  42.         //访问根节点  
  43.         Visit(T);  
  44.         //访问左子结点  
  45.         PreOrder(T->lchild);  
  46.         //访问右子结点  
  47.         PreOrder(T->rchild);  
  48.     }  
  49. }  
  50. //中序遍历    
  51. void InOrder(BiTree T){    
  52.     if(T != NULL){    
  53.         //访问左子结点    
  54.         InOrder(T->lchild);    
  55.         //访问根节点    
  56.         Visit(T);    
  57.         //访问右子结点    
  58.         InOrder(T->rchild);    
  59.     }    
  60. }    
  61. //后序遍历  
  62. void PostOrder(BiTree T){  
  63.     if(T != NULL){  
  64.         //访问左子结点  
  65.         PostOrder(T->lchild);  
  66.         //访问右子结点  
  67.         PostOrder(T->rchild);  
  68.         //访问根节点  
  69.         Visit(T);  
  70.     }  
  71. }  
  72. /* 先序遍历(非递归) 
  73.    思路：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。 
  74. */  
  75. void PreOrder2(BiTree T){  
  76.     stack<BiTree> stack;  
  77.     //p是遍历指针  
  78.     BiTree p = T;  
  79.     //栈不空或者p不空时循环  
  80.     while(p || !stack.empty()){  
  81.         if(p != NULL){  
  82.             //存入栈中  
  83.             stack.push(p);  
  84.             //访问根节点  
  85.             printf("%c ",p->data);  
  86.             //遍历左子树  
  87.             p = p->lchild;  
  88.         }  
  89.         else{  
  90.             //退栈  
  91.             p = stack.top();  
  92.             stack.pop();  
  93.             //访问右子树  
  94.             p = p->rchild;  
  95.         }  
  96.     }//while  
  97. }  
  98. /* 中序遍历(非递归) 
  99.    思路：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。 
  100.          先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。 
  101. */  
  102. void InOrder2(BiTree T){  
  103.     stack<BiTree> stack;  
  104.     //p是遍历指针  
  105.     BiTree p = T;  
  106.     //栈不空或者p不空时循环  
  107.     while(p || !stack.empty()){  
  108.         if(p != NULL){  
  109.             //存入栈中  
  110.             stack.push(p);  
  111.             //遍历左子树  
  112.             p = p->lchild;  
  113.         }  
  114.         else{  
  115.             //退栈，访问根节点  
  116.             p = stack.top();  
  117.             printf("%c ",p->data);  
  118.             stack.pop();  
  119.             //访问右子树  
  120.             p = p->rchild;  
  121.         }  
  122.     }//while  
  123. }  
  124.   
  125. //后序遍历(非递归)  
  126. typedef struct BiTNodePost{  
  127.     BiTree biTree;  
  128.     char tag;  
  129. }BiTNodePost,*BiTreePost;  
  130.   
  131. void PostOrder2(BiTree T){  
  132.     stack<BiTreePost> stack;  
  133.     //p是遍历指针  
  134.     BiTree p = T;  
  135.     BiTreePost BT;  
  136.     //栈不空或者p不空时循环  
  137.     while(p != NULL || !stack.empty()){  
  138.         //遍历左子树  
  139.         while(p != NULL){  
  140.             BT = (BiTreePost)malloc(sizeof(BiTNodePost));  
  141.             BT->biTree = p;  
  142.             //访问过左子树  
  143.             BT->tag = 'L';  
  144.             stack.push(BT);  
  145.             p = p->lchild;  
  146.         }  
  147.         //左右子树访问完毕访问根节点  
  148.         while(!stack.empty() && (stack.top())->tag == 'R'){  
  149.             BT = stack.top();  
  150.             //退栈  
  151.             stack.pop();  
  152.             BT->biTree;  
  153.             printf("%c ",BT->biTree->data);  
  154.         }  
  155.         //遍历右子树  
  156.         if(!stack.empty()){  
  157.             BT = stack.top();  
  158.             //访问过右子树  
  159.             BT->tag = 'R';  
  160.             p = BT->biTree;  
  161.             p = p->rchild;  
  162.         }  
  163.     }//while  
  164. }  
  165. //层次遍历  
  166. void LevelOrder(BiTree T){  
  167.     BiTree p = T;  
  168.     //队列  
  169.     queue<BiTree> queue;  
  170.     //根节点入队  
  171.     queue.push(p);  
  172.     //队列不空循环  
  173.     while(!queue.empty()){  
  174.         //对头元素出队  
  175.         p = queue.front();  
  176.         //访问p指向的结点  
  177.         printf("%c ",p->data);  
  178.         //退出队列  
  179.         queue.pop();  
  180.         //左子树不空，将左子树入队  
  181.         if(p->lchild != NULL){  
  182.             queue.push(p->lchild);  
  183.         }  
  184.         //右子树不空，将右子树入队  
  185.         if(p->rchild != NULL){  
  186.             queue.push(p->rchild);  
  187.         }  
  188.     }  
  189. }  
  190. int main()  
  191. {  
  192.     BiTree T;  
  193.     CreateBiTree(T);  
  194.     printf("先序遍历：\n");  
  195.     PreOrder(T);  
  196.     printf("\n");  
  197.     printf("先序遍历(非递归)：\n");  
  198.     PreOrder2(T);  
  199.     printf("\n");  
  200.     printf("中序遍历：\n");  
  201.     InOrder(T);  
  202.     printf("\n");  
  203.     printf("中序遍历(非递归)：\n");  
  204.     InOrder2(T);  
  205.     printf("\n");  
  206.     printf("后序遍历：\n");  
  207.     PostOrder(T);  
  208.     printf("\n");  
  209.     printf("后序遍历(非递归)：\n");  
  210.     PostOrder2(T);  
  211.     printf("\n");  
  212.     printf("层次遍历：\n");  
  213.     LevelOrder(T);  
  214.     printf("\n");  
  215.     return 0;  
  216. }  
时间： 2024-10-28 21:08:34

[算法系列之二]二叉树各种遍历的相关文章

[算法系列之二十四]后缀树（Suffix Tree）

之前有篇文章([算法系列之二十]字典树(Trie))我们详细的介绍了字典树.有了这些基础我们就能更好的理解后缀树了. 一 引言 模式匹配问题 给定一个文本text[0-n-1], 和一个模式串 pattern[0-m-1],写一个函数 search(char pattern[], char text[]), 打印出pattern在text中出现的所有位置(n > m). 这个问题已经有两个经典的算法:KMP算法 ,有限自动机,前者是对模式串pattern做预处理,后者是对待查证文本text做预处

[算法系列之二十三]线段树（Interval Tree）

一 背景 在信息学竞赛中,我们经常会碰到一些跟区间有关的问题,比如给一些区 间线段求并区间的长度,或者并区间的个数等等.这些问题的描述都非常简单,但是通常情况下数据范围会非常大,而朴素方法的时间复杂度过高,导致不能在规定时间内得到问题的解.这时,我们需要一种高效的数据结构来处理这样的问题,在本文中,我们介绍一种基于分治思想的数据结构--线段树. 二 简介 线段树是一种二叉树形结构,属于平衡树的一种.它将线段区间组织成树形的结构,并用每个节点来表示一条线段.一棵[1,10)的线段树的结构如图1.1

[算法系列之二十]字典树（Trie）

一 概述 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种.典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计. 二 优点 利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希表高. 三 性质 (1)根节点不包含字符,除根节点外每一个节点都只包含一个字符: (2)从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串: (3)每个节点的所有子节点包含的字符都不相同. 单词列表为"apps&

算法系列（二十） 计算中国农历（二）

所谓的"天文算法",就是利用经典力学定律推导行星运转轨道,对任意时刻的行星位置进行精确计 算,从而获得某种天文现象发生时的时间,比如日月合朔这一天文现象就是太阳和月亮的地心黄经(视黄 经)差为0的那一瞬间.能够计算任意时刻行星位置的一套理论就被称为星历表,比较著名的星历表有美 国国家航空航天局下属的喷气推进实验室发布的DE系列星历表,还有瑞士天文台在DE406基础上拓展的瑞 士星历表等等.根据行星运行轨道直接计算行星位置通常不是很方便,更何况大多数民用天文计算用不上 那么多精确的轨道参

[算法系列之二十六]字符串匹配之KMP算法

一 简介 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特-莫里斯-普拉特操作(简称KMP算法).KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的. 二 基于部分匹配表的KMP算法 举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含搜索串"ABCDABD"? 步骤1:字符串"BBC ABC

[算法系列之二十二]包含T全部元素的最小子窗口

题目描述 给定一个包含一系列字符的集合T和字符串S,请在字符串S中找到一个最小的窗口,这个窗口中必须包含T中的所有字符. 例如, S = "ADOBECODEBANC" T = "ABC" 最小窗口是"BANC" 分析 这是一个有趣的问题,这个有趣的问题有多种方法来解决,最好的方法是非常简单,美丽的. 在这篇文章中,我首先说明了一个方法,是我第一次遇见这个问题时想到的.我的第一个方法有点复杂,同时也不是最好的解决方案(时间复杂度为O(NlgM))

[算法系列之二十一]最短摘要的生成

题目描述 你我在百度或谷歌搜索框中敲入本博客名称的前4个字"结构之法",便能在第一个选项看到本博客的链接,如下图2所示: 图2 谷歌中搜索关键字"结构之法" 在上面所示的图2中,搜索结果"结构之法算法之道-博客频道-CSDN.NET"下有一段说明性的文字:"程序员面试.算法研究.编程艺术.红黑树4大经典原创系列集锦与总结 作者:July–结构之法算法-",我们把这段文字称为那个搜索结果的摘要,亦即最短摘要.我们的问题是,请问,

算法系列（二十） 计算中国农历（一）

世界各国的日历都是以天为最小单位,但是关于年和月的算法却各不相同,大致可以分为三类: 阳历--以天文年作为日历的主要周期,例如:中国公历(格里历) 阴历--以天文月作为日 历的主要周期,例如:伊斯兰历 阴阳历--以天文年和天文月作为日历的主要周期,例如:中国农 历 我国古人很早就开始关注天象,定昼夜交替为"日",月轮盈亏为"月",寒暑交替为"年" ,在总结日月变化规律的基础上制定了兼有阴历月和阳历年性质的历法,称为中国农历.本文将介绍中国 农历的

[算法系列之二十八]并查集（不相交集合）

一 概述 并查集(Disjoint set或者Union-find set)是一种树型的数据结构,常用于处理一些不相交集合(Disjoint Sets)的合并及查询问题. 有一个联合-查找算法(union-find algorithm)定义了两个操作用于此数据结构: Find:确定元素属于哪一个子集.它可以被用来确定两个元素是否属于同一子集. Union:将两个子集合并成同一个集合. 因为它支持这两种操作,一个不相交集也常被称为联合-查找数据结构(union-find data structur