一、树

1、节点的定义

template<class T>
struct Tree_Node {
    T  _val;
    vector<Tree_Node<T>*> _children;

    Node() {}    

    Node(const T& val, const vector<Tree_Node<T>*>& children) {
        _val = val;
        _children = children;
    }
};

2、树的抽象数据结构

template <class T>
class Tree
{
    Tree()
    :_root(NULL)
    {}

    void Clear();      
    Tree_Node<T>* Find(T value);
    bool Add_Node(T parent, T child);
    int size();
    int Height();
    int Leaves();
    bool empty();

private:
    Tree_Node<T> *Find_R(Tree_Node<T>*root, T value);
    int Tree::Height_R(Tree_Node<T>* root);
    int Tree::Size_R(Tree_Node<T>* root);
    int Tree::Leaves_R(Tree_Node<T>* root);
private:
    Tree_Node<T>* _root;
};

3、树的基本操作

3.1、 插入

template <class T>
bool Tree::Add_Node(T parent, T child)
{
    if( _root == NULL )
    {  /*设置为根节点*/
          _root = new Tree_Node(child, NULL);
          return true;
    }
    
    /*寻找值 = parent的节点*/
    Tree_Node* cur = Find(parent);
    Tree_Node* child = new Tree_Node(child, NULL);

    cur->_children.push_back(child);
}

3.2、查询

template <class T>
Tree_Node<T>* Tree::Find( T value )
{
     return Find_R(_root, value);
}

template <class T>
Tree_Node<T>* Tree::Find_R(Tree_Node<T>* root, T value)
{
   if ( root->value == value )
       return root;
   for(auto &child:  root->children)
   {
       Find_R(child, value);
   }
   return NULL;
}

3.3、求树高、节点个数、叶子个数、判断空

template <class T>
int Tree::Height()
{
    Height_R(_root);
}

template <class T>
int Tree::Height_R(Tree_Node<T>* root)
{
    if( root == NULL )
        return 0;
    int height = 0;

    for(auto &child : root -> _children)
    {
        height = max(height, Height_R(child));
    }
    return height + 1;
}

template <class T>
int Tree::Size()
{
    return Size_R(_root);
}

template <class T>
int Tree::Size_R( Tree_Node<T> root )
{
    if( root == NULL )
        return 0;
    int size = 0;
    for( auto &child : root -> _children )
    {
        size += Size_R(child);
    }
    return size + 1;
}

template <class T>
bool Tree::Empty()
{
    if( _root == NULL )
        return true;
    else
        return false;
}

template <class T>
int Tree::Leaves()
{
    return Leaves_R(_root);
}

template <class T>
int Tree::Leaves_R(Tree_Node<T>* root)
{
    if(root == NULL)
        return 0;
    if( root -> _children.size() == 0 )
        return 1;

    int leaves = 0;

    for( auto &child : root -> _children )
    {
        leaves += Leaves_R(child);
    }
}