数据结构(12)_树的概念及通用树的实现

1.树的定义与操作

1.1.树的相关定义

1.树的定义

树是一种非线性的数据结构,右n(n>=0)个结点组成的有限集合,如果n=0,称为空树,如果n>0,则:

创新互联公司基于成都重庆香港及美国等地区分布式IDC机房数据中心构建的电信大带宽,联通大带宽,移动大带宽,多线BGP大带宽租用,是为众多客户提供专业达州电信机房报价,主机托管价格性价比高,为金融证券行业服务器托管,ai人工智能服务器托管提供bgp线路100M独享,G口带宽及机柜租用的专业成都idc公司。

  • 有一个特定的结点被称之为跟结点(root),根结点只有直接后继,没有前驱,
  • 除根结点外的其他结点划分为m(m>=0)个互不相交的有限集合T0,T1...Tm-1,每一个集合又是一颗子树,并称之为跟的子树。
    树的示例如下:
    数据结构(12)_树的概念及通用树的实现

    2.树中度的概念

    树的结点包含一个数据及若干指向子树的分支,结点拥有的子树数目称为结点的度(度为0的结点称为叶结点;度不为0称为分支结点);
    树的度定义为所有结点中度的最大值。
    数据结构(12)_树的概念及通用树的实现

    3.树的前驱和后继

    结点的直接后继称为该结点的孩子,相应的,该结点称为孩子的双亲;
    结点的孩子的孩子,称为该结点的子孙,相应 该结点称为子孙的祖先;
    同一个双亲的孩子之间互称兄弟。
    数据结构(12)_树的概念及通用树的实现

    4.树中结点的层次

    树中结点最大层次称为树的深度或高度。
    数据结构(12)_树的概念及通用树的实现

    5.树的有序性

    如果树中结点的各个子树从左向右是有次序的,子树间不能互换位置,则称该树为有序树,否则为无序树。
    数据结构(12)_树的概念及通用树的实现

    6.森林的概念

    数据结构(12)_树的概念及通用树的实现

    1.2.树的抽象定义

    与其他的数据结构一样,树的常用操作包括:插入、删除、查找(获取树的节点)、获取树的高度/深度、获取树的度、清空树中的元素等。

    1.2.1.树的抽象定义

    template < typename T >
    class Tree : public Object
    {
    protected:
    TreeNode* m_root;
    public:
    Tree()  { m_root = NULL; }
    virtual bool insert(TreeNode* node) = 0;
    virtual bool insert(const T& value, TreeNode* node) = 0;
    virtual SharedPointer> remove(TreeNode* node) = 0;
    virtual SharedPointer> remove(const T& value) = 0;
    virtual TreeNode* find(TreeNode* node) const = 0;
    virtual TreeNode* find(const T& value) const = 0;
    virtual TreeNode* root() const = 0;
    virtual int degree() const = 0;
    virtual int hight() const = 0;
    virtual int count() const = 0;
    virtual void clear() =0;
    };

    1..2.2.树的节点的抽象定义

    树的节点也表现为一种特殊的数据类型

    template < typename T >
    class TreeNode : public Object
    {
    public:
    TreeNode* m_parent;
    
    TreeNode()
    {
        m_parent = NULL;
    }
    virtual ~TreeNode() = 0;
    };

    树与节点的类关系:都继承自顶层父类Object,通过树的节点与树形成组合关系。
    数据结构(12)_树的概念及通用树的实现
    总结:

  • 树是一种非线性的数据结构,拥有唯一前驱(父节点)和若干后继(子节点);
  • 树的结点包含一个数据及若干指向其他节点的指针,在程序中表现为一种特殊的数据类型。

    2.树的存储结构设计

    课程目标:完成树和结点的存储结构设计。
    前面我们实现了树的抽象结构,本节我们实现一个通用树结构的基本框架。类继承结构如下图所示:
    数据结构(12)_树的概念及通用树的实现
    设计要点:
    1.GTree为通用树结构,每个结点可以存在多个后继结点;
    2.GTreeNode能够包含任意多指向后继结点的指针
    3.实现树结构的所有操作(增、删、查、改、等)

    2.1.GTreeNode的设计与实现

    我们使用单链表组合完成GTreeNode的实现,便于在GTreeNode中存储多个指向其后继结点的指针;
    数据结构(12)_树的概念及通用树的实现

    template < typename T >
    class GTreeNode : public TreeNode
    {
    public:
    LinkList*> child;
    ~GTreeNode(){}
    };

    2.2.GTree的设计与实现

    数据结构(12)_树的概念及通用树的实现

    template
    class GTree : public Tree
    { };

    2.3.GTree(通用树结构)的架构实现

    数据结构(12)_树的概念及通用树的实现
    问题:每个树结中为什么要包含指向前驱结点的指针?
    数据结构(12)_树的概念及通用树的实现
    数据结构(12)_树的概念及通用树的实现

    3. 树的通用操作实现

    3.1.树中结点的查找操作

    查找方式:

  • 基于数据元素值的查找
    GTreeNode<T>* find(const T& value) const
  • 基于结点的查找
    GTreeNode<T>* find(TreeNode<T>* node) const
    数据结构(12)_树的概念及通用树的实现
    基于数据元素值的查找:
    定义功能函数:find (node, value),在node为根结点的树中递归查找value所在的节点
    数据结构(12)_树的概念及通用树的实现

    GTreeNode* find(GTreeNode* node, const T& value)const
    {
      GTreeNode* ret = NULL;
      if(node != NULL)
      {
          //如果根结点的就是目标结点
          if(node->value == value)
          {
              ret =  node;
          }
          else
          {
              //遍历根节点的子结点
              for(node->m_children.move(0); !node->m_children.end() && (ret == NULL); node->m_children.next())
              {
                  //对每个子子结点进行查找
                  ret = find(node->m_children.current(), value);
              }
          }
      }
      return ret;
    }
    
    //查找结点
    virtual GTreeNode* find(const T& value)const
    {
      return find(root(), value);
    }

    基于结点的查找:
    定义功能函数:find(node, obj),在node为根结点的树中递归查找是否存在obj结点;
    数据结构(12)_树的概念及通用树的实现

    GTreeNode* find(GTreeNode* node, GTreeNode* obj)const
    {
      GTreeNode* ret = NULL;
      //根结点为目标结点
      if(node == obj)
      {
          ret =  node;
      }
      else
      {
          if(node != NULL)
          {
              //遍历子结点
              for(node->m_children.move(0); !node->m_children.end() && (ret == NULL); node->m_children.next())
              {
                  ret = find(node->m_children.current(), obj);
              }
          }
      }
      return ret;
    }
    
    virtual GTreeNode* find(TreeNode* node)const
    {
      return find(root(), dynamic_cast*>(node));
    }

    总结:
    1.查找操作是树的关键操作之一,插入函删除操作都依赖于查找操作;
    2.基于数据元素的查找可以判断值是否存在于树中;基于结点的查找可以判断树中是否存在指定结点;

    3.1.树中结点的插入操作

    插入方式:

  • 插入新的结点
    bool insert(TreeNode<T>* node)
  • 插入新的数据元素
    bool insert(const T& value,TreeNode<T>* parent)
    问题:如何指定新结点在树中的位置?
    1.树是非线性的,无法采用下标的形式定位数据元素
    2.每一个树结点都有一个唯一的前驱结点(父节点),必须先找到前驱结点才能完成结点的插入;
    数据结构(12)_树的概念及通用树的实现
    插入节点操作
    数据结构(12)_树的概念及通用树的实现
    bool insert(TreeNode* node)
    {
      bool ret = true;
      if(node != NULL)
      {
          //树为空,插入结点为根结点
          if(this->m_root == NULL)
          {
              node->parent = NULL;
              this->m_root = node;
          }
          else
          {
              //找到插入结点的父结点
              GTreeNode* np = find(node->parent);
              if(np != NULL)
              {
                  GTreeNode* n = dynamic_cast*>(node);
                  //如果子结点中无该结点,插入结点
                  if(np->m_children.find(n) < 0)
                  {
                      ret = np->m_children.insert(n);
                  }
              }
              else
              {
                  THROW_EXCEPTION(InvalidOperationException, "Invalid node...");
              }
          }
      }
      else
      {
          THROW_EXCEPTION(InvalidParameterException, "Parameter is invalid...");
      }
      return ret;
    }

    插入数据元素:
    数据结构(12)_树的概念及通用树的实现

    bool insert(const T& value, TreeNode* parent)
    {
      bool ret = true;
      GTreeNode* node = GTreeNode::NewNode();
      if(node != NULL)
      {
          node->value = value;
          node->parent = parent;
          insert(node);
      }
      else
      {
          THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
      }
      return ret;
    }

    总结:
    1.插入操作是构建树的唯一操作,需要从堆空间中创建结点
    2.执行插入操作必须正确处理指向父节点的指针

3.3.树中结点的清除操作

3.3.1.清除操作

清除操作的定义:void clear() //将树中的所有节点清除(释放堆中的节点)
数据结构(12)_树的概念及通用树的实现
清除操作功能函数定义:
free(node) //清除node为根结点的树,释放树中的每一个结点
数据结构(12)_树的概念及通用树的实现
问题:树中的结点可能来源于不同的存储空间,如何判断堆空间中的结点并释放?
1.单凭内存地址很难准确判断具体的存储区域;
2.只有堆空间的内存才需要主动释放(delete)
3.清除操作时只需要对堆中的结点进行释放

3.3.2.工厂模式

1.在GTreeNode中增加保护成员m_flag;
2.将GTreeNode中的operator new重载为保护成员函数;
3.提供工厂方法GTreeNode* NewNode()
4.在工厂方法中new新结点并将m_flage设置为true;
树结点的工厂模式示例:

template 
  class GTreeNode:public TreeNode
  {
  protected:
    bool m_flag;//堆空间标识
    //重载new操作符,声明为保护
    void* operator new(unsigned int size)throw()
    {
      return Object::operator new(size);
    }

  public:
    LinkedList*> m_children;
    GTreeNode()
    {
      //栈上分配的空间标识为false
      m_flag = false;
    }
    //工厂方法,创建堆空间的结点
    static GTreeNode* NewNode()
    {
      GTreeNode* ret = new GTreeNode();
      if(ret != NULL)
      {
          //堆空间的结点标识为true
          ret->m_flag = true;
      }
      return ret;
    }
    //堆空间结点标识访问函数
    bool flag()const
    {
      return m_flag;
    }
  };
//结点的释放:
    void free(GTreeNode* node)
    {
      if(node != NULL)
      {
          for(node->m_children.move(0); !node->m_children.end(); node->m_children.next())
          {
              free(node->m_children.current());
          }
          //如果结点存储在堆空间
          if(node->flag())
             delete node;//释放
      }
    }
//清空树:
    void clear()
    {
        free(root());
        this->m_root = NULL;
    }

总结:
1.清除操作用于销毁树中的每个结点,需要释放对应的内存空间;
2.工厂模式可用于“定制”堆空间中的结点,只有销毁定制结点的时候需要进行释放

3.4树中结点的删除操作

删除的方式:

  • 基于数据元素的删除
    SharedPointer< Tree<T> > remove(const T& value)
  • 基于结点的删除
    SharedPointer< Tree<T> > remove(TreeNode<T>* node)
    删除操作成员函数的操作要点:
    1.被删除的结点所代表的子树进行删除;
    2.删除函数返回一棵树堆空间中的树
    3.具体返回值为指向树的智能指针对象
    数据结构(12)_树的概念及通用树的实现
    实用的设计原则:
    当需要从函数中返回堆中的对象时,使用智能指针(SharedPointer)作为函数的返回值。
    删除操作功能函数定义:
    void remove(GTreeNode<T>* node, GTree<T>*& ret)
    1.将node为根结点的子树从原来的树中删除
    2.Ret做为子树返回(ret指向堆空间中的树对象)
    数据结构(12)_树的概念及通用树的实现

    // 删除操作功能函数
    void remove(GTreeNode* node, GTree*& ret)
    {
      ret = new GTree();
      if(ret != NULL)
      {
          //如果删除的结点是根结点
          if(root() == node)
          {
              this->m_root = NULL;
          }
          else
          {
              //获取删除结点的父结点的子结点链表
              LinkedList*>& child = dynamic_cast*>(node->parent)->m_children;
              //从链表中删除结点
              child.remove(child.find(node));
              //结点的父结点置NULL
              node->parent = NULL;
          }
          //将删除结点赋值给创建的树ret的根结点
          ret->m_root = node;
      }
      else
      {
          THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
      }
    }
    // A、基于删除数据元素值删除结点
    
    SharedPointer> remove(const T& value)
    {
      GTree* ret = NULL;
      //找到结点
      GTreeNode* node = find(value);
      if(node != NULL)
      {
          remove(node, ret);
      }
      else
      {
          THROW_EXCEPTION(InvalidParameterException, "Parameter invalid...");
      }
      return ret;
    }
    // B、基于结点删除
    
    SharedPointer> remove(TreeNode* node)
    {
      GTree* ret = NULL;
      node = find(node);
      if(node != NULL)
      {
          remove(dynamic_cast*>(node), ret);
      }
      else
      {
          THROW_EXCEPTION(InvalidParameterException, "Parameter invalid...");
      }
      return ret;
    }

    总结:
    1.删除操作将目标节点所代表的子树移除,返回值为指向树智能指针对象;
    2.删除操作必须完善处理父节点和子节点的关系;
    3.函数中返回堆中的对象时,使用智能指针作为返回值。

    3.5.树的属性操作实现

    3.5.1.树中结点的数目

    定义功能,count(node),在node为根结点的树中统计结点数目。
    使用递归实现:结点数目 = 子树结点数目+1(根结点)。
    数据结构(12)_树的概念及通用树的实现
    数据结构(12)_树的概念及通用树的实现

int count(GTreeNode* node) const
    {
      int ret = 0;
      if(node != NULL)
      {
          ret = 1;//根结点
          //遍历根节点的子结点
          for(node->m_children.move(0); !node->m_children.end(); node->m_children.next())
          {
              ret += count(node->m_children.current());
          }
      }
      return ret;
    }
    //树的结点数目访问函数
    int count()const
    {
        count(root());
    }

3.5.2.树的高度

功能定义:height(node),获取node为根结点的树的高度。
递归实现:树的高度 = 子树结点高度的最大值 + 1(根结点)。
数据结构(12)_树的概念及通用树的实现
数据结构(12)_树的概念及通用树的实现

int degree(GTreeNode* node) const
    {
      int ret = 0;
      if(node != NULL)
      {
          //结点的子结点的数量
          ret = node->m_children.length();
          //遍历子结点
          for(node->m_children.move(0); !node->m_children.end(); node->m_children.next())
          {
              int d = degree(node->m_children.current());
              if(ret < d)
              {
                  ret = d;
              }
          }
      }
      return ret;
    }

    //树的度访问函数
    int degree()const
    {
        return degree(root());
    }

3.5.3.树的度数

功能定义:degree(node),获取node为结点的树的度数。
递归实现:树的度数 = 子树的最大度数 + 1(根结点)
数据结构(12)_树的概念及通用树的实现
数据结构(12)_树的概念及通用树的实现

int height(GTreeNode* node)const
    {
      int ret = 0;
      if(node != NULL)
      {
          //遍历子结点
          for(node->m_children.move(0); !node->m_children.end(); node->m_children.next())
          {
              //当前结点的高度
              int h = height(node->m_children.current());
              if(ret < h)
              {
                  ret = h;
              }
          }
          ret = ret + 1;
      }
      return ret;
    }
    //树的高度访问函数
    int height()const
    {
        height(root());
    }

3.6.树形结构的层次遍历

问题:如何按照层次遍历通用树结构中的每一个数据元素?
当前的事实:- 树是一种非线性的数据结构,树的节点没有固定的编号方式;
新的需求:- 为通用树结构提供新的方法,快速遍历每一个节点
设计思路:
在树中定义一个新游标(GTreeNode*),遍历开始将游标指向根结点(root()),获取游标指向的数据元素,通过结点中的child成员移动游标;
提供一组遍历相关的函数,按层次访问树中的数据元素。
数据结构(12)_树的概念及通用树的实现
层次遍历算法:
原料:class LinkQueue; 游标:LinkQueue::front();
思想:

  • begin() 将根结点压人队列中
  • current() 访问队头指向的数据元素
  • next() 队头元素弹出,将队头元素的孩子压入队列中(核心)
  • end() 判断队列是否为空
    数据结构(12)_树的概念及通用树的实现

    //将根结点压入队列中
    bool begin()
    {
      bool ret = (root() != NULL);
      if(ret)
      {
          //清空队列
          m_queue.clear();
          //根节点加入队列
          m_queue.add(root());
      }
      return ret;
    }
    //判断队列是否为空
    bool end()
    {
        return (m_queue.length() == 0);
    }
    //队头元素弹出,将队头元素的孩子压入队列中
    bool next()
    {
      bool ret = (m_queue.length() > 0);
      if(ret)
      {
          GTreeNode* node = m_queue.front();
          m_queue.remove();//队头元素出队
          //将队头元素的子结点入队
          for(node->m_children.move(0); !node->m_children.end(); node->m_children.next())
          {
              m_queue.add(node->m_children.current());
          }
      }
      return ret;
    }
    //访问队头元素指向的数据元素
    T current()
    {
      if(!end())
      {
          return m_queue.front()->value;
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No value at current Node...");
        }
    }

    总结:
    1.树的结点没有固定的编号方式,可以按照层次关系堆树中的结点进行遍历;
    2.通过游标的思想设计成员函数,遍历函数是相互依赖,相互配合的;
    3.遍历操作的核心是队列的使用。

    4. 通用树的最终实现

    4.1 GTree的实现

    template
    class GTree : public Tree
    {
    protected:
    LinkQueue*> m_queue;
    
    GTree(const GTree&);
    GTree& operator =(const GTree&);  //容器的内容不能复制
    
    GTreeNode* find(GTreeNode* node, const T& value) const
    {
        GTreeNode* ret = NULL;
    
        if(node != NULL)
        {
            if(node->value == value)
            {
                ret = node;
            }
            else
            {
                // 遍历单链表(树中子结点的指针),
                for(node->child.move(0); (!node->child.end()) && (ret==NULL); node->child.next())
                {
                    ret = find(node->child.current(), value);
                }
            }
        }
    
        return ret;
    }
    
    GTreeNode* find(GTreeNode* node, GTreeNode* obj) const
    {
        GTreeNode* ret = NULL;
    
        if(node != NULL)
        {
            if(node == obj)
            {
                ret = node;
            }
            else
            {
                for(node->child.move(0);!node->child.end() && (ret == NULL);node->child.next())
                {
                    ret = find(node->child.current(),obj);
                }
            }
        }
    
        return ret;
    }
    
    //清空数的功能函数,递归是释放每个子树
    void free(GTreeNode* node)
    {
        if(node != NULL)    //递归出口
        {
            for(node->child.move(0); !node->child.end(); node->child.next())
            {
                free(node->child.current());
            }
    
            //如果结点存在于堆空间,则释放
            if(node->flag())
            {
                delete node;
            }
            /*else
            {
                cout << node->value << endl;
            }*/
        }
    }
    
    // 删除操作的功能函数,(1.将node为根结点的子树从原来的树中删除 2.Ret做为子树返回(ret指向堆空间中的树对象))
    void remove(GTreeNode* node, GTree*& ret)     //ret 是一个指针的别名
    {
        ret = new GTree();
    
        if(ret != NULL)
        {
            if(node == root())
            {
                this->m_root = NULL;
            }
            else
            {
                 //获取删除结点的父结点的子结点链表
                LinkList*>& child = dynamic_cast*>(node->m_parent)->child;
                // 从链表中删除节点
                child.remove(child.find(node));
                // 结点的父结点置NULL
                node->m_parent = NULL;
            }
            // 将删除结点赋值给创建的树ret的根结点
            ret->m_root = node;
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "no memory to create GTree...");
        }
    }
    
    int count(GTreeNode* node) const
    {
        int ret = 0;
    
        if(node != NULL)
        {
            ret = 1;    //根结点
            //递归计算子树的节点
            for(node->child.move(0); !node->child.end(); node->child.next())
            {
                ret += count(node->child.current());
            }
        }
    
        return ret;
    }
    
    int height(GTreeNode* node) const
    {
        int ret = 0;
    
        if(node != NULL)
        {
            for(node->child.move(0); !node->child.end(); node->child.next())
            {
                int h = height(node->child.current());
    
                if(h > ret)     //获取子树高度的最大值
                {
                    ret = h;
                }
            }
    
            ret = ret + 1/*根结点*/;
        }
    
        return ret;
    }
    
    int degree(GTreeNode* node) const
    {
        int ret = 0;
    
        if(node != NULL)
        {
            ret = node->child.length();
    
            for(node->child.move(0); !node->child.end(); node->child.next())
            {
                int d = degree(node->child.current());
    
                if(ret < d)
                {
                    ret = d;    //获取子树高度的最大度数
                }
            }
        }
    
        return ret;
    }
    public:
    GTree(){}
    
    bool insert(TreeNode* node)
    {
        bool ret = true;
    
        if(node != NULL)
        {
            if(this->m_root == NULL)
            {
                this->m_root = node;
                node->m_parent = NULL;
            }
            else
            {
                GTreeNode* np = find(node->m_parent);
    
                if(np != NULL)
                {
                    GTreeNode* n = dynamic_cast*>(node);
    
                    // 防止重复插入
                    if( np->child.find(n) < 0 )
                    {
                        np->child.insert(n);
                    }
    
                }
                else
                {
                    THROW_EXCEPTION(InvaildParemeterException, "can't find parent node for current node...");
                }
            }
        }
        else
        {
            THROW_EXCEPTION(InvaildParemeterException, "con't insert NULL node...");
        }
    
        return ret;
    }
    
    bool insert(const T& value, TreeNode* parent)
    {
        bool ret = true;
    
        GTreeNode* node = GTreeNode::NewNode();
    
        if(node != NULL)
        {
            node->value = value;
            node->m_parent = parent;
            insert(node);
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "no memory to create node... ");
        }
    
        return ret;
    }
    
    SharedPointer< Tree > remove(const T& value)
    {
        GTree* ret = NULL;
        GTreeNode* node = find(value);
    
        if(node != NULL)
        {
            remove(node, ret);
            m_queue.clear();
            m_queue.clear();
        }
        else
        {
            THROW_EXCEPTION(InvaildParemeterException, "invaild paremeter...");
        }
    
        return ret;
    }
    
    SharedPointer< Tree > remove(TreeNode* node)
    {
        GTree* ret = NULL;
        node = find(node);
    
        if(node != NULL)
        {
            remove(dynamic_cast*>(node), ret);
        }
        else
        {
            THROW_EXCEPTION(InvaildParemeterException, "invaild paremeter...");
        }
    
        return ret;
    }
    
    GTreeNode* find(const T& value) const
    {
    
        return find(root(),value);
    }
    
    GTreeNode* find(TreeNode* node) const
    {
        return find(root(), dynamic_cast*>(node));
    }
    
    GTreeNode* root() const
    {
        return dynamic_cast*>(this->m_root);
    }
    
    int degree() const
    {
        return degree(root());
    }
    
    int count() const
    {
        return count(root());
    }
    
    int height() const
    {
        return height(root());
    }
    
    void clear()
    {
        free(root());
        this->m_root = NULL;
    }
    
    bool begin()
    {
        bool ret = (root() != NULL);
    
        if(ret)
        {
            m_queue.clear();
            m_queue.enqueue(root());
        }
    
        return ret;
    }
    
    bool end()
    {
        return (m_queue.length() == 0);
    }
    
    bool next()
    {
        bool ret = (m_queue.length() > 0);
    
        if(ret)
        {
            GTreeNode* node = m_queue.front();
            m_queue.dequeue();
    
            for(node->child.move(0); !node->child.end(); node->child.next())
            {
                m_queue.enqueue(node->child.current());
            }
        }
    
        return ret;
    }
    
    T current()
    {
        if(!end())
        {
            return m_queue.front()->value;
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "invalid operation ...");
        }
    }
    
    ~GTree()
    {
        clear();
        m_queue.clear();
    }
    };

4.2. GTreeNode的实现

template < typename T >
class GTreeNode : public TreeNode
{
protected:
    //堆空间标识,如果在堆空间中创建了结点,则置为true,以便后续释放结点时判断结点是否创建自堆空间
    bool m_flag;

    GTreeNode(const GTreeNode&);
    GTreeNode& operator =(const GTreeNode&);  //容器的内容不能复制

    //重载new操作符,声明为保护成员
    void* operator new(unsigned int size)throw()
    {
      return Object::operator new(size);
    }
public:
    LinkList*> child;

    GTreeNode()
    {
        m_flag = false;
    }

    static GTreeNode* NewNode()
    {
        GTreeNode* ret = new GTreeNode();

        if(ret != NULL)
        {
            ret->m_flag = true;  //在堆空间中申请了结点,则将该标识置为true
        }

        return ret;
    }

    //堆空间结点标识访问函数
    bool flag()const
    {
     return m_flag;
    }

    ~GTreeNode(){}
};

文章标题:数据结构(12)_树的概念及通用树的实现
网页地址:http://cdiso.cn/article/ppgssd.html

其他资讯