KMP

#include <bits/stdc++.h>
using namespace std;

void getnext(string s,int next[],int length){    //得到next数组
    int j=0,k=-1;
    next[j]=k;
    while(j<length-1){
        if(k==-1||s[j]==s[k]){
            j++,k++;
            next[j]=k;
        }
        else k=next[k];
    }
}

int kmp__(string s,string t){
    int next[100],i=0,j=0;
    getnext(t,next,t.length());
    while(i<s.length()&&j<t.length()){
        if(j==-1||s[i]==t[j]){
            i++,j++;
        }
        else j=next[j];                  //不匹配，模式串的j向后移，变为next[j]；
    }
    if(j>=t.length()) return i-t.length();   
    //这个等于也行，意思就是j走到了最后一个，表示能找到，然后返回主串匹配的第一个位置
    return -1;
}

int main(){
    string s,t;
    cin>>s>>t;
    cout<<kmp__(s,t);
    return 0;
}

树的构建

#include <bits/stdc++.h>
using namespace std;

struct Node {
    char data;
    Node* lchild, * rchild;
};
using BiTree = Node*; 

void create(BiTree& node) {
    char ch;
    cin >> ch;
    if (ch == '#') // '#' => null character
        node = nullptr;
    else {
        node = new Node;
        node->data = ch;
        create(node->lchild); //递归
        create(node->rchild);
    }
}

void preTraversal(BiTree root) {
    if (root == nullptr) {
        return;
    }
    cout << root->data << " ";
    preTraversal(root->lchild);
    preTraversal(root->rchild);
}

int main(){
    BiTree T;
    create(T);
    preTraversal(T);
    return 0;
}