43二叉树的抽象数据类型 template <class T> class BinaryTreeNode //申明二叉树为结点类的友元类,便于访问私有 //数据成员 friend class BinaryTree private t element//二叉树结点数据域 /实现时,可以补充 private的左右 /子结点定义 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 16 4.3 二叉树的抽象数据类型 template <class T> class BinaryTreeNode { //申明二叉树为结点类的友元类，便于访问私有 //数据成员 friend class BinaryTree; private: T element; //二叉树结点数据域 // 实现时，可以补充private的左右 //子结点定义
43二叉树的抽象数据类型 public: BinarytreeNodeO; /缺省构造函数 BinaryTreeNode( const T&ele)//拷贝构造函数 //给定了结点值和左右子树的构造函数 Binary TreeNode const T&ele, BinaryTreeNode*r) T valued const;//返回当前结点的数据 /返回当前结点指向左子树 BinaryTreeNode<T>* leftchildo const; ∥/返回当前结点指向右子树 Binary treeNode<t>* rightchildo const; 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 17 4.3 二叉树的抽象数据类型 public: BinaryTreeNode(); //缺省构造函数 BinaryTreeNode(const T& ele);//拷贝构造函数 //给定了结点值和左右子树的构造函数 BinaryTreeNode(const T& ele, BinaryTreeNode* l, BinaryTreeNode* r); T value() const;//返回当前结点的数据 //返回当前结点指向左子树 BinaryTreeNode<T>* leftchild() const; //返回当前结点指向右子树 BinaryTreeNode<T>* rightchild() const;
43二叉树的抽象数据类型 //设置当前结点的左子树 void setLeftchild BinarytreeNode*)i ∥/设置当前结点的右子树 void setRightchild(Binary TreeNode*)i /设置当前结点的数据域 void setValue( const T& val) //判定当前结点是否为叶结点若是返回true bool isLeafo const; /重载赋值操作符 Binary TreeNode<T>& operator= (const BinaryTreeNode<T>& Node) 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 18 4.3 二叉树的抽象数据类型 //设置当前结点的左子树 void setLeftchild(BinaryTreeNode*) ; //设置当前结点的右子树 void setRightchild(BinaryTreeNode*) ; //设置当前结点的数据域 void setValue(const T& val); //判定当前结点是否为叶结点,若是返回true bool isLeaf() const; //重载赋值操作符 BinaryTreeNode<T>& operator= (const BinaryTreeNode<T>& Node) };
43二叉树的抽象数据类型 二叉树的抽象数据类型的C++定义 BinaryTree,没有 具体规定该抽象数据类型的存储方式 template <class T> class BinaryTree t private /二叉树根结点指针 BinaryTreeNode<T>* root 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 4.3 二叉树的抽象数据类型 二叉树的抽象数据类型的C++定义BinaryTree，没有 具体规定该抽象数据类型的存储方式 template <class T> class BinaryTree { private: //二叉树根结点指针 BinaryTreeNode<T>* root;
43二叉树的抽象数据类型 public. Binarytree //构造函数 Binarytree /析构函数 bool isEmptyo const 判定二叉树是否为空树 /返回二叉树根结点 BinaryTreeNode<T>* RootOF //返回 current结点的父结点 Binary TreeNode<T>* Parent(Binary TreeNode<T>* current) /返回 current结点的左兄弟 BinaryTreeNode<t>* Leftsibling( BinaryTreeNode<T>* current; 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 20
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 20 4.3 二叉树的抽象数据类型 public: BinaryTree(); //构造函数 ~BinaryTree(); //析构函数 bool isEmpty() const; //判定二叉树是否为空树 //返回二叉树根结点 BinaryTreeNode<T>* Root(); //返回current结点的父结点 BinaryTreeNode<T>* Parent(BinaryTreeNode<T>* current); //返回current结点的左兄弟 BinaryTreeNode<T>* LeftSibling( BinaryTreeNode<T>* current);