ACM_二叉树实现板子

发布于 2019-09-02  44 次阅读


二叉树实现:

#pragma comment(linker,"/STACK:1024000000,1024000000")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <experimental/string_view>
#define lodou long double
#define lll __int128
#define INmF 0x3f3f3f3f
#define lbt(x) (x&(-x))
#define mes(a,b) memset(a,b,sizeof(a))
#define qwq(a,b) for(int i=a ;i<=b;++i)
#define qeq(a,b) for(int j=a ;j<=b;++j)
#define IOS ios::sync_with_stdio(false)
#define UPCASE( c ) ( ((c) >= 'c' && (c) <= 'z') ? ((c) - 0x20) : (c) )
#define pb push_back
#define mkp make_pair
using namespace std;
using namespace __gnu_pbds;

using pii=pair<int,int>;
using Balanced_Tree=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
Balanced_Tree seq;

const double Eps = 1e-8 ;
const double pi  = acos(-1) ;
const long long mod = 1e9+7 ;
typedef long long int ll;


inline ll pow_mod (ll a,ll b) {ll res=1;a%=mod; if(b<0) return -1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
inline ll fas_mul (ll a,ll b) { return ( (a*b-(ll)(((long double)a*b+0.5)/mod)*mod)%mod+mod)%mod ; }


namespace io {

    #define in(a) a=read()
    #define out(a) write(a)
    #define outn(a) out(a),putchar('\n')

    #define I_int __int128
    inline I_int read() {
        I_int x = 0 , f = 1 ; char c = getchar() ;
        while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
        while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
        return x * f ;
    }
    char F[ 200 ] ;
    inline void write( I_int x ) {
        if( x == 0 ) { putchar( '0' ) ; return ; }
        I_int tmp = x > 0 ? x : -x ;
        if( x < 0 ) putchar( '-' ) ;
        int cnt = 0 ;
        while( tmp > 0 ) {
            F[ cnt ++ ] = tmp % 10 + '0' ;
            tmp /= 10 ;
        }
        while( cnt > 0 ) putchar ( F[ -- cnt ] ) ;
    }
    #undef I_int

}using namespace io ;

template <class datatype>
struct Treenode
{
    datatype data ;
    Treenode<datatype> *left ;
    Treenode<datatype> *righ ;
    Treenode( const datatype& x ):data(x),left(NULL),righ(NULL)
    {}
};
template <class datatype>
class Binarytree
{
    typedef Treenode<datatype> node ;
    protected :
        node *root ;
    public :
        Binarytree( datatype* x , size_t n , const datatype& inva )
        {
            size_t index=0 ;
            root = creat_tree( x , n , inva , index ) ;
        }
        Binarytree( const Binarytree<datatype> &t )
        {
            root = copy_tree( t.root ) ;
        }~Binarytree()
        {
            destory( root ) ;
            root = NULL ;
        }
        Binarytree<datatype>& operator = ( Binarytree<datatype> t )
        {
            swap( root , t.root ) ;
            return *this ;
        }
        node* copy_tree( node* root )
        {
            if( root==NULL )
                return NULL ;
            node* newroot = new node ( root->data ) ;
            newroot->left = copy_tree( root->left ) ;
            newroot->righ = copy_tree( root->righ ) ;
            return newroot ;
        }
        void destory( node* root )
        {
            if( root==NULL )
                return ;
            destory (root->left );
            destory (root->righ );
        }

        node* creat_tree( datatype* x , size_t n , const datatype& inva , size_t& index )
        {
            node* root=NULL ;
            if( x[index]!=inva ){//puts("here");
                root = new node( x[index] );
                root->left = creat_tree( x , n , inva , ++index ) ;
                root->righ = creat_tree( x , n , inva , ++index ) ;
            }
            return root ;
        }
        void prevorder()
        {
            _prev_order( root ) ;
            puts("") ;
        }
        void _prev_order( node* root )
        {
            if( root==NULL )
                return ;
            cout<<root->data<<" " ;
            _prev_order( root->left ) ;
            _prev_order( root->righ ) ;
        }
        void prev_order_nor()
        {
            node *cur = root ;
            stack<node*> st ;
            while( cur|| !st.empty() )
            {
                while( cur )
                {
                    cout<<cur->data<<" " ;
                    st.push( cur ) ;
                    cur = cur->left ;
                }
                node *top = st.top() ;
                st.pop() ;
                cur = top->righ ;
            }
            puts("");
        }

        void inorder()
        {
            in_order( root ) ;
            puts("") ;
        }
        void in_order(node* root)
        {
            if( root==NULL ) return ;
            in_order( root->left ) ;
            cout<<root->data<<" ";
            in_order( root->righ ) ;
        }
        void in_order_nor()
        {
            node* cur = root ;
            stack<node*> st ;
            while( cur || !st.empty() )
            {
                while( cur )
                {
                    st.push( cur ) ;
                    cur = cur->left ;
                }
                node *top = st.top() ;
                cout<<top->data<<" " ;
                st.pop() ;
                cur = top->righ ;
            }
            puts("");
        }
        void post_order_nor()
        {
            node* cur = root ;
            node* pre = NULL ;
            stack<node*> st ;
            while( cur|| !st.empty() )
            {
                while( cur )
                {
                    st.push( cur ) ;
                    cur = cur->left ;
                }
                node* top = st.top() ;
                if( top->righ ==NULL || top->righ == pre ){
                    cout<<top->data<<" ";
                    st.pop() ;
                    pre = top ;
                }else{
                    cur = top->righ ;
                }
            }
            puts("") ;
        }
        int Sice()
        {
            size_t size=0 ;
            _Sice( root , size ) ;
            return size ;
        }
        void _Sice( node* root , size_t& size )
        {
            if( root==NULL )
                return ;
            _Sice( root->left , size ) ;
            _Sice( root->righ , ++size ) ;
        }
        size_t leaf_size()
        {
            return _leaf_size( root ) ;
        }
        size_t _leaf_size( node* root )
        {
            if( root==NULL ) return 0 ;
            if( root->left==NULL&&root->righ==NULL )
                return 1 ;
            return _leaf_size( root->left) +_leaf_size( root->righ ) ;
        }
        size_t height()
        {
            return _height(root) ;
        }
        size_t _height( node* root )
        {
            if( root==NULL ) return 0 ;
            size_t left_hei = _height( root->left ) ;
            size_t righ_hei = _height( root->righ ) ;
            return left_hei>righ_hei ? left_hei+1 : righ_hei+1 ;
        }
        size_t get_k_lev( size_t k )
        {
            return _get_k_lev( root , k ) ;
        }
        size_t _get_k_lev( node *root , size_t k )
        {
            if( root==NULL ) return 0 ;
            if( k==1 ) return 1 ;
            return  _get_k_lev(root->left,k-1)+_get_k_lev(root->righ,k-1) ;
        }
        void level_order()//bfs
        {
            queue<node*> qu ;
            if( root )
                qu.push(root) ;
            while( !qu.empty() )
            {
                node *front = qu.front() ;
                cout<< front->data <<" " ;
                qu.pop() ;
                if( front->left )
                    qu.push( front->left ) ;
                if( front->righ )
                    qu.push( front->righ ) ;
            }
            puts("") ;
        }
        bool is_cmptree()
        {
            queue<node*> qu ;
            if( root )
                qu.push( root ) ;
            bool flag=true ;
            while( !qu.empty() )
            {
                node* front = qu.front() ;
                qu.pop() ;
                if( front->left ){
                    if( !flag ){
                        return false ;
                    }
                    qu.push( front->left ) ;
                }else{
                    flag = false ;
                }
                if( front->righ ){
                    if( !flag ){
                        return false ;
                    }
                    qu.push( front->righ ) ;
                }else{
                    flag = false ;
                }
            }
            return true ;
        }
        node* find( const datatype& x )
        {
            return _find( root , x ) ;
        }
        node* _find( node* root , const datatype& x )
        {
            if( root==NULL )
                return NULL ;
            if( root->data == x )
                return root ;
            node* ret1 = _find( root->left , x ) ;
            if( ret1 ) 
                return ret1 ;
            node* ret2 = _find( root->righ , x ) ;
            if( ret2 ) 
                return ret2 ;
            return NULL ;
        }
};
signed main(int argc, char const *argv[])
{
    int arr[]={ 1, 2, 3, '#', '#', 4, 40, '#', '#', '#', 5, 6, '#', '#', '#' } ;
    Binarytree<int> t( arr , sizeof(arr)/sizeof(int) , '#' ) ;
    t.prevorder() ;
    t.prev_order_nor() ;
    t.inorder() ;
    t.in_order_nor() ;
    t.post_order_nor() ;
    t.level_order();
    cout << "size:" << t.Sice() << endl;
    cout << "leaf_size:" << t.leaf_size() << endl;
    cout << "height:" << t.height() << endl;
    cout << "is_complete_tree:" << t.is_cmptree() << endl;
    cout << "k_level_size:" << t.get_k_lev(4) << endl;
    
    Binarytree<int> t2(t);
    t2.prev_order_nor();
    return 0;
}

 

喜欢这篇文章吗,不妨分享给朋友们吧!

科学是第一生产力