BST

二叉树

template<typename T>
struct BiTNode{
    BiTNode(){}
    T val;
    BiTNode *left,*right;
};

using node=BiTNode<int>;


void build(node* &root){
    int val;cin>>val;
    if(val==-1){root=NULL;return;}
    root=new node;root->val=val;
    build(root->left);build(root->right);
}
int leaf(node *Tree)
{
    if(Tree==NULL)return 0;
    if(Tree->left==NULL && Tree->right==NULL)return 1;
    return leaf(Tree->left)+leaf(Tree->right);
}
int depth(node *root,int p)
{
    if(root=NULL)return p;
    return max(depth(root->left,p+1),depth(root->right,p+1));
}
void dfs_pre(node *Tree)
{
    if(Tree==NULL){return ;}
    printf("%d ",Tree->val);
    dfs_pre(Tree->left);
    dfs_pre(Tree->right);
}
void dfs_mid(node *Tree){
    if(Tree==NULL)return;
    dfs_mid(Tree->left);
    printf("%d ",Tree->val);
    dfs_mid(Tree->right);
}
void dfs_rear(node *Tree)
{
    if(Tree==NULL){return ;}
    dfs_rear(Tree->left);
    dfs_rear(Tree->right);
    printf("%d ",Tree->val);
}
void bfs_pre(node *Tree)
{
    stack<node*>Stack;
    node *p=Tree;
    while(p!=NULL||!Stack.empty())
    {
        if(p)
        {
            printf("%d ",p->val);
            Stack.push(p);
            p=p->left;
        }
        else 
        {
            p=Stack.top();
            Stack.pop();
            p=p->right;
        }
    }
}

void bfs_mid(node *Tree)
{
    stack<node*>Stack;
    node *p=Tree;
    while(p!=NULL||!Stack.empty())
    {
        if(p)
        {
            Stack.push(p);
            p=p->left;
        }
        else 
        {
            p=Stack.top();
            Stack.pop();
            printf("%d ",p->val);
            p=p->right;
        }
    }
}
void bfs_rear(node *Tree)
{
    stack<node*>Stack;
    Stack.push(Tree);
    node *pre,*cur;
    cur=pre=NULL;
    while(!Stack.empty())
    {
        cur=Stack.top();
        if((cur->left == NULL && cur->right == NULL) \
        || (pre != NULL && (pre == cur->left || pre == cur->right)))
        {
            printf("%d ",cur->val);
            cur=Stack.top();
            Stack.pop();
            pre=cur;
        }
        else 
        {
            if(cur->right!=NULL)Stack.push(cur->right);
            if(cur->left!=NULL)Stack.push(cur->left);
        }
    }
}

BST

template<typename T>
struct BiTNode{
    BiTNode(){left=NULL,right=BULL;}
    T val;
    BiTNode *left,*right;
};

using node=BiTNode<int>;
node* insert(node* root,int key){
    if(root==NULL){
        root=new node();
        root->val=key;
        return root;
    }
    if(key<root->val)root->left=insert(root->left,key);
    else root->right=insert(root->right,key);
    return root;
}
node* find(node* root,int key){
    if(root==NULL)return NULL;
    if(key==root->val)return root;
    if(key>root->val)return find(root->right,key);
    return find(root->left,key);
}
node* erase(node* root, int key) {
    if(root==NULL)return NULL;
    if(key<root->val)root->left=erase(root->left,key);
    else if(key>root->val)root->right=erase(root->right,key);
    else if(root->val==key){
        if(root->left&&root->right){
            node *p=root->left;
            while(p->right)p=p->right;
            root->val=p->val;
            root->left=erase(root->left,p->val);
        }else{
            node *p=root->left?root->left:root->right;
            delete root;return p;
        }
    }
    return root;
}