43二叉树的抽象数据类型 43二叉树的抽象数据类型 又树的抽象数据类型的C++定义 BinaryTree,没有 具体规定该抽象数据类型的存储方式 BinaryTree //构造函数 template <class t> bool isEmpty( const 判定二叉树是否为空树 class BinaryTree t /返回二叉树根结点 private eeNode<T>* Root; /返回 current结点的父结点 /二叉树根结点指针 BinaryTreeNode<T>* Parent(Binary TreeNode<T>* Binary TreeNode<T>* root; /返回 current结点的左兄弟 Binary TreeNode<T>*curre 张写 43二叉树的抽象数据类型 43二叉树的抽象数据类型 /返回 current结点的右兄弟 /后序周游二叉树或其子树 BinaryTreeNode<T>* current) void Postorder(BinaryTreeNode<T>* root); /以eem作为根结点, leftTree作为树的左子树 ∥/ rightTree作为树的右子树,构造一橾新的二叉树 /按层次周游二叉树或其子树 void CreateTree(const T& elem, void LevelOrder( BinaryTreeNode<T>k root); BinaryTree<T>& rightTree) /删除二叉树或其子树 //前序周游二叉树或其子树 void Delete BinaryTree(BinaryTreeNode<T>* /中序周游二叉树或其子树 id Inorder(Binary Treenode <t>* root): 张鲁写 前有,聊脂究 44周游二叉树 44周游二叉树 ■周游 ■二叉树周游 ■系统地访问数据结构中的结点 441深度优先周游二叉树 ■每个结点都正好被访问到一次 ■二叉树的结点的线性化 442非递归深度优先周游二叉树 44.3广度优先周游二叉树 真大_血单 大息4 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 4.3 二叉树的抽象数据类型 „ 二叉树的抽象数据类型的C++定义BinaryTree，没有 具体规定该抽象数据类型的存储方式 template <class T> class BinaryTree { private: //二叉树根结点指针 BinaryTreeNode<T>* root; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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); 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 21 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)； 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 22 4.3 二叉树的抽象数据类型 //后序周游二叉树或其子树 void PostOrder(BinaryTreeNode<T>* root)； //按层次周游二叉树或其子树 void LevelOrder(BinaryTreeNode<T>* root)； //删除二叉树或其子树 void DeleteBinaryTree(BinaryTreeNode<T>* root); }; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 23 4.4 周游二叉树 „ 周游 „ 系统地访问数据结构中的结点 „ 每个结点都正好被访问到一次 „ 二叉树的结点的线性化 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 24 4.4 周游二叉树 „ 二叉树周游 „ 4.4.1 深度优先周游二叉树 „ 4.4.2 非递归深度优先周游二叉树 „ 4.4.3 广度优先周游二叉树