c++模板编程，搜索二叉树构造

妖狐艹你老母 2022-04-17 01:53 121阅读 0赞

// 树的迭代器  
tree\_iterator.h

//
    // Created by Yongyu Wu on 2018/11/11.
    //
    //树节点的迭代器
    
    
    #ifndef C11TEMPLATE_TREE_ITERATOR_H
    #define C11TEMPLATE_TREE_ITERATOR_H
    #pragma once
    template <typename N>
    class tree_iterator{
        const N *pos; //当前位置
    public:
        typedef typename N::value_type value_type;
        typedef typename N::const_reference_type const_reference_type;
        typedef tree_iterator<N> self_type;
    
        tree_iterator():pos(0){}
        tree_iterator(const N*pos):pos(pos){}
    
        bool operator ==(self_type const &right)const{
            return pos == right.pos;
        }
    
        self_type &operator++(){
            if(pos){
                //首先确保不是空的迭代器，再查看有没有右子树
                if(pos->right){
                    //定位到右子树的最左节点
                    pos=pos->right;
                    while (pos->left)pos=pos->left;
                }else{
                    //定位到尚未访问过的祖先节点
                    while ((pos->parent)&&(pos->parent->right==pos))pos=pos->parent;
                    pos=pos->parent;
                }
            }
            return *this;
    
        }
    
        const_reference_type operator *()const throw(std::runtime_error){
            if(pos)return pos->value;
            else {
                throw  std::runtime_error("dereference null iterator!");
            }
        }
    
    };
    
    template <typename N>
    bool operator !=(tree_iterator<N>const & left,tree_iterator<N> const & right){
        return !(left==right);
    }
    
    
    #endif //C11TEMPLATE_TREE_ITERATOR_H

//
    // Created by Yongyu Wu on 2018/11/11.
    //
    
    #ifndef C11TEMPLATE_SET_H
    #define C11TEMPLATE_SET_H
    
    #pragma once
    
    #include <iostream>
    #include "tree_iterator.h"
    
    //二叉搜索树模板
    template <typename T>
    struct tree_node{
        typedef T value_type;
        typedef T & reference_type;
        typedef const T& const_reference_type;
        T value;
        tree_node * parent;
        tree_node * left;
        tree_node * right;
    
        tree_node(T const & value,tree_node *parent,tree_node*left,tree_node* right):value(value),
        parent(parent),left(left),right(right){}
    
        ~tree_node(){
            if(left) delete  left;
            if (right) delete right;
        }
    
    };
    //集合容器模板
    template <typename T>
    class set{
        typedef tree_node<T> node_type;
        node_type* root;
    public:
        typedef T value_type;
        typedef tree_iterator<node_type> const_iterator;
    
        set():root(){}
        ~set(){if(root)delete root;}
    
        //尝试向集合中插入数据，返回是否成功的插入
        //当集合中已经有该值时，返回false，否则返回true
        bool insert(T const &v){
            node_type **n =&root; //这里root虽然是个指针但是可能是空值,为了给指针赋值，所以取地址
            node_type*p=0;
    
            while(*n){
                if(v==(*n)->value)//集合中已经有该值
                    return false;
                else{
                    p =*n;
                    n=v<(*n)->value?&((*n)->left):&((*n)->right);
    
                }
            }
            *n =new node_type(v,p,0,0);
            return true;
        }
        //查询集合中是否有某值，有时返回true，没有返回=false
        bool has(T const & v){
            node_type*n =root;
            while (n){
                if(v==n->value)
                    return true;
                n= v < n->value ? n->left : n->right;
            }
            return false;
        }
    
        bool is_empty()const{
            return root ==0;
        }
        const_iterator begin()const{
            //定位到最左节点及中序遍历的第一个节点，返回一个指向该节点的遍历器
            node_type*n=root;
            while (n->left)n=n->left;
            return const_iterator(n);
        }
        const_iterator end()const{
    
            return const_iterator();
        }
    
    
    
    };
    
    
    #endif //C11TEMPLATE_SET_H