53 树中结点的查找操作

树中结点的查找操作(一)

• 查找的方式

  • 基于数据元素值的查找

    GTreeNode<T>* find(const T &value)const

  • 基于结点的查找

    GTreeNode<T>* find(TreeNode<T> *node)const

• 树中数据元素和结点的查找

  

• 基于数据元素值的查找

  • 定义功能：find(node,value)
    • 在node为根结点的树中查找value所在的结点

  

编程实验(一)

• 基于数据元素值的查找

树中结点的查找操作(二)

• 基于结点的查找

  • 定义功能：find(node,obj)
    • 在node为根结点的树中查找是否存在obj结点

  

编程实验(二)

• 基于结点的查找

小结

• 查找操作是树的关键操作之一
• 基于数据元素的查找可判断值是否存在于树中
• 基于结点的查找可判断树中是否存在指定结点
• 插入操作和删除操作都依赖于查找操作

思考：如何实现GeneralTree(通用树结构)的结点插入操作

54 树中结点的插入操作

树中结点的插入操作

• 插入的方式

  • 插入新结点bool insert(TreeNode<T> *node)
  • 插入数据元素bool insert(const T &value,TreeNode<T> *parent)

• 问题 如何指定新结点在树中的位置？

• 问题分析

  • 树是非线性的，无法采用下标的形式定位数据元素
  • 每一个树结点都有唯一的前驱结点（父结点）
  • 因此，必须先找到前驱结点，才能完成新结点的插入

• 新结点的插入

  

• 插入新结点

  

• 插入数据元素

  

编程实验

• 树的插入操作

小结

• 插入操作是构建树的唯一操作
• 执行插入操作时必须指明结点间的父子关系
• 插入操作必须正确处理指向父结点的指针
• 插入数据元素时需要从堆空间中创建结点

思考：如何实现GeneralTree(通用树结构)的结点清除操作？