61 二叉树的存储结构设计

• 目标

  • 完成二叉树和二叉树结点的存储结构设计

  

• 设计要点

  • BTree为二叉树结构，每个结点最多只有两个后继结点
  • BTreeNode只包含4个固定的公有成员(哪4个？)
  • 实现树结构的所有操作(增，删，查，等)

• BTreeNode的设计与实现

  

  template<typename T>
  class BTreeNode : public TreeNode<T>{
  public:
      BTreeNode<T> *left;
      BTreeNode<T> *right;
      //factory pattern
      //......
  };

• BTree的设计与实现

  

  template<typename T>
  class BTree : public Tree<T>{
      //implemrntation
  };

• BTree(二叉树结构)的实现架构

  

编程实验

• 二叉树结构的创建

思考：如何实现BTree(二叉树结构)的结点查找操作？

62 二叉树中的结点查找操作

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

• 查找的方式

  • 基于数据元素值的查找BTreeNode<T>* find(const T &value)const
  • 基于结点的查找BTreeNode<T>* find(TreeNode<T> *node)const

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

  

• 基于数据元素值的查找

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

  

编程实验(一)

• 基于数据元素值的查找

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

• 基于结点的查找

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

  

编程实验(二)

• 基于结点的查找

思考：如何实现BTree(二叉树结构)的结点插入操作？