43二叉树的抽象数据类型 /设置当前结点的左子树 void setLeftchild(Binary treeNode<T>*)i ∥/设置当前结点的右子树 void setRightchild(BinaryTreeNode<T>x) /设置当前结点的数据域 void setValue(const T& val) //判定当前结点是否为叶结点若是返回true bool isLeaf(o const; /重载赋值操作符 BinaryTreeNode<T>& operator= (const BinaryTreeNode<T>& Node); Fi 北京大学信息学院 版权所有,转载或翻印必究 Page 21
北京大学信息学院 ©版权所有，转载或翻印必究 Page 21 4.3 二叉树的抽象数据类型 //设置当前结点的左子树 void setLeftchild(BinaryTreeNode<T>*) ; //设置当前结点的右子树 void setRightchild(BinaryTreeNode<T>*) ; //设置当前结点的数据域 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 /二叉树根结点指针 Binary TreeNode<T>* root; //从二叉树的root结点开始 //查找 current结点的父结点 Binary TreeNode<T>k GetParent(BinaryTreeNode<T>* root, BinaryTreeNode<T>* current) 北京大学信息学院 版权所有,转载或翻印必究 Page 22
北京大学信息学院 ©版权所有，转载或翻印必究 Page 22 4.3 二叉树的抽象数据类型 ◼ 二叉树的抽象数据类型的C++定义BinaryTree，没有具体规 定该抽象数据类型的存储方式 template <class T> class BinaryTree { private: //二叉树根结点指针 BinaryTreeNode<T>* root; //从二叉树的root结点开始 //查找current结点的父结点 BinaryTreeNode<T>* GetParent(BinaryTreeNode<T>* root, BinaryTreeNode<T>* current);
43二叉树的抽象数据类型 public Binary Tree(root=NULL) //构造函数 ~ BinaryTree({ DeleteBinaryTree(root)H}//析构函数 bool isEmpty o const, //判定二叉树是否为空树 /返回二叉树根结点 BinaryTreeNode<T>* Roototreturn root; ji //返回 current结点的父结点 BinaryTreeNode<T>* Parent(BinaryTreeNode<T>x current); /返回 current结点的左兄弟 BinaryTreeNode<T>* Leftsibling( BinaryTreeNode<t>* current) 北京大学信息学院 版权所有,转载或翻印必究 Page 23
北京大学信息学院 ©版权所有，转载或翻印必究 Page 23 4.3 二叉树的抽象数据类型 public: BinaryTree(root=NULL); //构造函数 ~BinaryTree() {DeleteBinaryTree(root);};//析构函数 bool isEmpty() const; //判定二叉树是否为空树 //返回二叉树根结点 BinaryTreeNode<T>* Root(){return root;}; //返回current结点的父结点 BinaryTreeNode<T>* Parent(BinaryTreeNode<T>* current); //返回current结点的左兄弟 BinaryTreeNode<T>* LeftSibling( BinaryTreeNode<T>* current);
43二叉树的抽象数据类型 /返回 current结点的右兄弟 Binary TreeNode<T>* Rightsibling( Binary TreeNode<T>* current) /以elem作为根结点, leftTree作为树的左子树, / rightTree作为树的右子树,构造一棵新的二叉树 void CreateTree(const T& elem, BinaryTree<T>& leftTree BinaryTree<T>& rightTree)i //前序周游二叉树或其子树 void preOrder(BinaryTreenode<t>* root); /中序周游二叉树或其子树 void InOrder (Binary TreeNode<T>* root 北京大学信息学院 版权所有,转载或翻印必究 Page 24
北京大学信息学院 ©版权所有，转载或翻印必究 Page 24 4.3 二叉树的抽象数据类型 //返回current结点的右兄弟 BinaryTreeNode<T>* RightSibling( BinaryTreeNode<T>* current); // 以elem作为根结点，leftTree作为树的左子树, //rightTree作为树的右子树，构造一棵新的二叉树 void CreateTree(const T& elem, BinaryTree<T>& leftTree, BinaryTree<T>& rightTree); //前序周游二叉树或其子树 void PreOrder(BinaryTreeNode<T>* root)； //中序周游二叉树或其子树 void InOrder(BinaryTreeNode<T>* root)；
43二叉树的抽象数据类型 /后序周游二叉树或其子树 void Postorder BinaryTreeNode<t>x root) /按层次周游二叉树或其子树 void LevelOrder(BinaryTreeNode<T>* root) /删除二叉树或其子树 void Delete BinaryTree(BinaryTreeNode<T>k root Si 北京大学信息学院 版权所有,转载或翻印必究 Page 25
北京大学信息学院 ©版权所有，转载或翻印必究 Page 25 4.3 二叉树的抽象数据类型 //后序周游二叉树或其子树 void PostOrder(BinaryTreeNode<T>* root)； //按层次周游二叉树或其子树 void LevelOrder(BinaryTreeNode<T>* root)； //删除二叉树或其子树 void DeleteBinaryTree(BinaryTreeNode<T>* root); };