57-58 树形结构的层次遍历

阅读量: 101阅读人次: 102

57 树中属性操作的实现

树中属性操作的实现(一)

• 树中结点的数目

  • 定义功能：count(node)
    • 在node为根结点的树中统计结点数目

  

• 树结点数目的计算示例

  • count(A)=count(B)+count(C)+count(D)+1

  

编程实验(一)

• 树中结点的数目

树中属性操作的实现(二)

• 树的高度

  • 定义功能：height(node)
    • 获取node为根结点的树的高度

  

• 树的高度示例

  • height(A)=MAX{height(B),height(C),height(D)}+1

  

编程实验(二)

• 树的高度

树中属性操作的实现(三)

• 树的度数

  • 定义功能：degree(node)
    • 获取node为根结点的树的度数

  

• 树的度数计算示例

  • degree(A)=MAX{degree(B),degree(C),degree(D),3}

  

编程实验(三)

• 树的度数

思考：如何遍历GeneralTree(通用树结构)的每一个结点？

58 树形结构的层次遍历

树形结构的层次遍历

• 问题 如何按层次遍历通用树结构中的每一个数据元素？

• 当前的事实

  • 树是非线性的数据结构，树的结点没有固定的编号方式

• 新的需求

  • 为通用树结构提供新的方法，快速遍历每一个结点

• 设计思路（游标）

  • 在树中定义一个游标（GTreeNode<T>*）
  • 遍历开始前将游标指向根结点（root()）
  • 获取游标指向的数据元素
  • 通过结点中的child成员移动游标

  提供一组遍历相关的函数，按层次访问树中的数据元素。

  函数	功能说明
  begin()	初始化，准备进行遍历访问
  next()	移动游标，指向下一个结点
  current()	获取游标所指向的数据元素
  end()	判断游标是否达到尾部

• 层次遍历算法

  • 原料：class LinkQueue<T>;
  • 游标：LinkQueue<T>::front();
  • 思想：
    • begin()→将根结点压入队列中
    • current()→访问队头元素指向的数据元素
    • next()→队头元素弹出，将队头元素的孩子压入队列中（核心）
    • end()→判断队列是否为空

• 层次遍历算法示例

  

  函数调用	队列状态	出队结点
  begin()	A
  next()	B,C,D	A
  next()	C,D,E,F	B
  next()	D,E,F,G	C
  next()	E,F,G,H,I,J	D
  next()	F,G,H,I,J,K,L	E
  next()	G,H,I,J,K,L	F
  next()	H,I,J,K,L	G
  next()	I,J,K,L,M	H
  ...	...	...

编程实验

• 通用树结构的层次遍历

小结

• 树的结点没有固定的编号方式
• 可以按照层次关系对树中的节点进行遍历
• 通过游标的思想设计遍历成员函数
• 遍历成员函数是相互依赖，相互配合的关系
• 遍历算法的核心为队列的使用