C++树的实现
STL里面没有提供容器树的模板实现，从网上找到一个：
 
Tree.h
//tree.h 头文件
 
#include < list >
#include <algorithm>
using namespace std;
 
struct TreeNode ; // 定义一个结构体原形
class Tree ;      // 定义一个类原形
class Iterator ;  // 定义一个类原形
typedef list < TreeNode *> List ; // 重命名一个节点链表
 
TreeNode * clone ( TreeNode *, List &, TreeNode *); //Clone 复制函数
 
struct TreeNode {
   int _data ;                  // 数据
   TreeNode * _parent ;          // 父节点
   List _children ;             // 子节点
   TreeNode ( int , TreeNode *);    // 构造函数
   void SetParent ( TreeNode &);  // 设置父节点
   void InsertChildren ( TreeNode &); // 插入子节点
};
 
class Tree {
public:
 
  // 下面是构造器和运算符重载
   Tree ();                            // 默认构造函数
   Tree ( const Tree &);                 // 复制构造函数
   Tree ( const int );                   // 带参数构造函数
   Tree ( const int , const list < Tree *>&); // 带参数构造函数
   ~ Tree ();                           // 析构函数
   Tree & operator=( const Tree &);      //= 符号运算符重载
   bool operator==( const Tree &);      //== 符号运算符重载
   bool operator!=( const Tree &);      //!= 符号运算符重载
 
   // 下面是成员函数
   void Clear ();                      // 清空
   bool IsEmpty () const ;               // 判断是否为空
   int Size () const ;                   // 计算节点数目
   int Leaves ();                      // 计算叶子数
   int Root () const ;                   // 返回根元素
   int Height ();                      // 计算树的高度
 
 
   // 下面是静态成员函数
  static bool IsRoot ( Iterator );     // 判断是否是根
   static bool isLeaf ( Iterator );     // 判断是否是叶子
   static Iterator Parent ( Iterator ); // 返回其父节点
   static int NumChildren ( Iterator ); // 返回其子节点数目
 
   // 跌代器函数
   Iterator begin ();                  //Tree Begin
   Iterator end ();                    //Tree End
   friend class Iterator ;             //Iterator SubClass
private :
   list < TreeNode *> _nodes ;         // 节点数组
   list < TreeNode *>:: iterator LIt ;  // 一个节点迭代器
   int height ( TreeNode *);
   int level ( TreeNode *, Iterator );
};
 
//This is TreeSub Class Iterator
class Iterator {
   private : 
    Tree * _tree ;                     //Tree data
    list < TreeNode *>:: iterator _lit ;  //List Iterator
   public:
    Iterator ();                               // 默认构造函数
    Iterator ( const Iterator &);                // 复制构造函数
    Iterator ( Tree *, TreeNode *);                // 构造函数
    Iterator ( Tree *, list < TreeNode *>:: iterator ); // 构造函数
    // 运算符重载
    void operator=( const Iterator &);          // 赋值运算符重载
    bool operator==( const Iterator &);         // 关系运算符重载
    bool operator!=( const Iterator &);         // 关系运算符重载
    Iterator & operator++();                   // 前缀 ++ 运算符
    Iterator operator++( int );                 // 后缀 ++ 运算符
    int operator*() const ;                     // 获得节点信息
    bool operator!();                          // 赋值运算符重载
  
    typedef list < TreeNode *>:: iterator List ;
    friend class Tree ;
};
 
Tree.cpp
//tree.cpp 实现文件
 
#include "Tree.h"
 
//***** 下面是对于 TreeNode 结构体的定义实现 *****///
 
TreeNode::TreeNode( int type = 0,TreeNode* Parent = 0){
  _data = type ;
  _parent = Parent ;
}
void TreeNode:: SetParent (TreeNode& node ){
  _parent = & node ;
}
void TreeNode:: InsertChildren (TreeNode& node ){
 TreeNode* p = & node ;
  _children . push_back ( p );
}
 
 
 
//***** 下面是对于 Tree 类的定义实现 *****///
Tree :: Tree (){
 
}
 
Tree :: Tree ( const int type ){
  _nodes . push_back ( new TreeNode( type ));
}
 
Tree :: Tree ( const Tree & t ){
 if( t . _nodes . empty ())return;
  clone ( t . _nodes . front (), _nodes ,0);
}
Tree :: Tree ( const int type , const list < Tree *>& lit ){
 TreeNode* root = new TreeNode( type ); // 建立根节点
  _nodes . push_back ( root ); // 放入树中
  list < Tree *>:: const_iterator it ;
 for( it = lit . begin (); it != lit . end (); it ++){
 if(!((* it )-> _nodes . empty ())){ // 如果当前节点元素不为空
   Tree * tp = new Tree (** it );
   TreeNode* p = tp -> _nodes . front ();
   root -> _children . push_back ( p ); // 设置根的子节点
   p -> _parent = root ;            // 设置节点的父节点为根
   list <TreeNode*>:: iterator lit1 = tp -> _nodes . begin ();
   list <TreeNode*>:: iterator lit2 = tp -> _nodes . end ();
   list <TreeNode*>:: iterator lit3 = _nodes . end ();
   _nodes . insert ( lit3 , lit1 , lit2 );
 }
 }
}
 
Tree ::~ Tree (){
 for( list <TreeNode*>:: iterator it = _nodes . begin (); it != _nodes . end (); it ++){
 delete* it ;
 }
}
 
Tree & Tree ::operator =( const Tree & t ){
  Clear ();
  Tree * p = new Tree ( t );
  _nodes = p -> _nodes ;
 return *this;
}
 
bool Tree ::operator ==( const Tree & t ){
 if( _nodes . size ()!= t . _nodes . size ()){
 return false;
 }
  list <TreeNode*>:: iterator it = _nodes . begin ();
  list <TreeNode*>:: const_iterator _it = t . _nodes . begin ();
 while( it != _nodes . end ()&& _it != t . _nodes . end ()){
 if((* it )-> _data !=(* _it )-> _data ){
   return false;
 }
  it ++;
  _it ++;
 }
 return true;
}
 
bool Tree ::operator !=( const Tree & t ){
 if( _nodes . size ()!= _nodes . size ()){
 return true;
 }
 else{
  list <TreeNode*>:: iterator it = _nodes . begin ();
     list <TreeNode*>:: const_iterator _it = t . _nodes . begin ();
 while( it != _nodes . end ()&& _it != t . _nodes . end ()){
   if((* it )-> _data !=(* _it )-> _data ){
    return true;
   }
   it ++;
   _it ++;
 }
 return false;
 }
}
 
void Tree :: Clear (){
 for( list <TreeNode*>:: iterator it = _nodes . begin (); it != _nodes . end (); it ++){
 delete* it ;
 }
  _nodes . clear ();
}
 
bool Tree :: IsEmpty () const {
 return _nodes . empty ();
}
 
int Tree :: Size () const {
 return ( int ) _nodes . size ();
}
 
int Tree :: Leaves (){
  int i = 0;
  list <TreeNode*>:: iterator it = _nodes . begin ();
 while( it != _nodes . end ()){
 if((* it )-> _children . size ()==0){
   i ++;
 }
  it ++;
 }
 return i ;
}
 
 
int Tree :: Height (){
 if( _nodes . size ()!=0){
 TreeNode* TNode = _nodes . front ();
 return height ( TNode );
 }
 else{
 return -1; // 判断为空树
 }
}
 
int Tree :: height (TreeNode* node ){
 if(! node ){
 return -1;
 }
 else{
  list <TreeNode*> plist = node -> _children ;
 if( plist . size ()==0){
   return 0;
 }
  int hA = 0;
 for( list <TreeNode*>:: iterator it = plist . begin (); it != plist . end (); it ++){
   int hB = height (* it );
   if( hB > hA ){
    hA = hB ;
   }
 }
 return hA +1;
 }
}
 
 
Iterator Tree :: begin (){
 return Iterator (this, _nodes . begin ());
}
 
Iterator Tree :: end (){
 return Iterator (this, _nodes . end ());
}
int Tree :: Root () const {
 return (* _nodes . begin ())-> _data ;
}
 
 
bool Tree :: IsRoot ( Iterator it ){
 TreeNode p = * it ;
 if( p . _parent == 0){
 return true;
 }
 return false;
}
 
bool Tree :: isLeaf ( Iterator it ){
 TreeNode p = * it ;
 if( p . _children . size () == 0){
 return true;
 }
 return false;
}
 
Iterator Tree :: Parent ( Iterator it ){
 TreeNode p = * it ;
  Tree * t = it . _tree ;
  Iterator Ite ( t , p . _parent );
 return Ite ;
}
 
 
int Tree :: NumChildren ( Iterator it ){
 TreeNode p = * it ;
 return ( int ) p . _children . size ();
}
 
//***** 下面是对于 Tree::Iterator 类的定义实现 *****///
Iterator :: Iterator (){
}
 
Iterator :: Iterator ( const Iterator & it ){
  _tree = it . _tree ;
  _lit = it . _lit ;
}
 
Iterator :: Iterator ( Tree * t , TreeNode* n ){
  _tree = t ;
  list <TreeNode*>& nodes = _tree -> _nodes ;
  _lit = find ( nodes . begin (), nodes . end (), n ); //<algorithm> Members
}
 
Iterator :: Iterator ( Tree * t , list <TreeNode*>:: iterator lt ){
  _tree = t ;
  _lit = lt ;
}
 
void Iterator ::operator =( const Iterator & it ){
  _tree = it . _tree ;
  _lit = it . _lit ;
}
 
bool Iterator ::operator ==( const Iterator & it ){
 return _tree == it . _tree && _lit == it . _lit ;
}
 
bool Iterator ::operator !=( const Iterator & it ){
 return _tree != it . _tree || _lit != it . _lit ;
}
 
Iterator & Iterator ::operator ++(){
 ++ _lit ;
 return *this;
}
 
Iterator Iterator ::operator ++( int ){
  Iterator it (*this);
 ++ _lit ;
 return it ;
}
 
int Iterator ::operator *() const {
 return ((* _lit )-> _data );
}
 
bool Iterator ::operator !(){
 return _lit == _tree -> _nodes . end ();
}
 
//Clone 函数
TreeNode* clone (TreeNode* node , List & nodes ,TreeNode* nodep ){
 TreeNode* cp = new TreeNode( node -> _data , nodep );
  nodes . push_back ( cp );
  List & l = node -> _children ;
  List & cl = cp -> _children ;
 for( list <TreeNode*>:: iterator lt = l . begin (); lt != l . end (); lt ++){
  cl . push_back ( clone (* lt , nodes , cp ));
 }
 return cp ;
}
# c++ # list
Logo
向您推荐>>Eolink开发者社区

权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区

更多推荐

ELK实现containerd的容器日志采集展示【基于logging的全栈监测】

企业级ELK Stack构建介绍

avatar 云原生

深入理解 Mocha 测试框架：从零实现一个 Mocha

前言什么是自动化测试自动化测试在很多团队中都是Devops环节中很难执行起来的一个环节，主要原因在于测试代码的编写工作很难抽象，99%的场景都需要和业务强绑定，而且写测试代码的编写工作量往往比编写实际业务代码的工作量更多。在一些很多业务场景中投入产出比很低，适合写自动化测试的应该是那些中长期业务以及一些诸如组件一样的基础库。自动化测试是个比较大的概念，其中分类也比较多，比如单元测试，端对端测试，集

avatar 云原生

(20200916 Solved)docker-compose up创建容器自动退出

问题描述如题，创建容器后自动退出了。并且docker start container无效解决方案原因是缺失了控制终端的配置，需要在docker-compose.yml中增加tty:true ，有时候这样也不行，需要再增加一个command:/bin/bash，命令不一定是这个，需要是一个不会退出的命令，然后用-d后台启动容器。Referencesdocker-compose启动容器后自动退出...

avatar 云原生