×
028-86922220

建站动态

根据您的个性需求进行定制 先人一步 抢占小程序红利时代

数据结构（12）_树的概念及通用树的实现

1.树的定义与操作

1.1.树的相关定义

1.树的定义

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

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

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树中结点的删除操作

删除的方式：

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();
思想：

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://www.tsicrk.com/article/ppgssd.html

其他资讯

让你的专属顾问为你服务

0.8240s