42二叉树的性质 二叉树的高度定义为二叉树中层数最 大的叶结点的层数加1 二叉树的深度定义为二叉树中层数最 大的叶结点的层数 北京大学信息学院 版权所有,转载或翻印必究 Page 16
北京大学信息学院 ©版权所有，转载或翻印必究 Page 16 4.2 二叉树的性质 ◼ 二叉树的高度定义为二叉树中层数最 大的叶结点的层数加1 ◼ 二叉树的深度定义为二叉树中层数最 大的叶结点的层数
43二叉树的抽象数据类型 定义了二叉树的逻辑结构之后,我们需要考虑在二叉树逻辑 结构之上的各种可能运算,这些运算应该适合二叉树的各种 应用 二叉树的某些运算是针对整棵树的 初始化二叉树 合并两棵二叉树 二叉树的大部分运算都是围绕结点进行的 访问某个结点的左子结点、右子结点、父结点 访问结点存储的数据。 北京大学信息学院 版权所有,转载或翻印必究 Page 17
北京大学信息学院 ©版权所有，转载或翻印必究 Page 17 4.3 二叉树的抽象数据类型 ◼ 定义了二叉树的逻辑结构之后，我们需要考虑在二叉树逻辑 结构之上的各种可能运算，这些运算应该适合二叉树的各种 应用 ： ◼ 二叉树的某些运算是针对整棵树的 ◼ 初始化二叉树 ◼ 合并两棵二叉树 ◼ 二叉树的大部分运算都是围绕结点进行的 ◼ 访问某个结点的左子结点、右子结点、父结点 ◼ 访问结点存储的数据
43二叉树的抽象数据类型 二叉树结点抽象数据类型 BinaryTreeNode是带有 参数T的模板,T是存储在结点中的数据类型 n每个元素结点都有 eftchildo和 rightchild(左右子结点 结构 n另外每个结点还包含一个数据域 value 为了强调抽象数据类型与存储无关,我们并没有具 体规定该抽象数据类型的存储方式 北京大学信息学院 版权所有,转载或翻印必究 Page 18
北京大学信息学院 ©版权所有，转载或翻印必究 Page 18 4.3 二叉树的抽象数据类型 ◼ 二叉树结点抽象数据类型BinaryTreeNode是带有 参数 T 的模板，T是存储在结点中的数据类型 ◼ 每个元素结点都有leftchild()和rightchild()左右子结点 结构 ◼ 另外每个结点还包含一个数据域value()。 ◼ 为了强调抽象数据类型与存储无关，我们并没有具 体规定该抽象数据类型的存储方式
43二叉树的抽象数据类型 template <class T> class binaryTreenode //申明二叉树为结点类的友元类,便于访问私有 /数据成员 friend class BinaryTree prIvate //二叉树结点数据域 T element //实现时,可以补充 private的左子结点 /右子结点定义 北京大学信息学院 版权所有,转载或翻印必究 Page 19
北京大学信息学院 ©版权所有，转载或翻印必究 Page 19 4.3 二叉树的抽象数据类型 template <class T> class BinaryTreeNode { //申明二叉树为结点类的友元类，便于访问私有 //数据成员 friend class BinaryTree; private: //二叉树结点数据域 T element; // 实现时，可以补充private的左子结点 //右子结点定义
43二叉树的抽象数据类型 public. Binary TreeNode i /缺省构造函数 BinaryTreeNode( const t&ele);//贝构造函数 /给定了结点值和左右子树的构造函数 BinaryTreeNode const T& ele BinaryTreeNode<T>* Binary TreeNode<T>* ri T value( const//返回当前结点的数据 ∥/返回当前结点指向左子树 BinaryTreeNode<T>k leftchildo const; ∥/返回当前结点指向右子树 BinaryTreeNode<T>k rightchildo const; 北京大学信息学院 版权所有,转载或翻印必究 Page 20
北京大学信息学院 ©版权所有，转载或翻印必究 Page 20 4.3 二叉树的抽象数据类型 public: BinaryTreeNode(); //缺省构造函数 BinaryTreeNode(const T& ele);//拷贝构造函数 //给定了结点值和左右子树的构造函数 BinaryTreeNode(const T& ele, BinaryTreeNode<T>* l, BinaryTreeNode<T>* r); T value() const;//返回当前结点的数据 //返回当前结点指向左子树 BinaryTreeNode<T>* leftchild() const; //返回当前结点指向右子树 BinaryTreeNode<T>* rightchild() const;