这是浙江大学《数据结构》刷题记录的第二篇，越发觉得编程是一件很有意思的事情。而且对于EE/CS/AI专业的学生，多刷算法题和数据结构题真的对于无论找工还是培养工程代码能力都大有裨益。下面就具体论述下这次的五道数据结构题目。

二分查找

链接：https://pintia.cn/problem-sets/1497448825169559552/problems/1497448917745405953
这题就是最最原始的二分查找，之后刷很多算法题都有可能用到这个算法，因为其复杂度只有CS专题——浙大数据结构刷题（二） - 图1。但是要注意的一点是，二分查找需要数组或者序列是排好序的有序数列。
代码如下：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. #define MAXSIZE 10
  5. #define NotFound 0
  6. typedef int ElementType;
  8. typedef int Position;
  9. typedef struct LNode *List;
  10. struct LNode {
  11.     ElementType Data[MAXSIZE];
  12.     Position Last; /* 保存线性表中最后一个元素的位置 */
  13. };
  15. List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */
  16. Position BinarySearch( List L, ElementType X );
  18. int main()
  19. {
  20.     List L;
  21.     ElementType X;
  22.     Position P;
  24.     L = ReadInput();
  25.     scanf("%d", &X);
  26.     P = BinarySearch( L, X );
  27.     printf("%d\n", P);
  29.     return 0;
  30. }
  32. /* 你的代码将被嵌在这里 */
  33. Position BinarySearch( List L, ElementType X ){
  34.     Position end = L->Last;
  35.     Position start = 1;
  36.     Position temp;
  37.     Position i = NotFound;
  38.     while(1){
  39.         if(end==start){
  40.             if(X==L->Data[end])
  41.                 return end;
  42.             else
  43.                 break;
  44.         }
  45.         if((end-start+1)%2==0){
  46.             temp = (end-start+1)/2 + start - 1;
  47.             if(X==L->Data[temp])
  48.                 return temp;
  49.             else if(X==L->Data[temp+1])
  50.                 return temp+1;
  51.             else if(X<L->Data[temp])
  52.                 end = temp;
  53.             else
  54.                 start = temp + 1;
  55.         }
  56.         else{
  57.             temp = (start+end)/2;
  58.             if(X==L->Data[temp])
  59.                 return temp;
  60.             else if(X<L->Data[temp])
  61.                 end = temp - 1;
  62.             else
  63.                 start = temp + 1;
  64.         }
  65.     }
  66.     return i;
  67. }

树的同构问题

链接：https://pintia.cn/problem-sets/1497448825169559552/problems/1503334324290916352
其实在解决树的很多问题我们都需要用到一个很重要的性质——那就是树的递归效应，即树的子树仍旧是一棵树，所以在树的许多算法中也会用到递归的算法，在程序中经常体现为函数的递归调用，当然在递归时要经常考虑是否还能继续递归，即还有没有左节点或者右节点（节点可能为空，那就不需要继续递归了）。
代码如下：

  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstdio>
  4. #define Maxsize 10
  6. using namespace std;
  8. class Node{
  9.     public:
  10.     char value;
  11.     int left;
  12.     int right;
  13.     Node(){
  14.         value = 'a';
  15.         left = -1;
  16.         right = -1;
  17.     }
  18. };
  20. Node tree[Maxsize];
  21. int check[Maxsize] = {0};
  22. Node tree2[Maxsize];
  23. int check2[Maxsize] = {0};
  24. void Issame(int root,int root2);
  25. int Isthesame = 1;
  27. int main(){
  28.     int N,root;
  29.     char tempchar;
  30.     //读入数据并建树1
  31.     cin>>N;
  32.     for(int i = 0;i < N;i++){
  33.         cin >> tree[i].value;
  34.         cin >> tempchar;
  35.         if(tempchar != '-'){
  36.             tree[i].left = int(tempchar) - 48;
  37.             check[(int(tempchar) - 48)] = 1;
  38.         }
  39.         else
  40.             tree[i].left = -1;
  41.         cin >> tempchar;
  42.         if(tempchar != '-'){
  43.             tree[i].right = int(tempchar) - 48;
  44.             check[(int(tempchar) - 48)] = 1;
  45.         }
  46.         else
  47.             tree[i].right = -1;
  48.     }
  49.     //寻找根节点
  50.     for(int i = 0;i < N;i++)
  51.     {
  52.         if(check[i] == 0){
  53.             root = i;
  54.             break;
  55.         }
  56.     }
  57.     //for(int i = 0;i < N;i++)
  58.     //    cout<<tree[i].value<<" "<<tree[i].left<<" "<<tree[i].right<<endl;
  60.     //读入数据并建树2
  61.     int N2,root2;
  62.     cin>>N2;
  63.     for(int i = 0;i < N2;i++){
  64.         cin >> tree2[i].value;
  65.         cin >> tempchar;
  66.         if(tempchar != '-'){
  67.             tree2[i].left = int(tempchar) - 48;
  68.             check2[(int(tempchar) - 48)] = 1;
  69.         }
  70.         else
  71.             tree2[i].left = -1;
  72.         cin >> tempchar;
  73.         if(tempchar != '-'){
  74.             tree2[i].right = int(tempchar) - 48;
  75.             check2[(int(tempchar) - 48)] = 1;
  76.         }
  77.         else
  78.             tree2[i].right = -1;
  79.     }
  80.     for(int i = 0;i < N2;i++)
  81.     {
  82.         if(check2[i] == 0){
  83.             root2 = i;
  84.             break;
  85.         }
  86.     }
  87.     //for(int i = 0;i < N2;i++)
  88.     //    cout<<tree2[i].value<<" "<<tree2[i].left<<" "<<tree2[i].right<<endl;
  89.     //cout<<root<<endl;
  90.     //cout<<root2<<endl;
  92.     //判断两棵树是否同构
  93.     if((N == 0 && N2 != 0)||(N != 0 && N2 == 0)){
  94.         cout<<"No"<<endl;
  95.         return 0;
  96.     }
  97.     else if(N == 0 && N2 == 0){
  98.         cout<<"Yes"<<endl;
  99.         return 0;
  100.     }
  101.     else
  102.         Issame(root,root2);
  103.     if(Isthesame == 1)
  104.         cout<<"Yes"<<endl;
  105.     else
  106.         cout<<"No"<<endl;
  107.     return 0;
  108. }
  110. void Issame(int root,int root2){
  111.     //cout<<"1"<<endl;
  112.     //考虑不同情况，采用递归的方法
  113.     if(Isthesame == 0)
  114.         return;
  115.     if(tree[root].value != tree2[root2].value){
  116.         Isthesame = 0;
  117.         return;
  118.     }
  119.     else if((tree[root].left + tree[root].right == -2)&&(tree2[root2].left + tree2[root2].right == -2)){
  120.         return;
  121.     }
  122.     else if((tree[root].left >= 0 && tree[root].right == -1)&&(tree2[root2].left >= 0 && tree2[root2].right == -1)){
  123.         Issame(tree[root].left,tree2[root2].left);
  124.     }
  125.     else if((tree[root].left >= 0 && tree[root].right == -1)&&(tree2[root2].left == -1 && tree2[root2].right >= 0)){
  126.         Issame(tree[root].left,tree2[root2].right);
  127.     }
  128.     else if((tree[root].left == -1 && tree[root].right >= 0)&&(tree2[root2].left >= 0 && tree2[root2].right == -1)){
  129.         Issame(tree[root].right,tree2[root2].left);
  130.     }
  131.     else if((tree[root].left == -1 && tree[root].right >= 0)&&(tree2[root2].left == -1 && tree2[root2].right >= 0)){
  132.         Issame(tree[root].right,tree2[root2].right);
  133.     }
  134.     else{
  135.         if(tree[tree[root].left].value == tree2[tree2[root2].left].value){
  136.             Issame(tree[root].left,tree2[root2].left);
  137.             if(Isthesame != 0)
  138.                 Issame(tree[root].right,tree2[root2].right);
  139.         }
  140.         else{
  141.             Issame(tree[root].left,tree2[root2].right);
  142.             if(Isthesame != 0)
  143.                 Issame(tree[root].right,tree2[root2].left);
  144.         }
  145.     }
  146. }

List Leaves问题

链接：https://pintia.cn/problem-sets/1497448825169559552/problems/1503334324290916353
这题本质上就是使用层序遍历+判断叶节点，从而将叶节点一个个的输出。当谈到层序遍历时，我们需要使用队列queue来实现层序遍历，这里我使用了两个堆栈来代替队列执行一样的功能。
代码如下：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<vector>
#define Maxsize 10

using namespace std;

class Node{
    public:
    int left;
    int right;
    Node(){
        left = -1;
        right = -1;
    }
};

Node tree[Maxsize];
int check[Maxsize] = {0};
int count = 0;

int main(){
    int N,root;
    char tempchar;
    //读入数据并建树1
    cin>>N;
    for(int i = 0;i < N;i++){
        cin >> tempchar;
        if(tempchar != '-'){
            tree[i].left = int(tempchar) - 48;
            check[(int(tempchar) - 48)] = 1;
        }
        else
            tree[i].left = -1;
        cin >> tempchar;
        if(tempchar != '-'){
            tree[i].right = int(tempchar) - 48;
            check[(int(tempchar) - 48)] = 1;
        }
        else
            tree[i].right = -1;
    }
    //寻找根节点
    for(int i = 0;i < N;i++)
    {
        if(check[i] == 0){
            root = i;
            break;
        }
    }
    //for(int i = 0;i < N;i++)
    //    cout<<i<<" "<<tree[i].left<<" "<<tree[i].right<<endl;
    //cout<<root<<endl;
    vector<int> stack1,stack2;
    int tempindex;
    //cout<<root;
    if(N == 0)
        return 0;
    else if(N == 1){
        cout<<root;
        return 0;
    }
    while(true){
        //pop阶段
        //下面使用两个stack来完成一个queue的功能
        if(stack1.size() != 0){
            auto begin = stack1.begin();
            auto end = stack1.end();
            while(end != begin){
                stack2.push_back(*(end-1));
                --end;
            }
            stack1.clear();
            tempindex = stack2.back();
            if(tree[tempindex].left == -1 && tree[tempindex].right == -1){
                if(count != 0){
                    cout<<" ";
                }
                cout<<tempindex;
                count++;
            }
            stack2.pop_back();
        }
        else{
            tempindex = root;
        }

        //push阶段
        if(stack2.size() != 0){
            auto begin2 = stack2.begin();
            auto end2 = stack2.end();
            while(end2 != begin2){
                stack1.push_back(*(end2-1));
                --end2;
            }
            stack2.clear();
        }

        if(tree[tempindex].left != -1){
            stack1.push_back(tree[tempindex].left);
            //cout<<tree[tempindex].left;
        }
        if(tree[tempindex].right != -1){
            stack1.push_back(tree[tempindex].right);
            //cout<<tree[tempindex].right;
        }

        //判断是否全部pop出
        if(stack1.size() == 0)
            break;
    }
    return 0;
}

Tree Traversals Again

链接：https://pintia.cn/problem-sets/1497448825169559552/problems/1503334324290916354
好难，研究ing。。
代码如下：

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#define Maxsize 30

using namespace std;

class Node{
    public:
    int lastnode;
    int leftnode;
    int rightnode;
    int flag;
    Node(){
        leftnode = -1;
        rightnode = -1;
        flag = 0;
    }
};

Node array[Maxsize];

void Postorder(int index);

int main(){
    string No;
    int N;
    int count;
    count = 0;
    getline(cin, No, '\n');
    N = stoi(No);
    string temp,temp2;
    int num,root;
    int nowindex = 0;
    //根据operations of stack建树
    for(int p = 0;p < 2*N;p++){
        getline(cin, temp, '\n');
        if(array[root].flag == 1 && array[root].leftnode != -1 && array[root].rightnode != -1)
            goto f;
        //cout<<temp<<endl;
        //根节点及根节点左边
        if(p == 0){
            num = (int)(temp.back()) - 48;
            //cout<<num<<endl;
            root = num;
            count++;
            nowindex = num;
            array[nowindex].lastnode = -1;
            //cout<<"PUSH"<<endl;
        }
        else{
            if(temp.length() > 3){
                //cout<<"PUSH"<<endl;
                num = (int)(temp.back()) - 48;
                //cout<<num<<endl;
                if(array[nowindex].leftnode == -1 && array[nowindex].flag == 0)
                    array[nowindex].leftnode = num;
                else
                    array[nowindex].rightnode = num;
                array[num].lastnode = nowindex;
                nowindex = num;
                count++;
            }
            else{
                //cout<<"POP"<<endl;
                if(array[nowindex].leftnode == -1){
                    array[nowindex].flag = 1;
                    nowindex = array[nowindex].lastnode;
                    while(array[nowindex].flag == 1)
                        nowindex = array[nowindex].lastnode;

                }
                else{
                    array[nowindex].flag = 1;
                }
            }
        }
        continue;
        //根节点右边
        f:if(temp.length() > 3){
            num = (int)(temp.back()) - 48;
            //cout<<num<<endl;
            if(array[nowindex].leftnode == -1 && array[nowindex].flag == 0)
                array[nowindex].leftnode = num;
            else
                array[nowindex].rightnode = num;
            array[num].lastnode = nowindex;
            nowindex = num;
            count++;
        }
        else{

        }
        //cin>>temp;

        //for(int i = 0;i < count; i++)
        //    cout<<array[i].lastnode<<" "<<array[i].leftnode<<" "<<array[i].rightnode<<" "<<array[i].flag<<endl;
        //cout<<endl;
    }
    //for(int i = 0;i < count; i++)
    //    cout<<array[i].lastnode<<" "<<array[i].leftnode<<" "<<array[i].rightnode<<" "<<array[i].flag<<endl;

    //根据树进行后序遍历并输出
    Postorder(root);
    return 0;
}

int counts = 0;

void Postorder(int index){
    if(array[index].leftnode != -1)
        Postorder(array[index].leftnode);
    if(array[index].rightnode != -1)
        Postorder(array[index].rightnode);
    if(counts == 0){
        cout<<index;
        counts++;
    }
    else{
        cout<<" "<<index;
    }
}

同一棵二叉搜索树

链接：https://pintia.cn/problem-sets/1497448825169559552/problems/1505905647748263937
这题也是花了40分钟左右就AC的一道题，真的不难，还是利用到上面所说的“树的递归效应”将树根据根节点一分为二，然后将同样的操作作用于子树，递归判断子树，子树的子树等等。
代码如下：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#define Maxsize 10

using namespace std;

int flag = 1;
void Compare(int* a, int* b, int length1, int length2);

int main(){
    int N,L;
    int temps,tempnum;
    int arr_o[Maxsize];
    int arr_c[Maxsize];
    while(true){
        cin>>N;
        if(N == 0)
            return 0;
        cin>>L;
        //建立原始序列
        for(int i = 0;i < N;i++){
            cin >> tempnum;
            arr_o[i] = tempnum;
        }
        //读入与原始序列比较的L个序列
        for(int p = 0;p < L;p++){
            for(int i = 0;i < N;i++){
                cin >> temps;
                arr_c[i] = temps;
                if(temps == 0)
                    return 0;
            }
            flag = 1;
            //将两个序列进行比较
            Compare(arr_o,arr_c,N,N);
            if(flag == 0)
                cout<<"No"<<endl;
            else
                cout<<"Yes"<<endl;
        }
    }
    return 0;
}

void Compare(int* a, int* b, int length1, int length2){
    if(flag == 0)
        return;
    //长度不等直接返回No
    if(length1 != length2){
        //cout<<"a"<<endl;
        flag = 0;
        return;
    }
    //序列都为空直接返回
    if(length1 == 0 && length2 == 0){
        return;
    }
    else if(length1 <= 2){
        for(int i = 0;i < length1;i++){
            //根节点不一样直接No
            if(a[i] != b[i]){
                //cout<<"b"<<endl;
                flag = 0;
                return;
            }
        }
        return;
    }
    else{
        //如果根节点一样就直接比较根节点两边（大于和小于）的子序列，递归比较
        int tempa[Maxsize],tempb[Maxsize],tempa_2[Maxsize],tempb_2[Maxsize];
        int templen1,templen2,templen1_2,templen2_2;
        templen1 = templen2 = templen1_2 = templen2_2 = 0;
        for(int i = 0;i < length1;i++){
            if(i == 0){
                if(a[0] != b[0]){
                    //cout<<"c"<<endl;
                    flag = 0;
                    return;
                }
            }
            else{
                if(a[i] > a[0])
                    tempa_2[templen1_2++] = a[i];
                else
                    tempa[templen1++] = a[i];
                if(b[i] > b[0])
                    tempb_2[templen2_2++] = b[i];
                else
                    tempb[templen2++] = b[i];
            }
        }
        //递归比较左右子序列
        Compare(tempa,tempb,templen1,templen2);
        Compare(tempa_2,tempb_2,templen1_2,templen2_2);
        return;
    }
}

总结

从这次的五道题中，我又有新的收获，就是：1）关于代码的调试，可以多采用cout来观察想观察的变量来判断程序地bug在哪个地方；2）抓住问题的本质，多总结归纳，比如说树的递归效应，这在很多树的相关问题中都有用到；3）注释一定要及时补充好，不然真的过段时间非常容易忘记；4）写代码的时候多注意边界测试，比如i=0或者1，或者某个指针为空的情况等等。
欢迎对ECE/CS/AI感兴趣的小伙伴关注我，如果你对我的内容有什么建议的话，或者你也对算法和数据结构感兴趣的话，可以单独找我讨论，也欢迎在评论区留下你的声音。