5.21抽象数据类型 T value( const;∥/返回当前结点的数据 Binary TreeNode<t leftchildo const; ∥返回当前结点左子树 Binary TreeNode<t>* rightchildo const ∥返回当前结点右子树 void setLeftchild Binary TreeNode<t>%) ∥设置当前结点的左子树 void setrightchild Binary TreeNode<t>*) ∥设置当前结点的右子树 void set value(const T& val); ∥设置当前结点的数据域 bool isleaf( const ∥判断当前结点是否为叶结点 Binary TreeNode<t>& operator=-(const Binary TreeNode<t>& node); / 重载赋值操作符 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 5.2.1 抽象数据类型 T value() const; // 返回当前结点的数据 BinaryTreeNode<T>* leftchild() const; // 返回当前结点左子树 BinaryTreeNode<T>* rightchild() const; // 返回当前结点右子树 void setLeftchild(BinaryTreeNode<T>*) ; // 设置当前结点的左子树 void setRightchild(BinaryTreeNode<T>*) ; // 设置当前结点的右子树 void setValue(const T& val); // 设置当前结点的数据域 bool isLeaf() const; // 判断当前结点是否为叶结点 BinaryTreeNode<T>& operator = (const BinaryTreeNode<T>& Node); // 重载赋值操作符 };
521抽象数据类型 【代码52】二叉树的抽象数据类型 template <class t class binary Tree private Binary TreeNode<t> root ∥二叉树根结点 public Binary Treeo root= NULL ∥构造函数 Binary Treeo Delete Binary Tree(root); j ∥析构函数 bool is empty const ∥判定二叉树是否为空树 Binary TreeNode<t>* Root return root ∥返回二叉树根结点 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 5.2.1 抽象数据类型 【代码5.2】 二叉树的抽象数据类型 template <class T> class BinaryTree { private: BinaryTreeNode<T>* root; // 二叉树根结点 public: BinaryTree() {root = NULL;}; // 构造函数 ~BinaryTree() {DeleteBinaryTree(root);}; // 析构函数 bool isEmpty() const; // 判定二叉树是否为空树 BinaryTreeNode<T>* Root(){return root;}; // 返回二叉树根结点
521抽象数据类型 Binary treeNode<t> parent( Binary Tree Node<t>*current) 返回当前结点的父结点 Binary TreeNode<t>* leftSibling Binary TreeNode<t>*current); 返回当前结点的左兄弟 Binary TreeNode<t>* rightSibling( Binary TreeNode<t>*current); ∥/返 回当前结点的右兄弟 void Create Tree(const t& info, Binary Tree< t>& leftTree, Binary Tree<t>& right tree) ∥构造新树 void preorder( Binary TreeNode<T>*root);∥前序周游二又树或其子树 void in order( Binary TreeNode<T>*root)//中序周游二叉树或其子树 void PostOrder Binary TreeNode<T*root);∥后序周游二叉树或其子树 void Levelorder( Binary TreeNode<T>*root);∥按层次周游二叉树或其子树 void Delete Binary Tree(( Binary TreeNode<T*root);∥/删除二叉树或其子树 十一五”国家級规划教材。张铭,王膳腾蛟,赵海燕,《数据结构与算法》,高教社,B08.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 5.2.1 抽象数据类型 BinaryTreeNode<T>* Parent(BinaryTreeNode<T> *current); // 返回当前结点的父结点 BinaryTreeNode<T>* LeftSibling(BinaryTreeNode<T> *current); // 返回当前结点的左兄弟 BinaryTreeNode<T>* RightSibling(BinaryTreeNode<T> *current); // 返 回当前结点的右兄弟 void CreateTree(const T& info, BinaryTree<T>& leftTree, BinaryTree<T>& rightTree); // 构造新树 void PreOrder(BinaryTreeNode<T> *root); // 前序周游二叉树或其子树 void InOrder(BinaryTreeNode<T> *root);// 中序周游二叉树或其子树 void PostOrder(BinaryTreeNode<T> *root);// 后序周游二叉树或其子树 void LevelOrder(BinaryTreeNode<T> *root); // 按层次周游二叉树或其子树 void DeleteBinaryTree(BinaryTreeNode<T> *root); // 删除二叉树或其子树 }；
521抽象数据类型 □所谓二叉树的周游(或称遍历, traversa是指按照 定顺序依次访问树中所有结点,并使得每一结点 仅被访问一次。这里所说的“访问”是指操作,可 以理解成对二叉树结点数据成员的处理,比如输出、 修改结点的信息等。 口周游一棵二叉树的过程实际上就是把二叉树的结 点放入一个线性序列的过程,也就是对二叉树进行 线性化 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 5.2.1 抽象数据类型 所谓二叉树的周游(或称遍历，traversal)是指按照 一定顺序依次访问树中所有结点，并使得每一结点 仅被访问一次。这里所说的“访问”是指操作，可 以理解成对二叉树结点数据成员的处理，比如输出、 修改结点的信息等。 周游一棵二叉树的过程实际上就是把二叉树的结 点放入一个线性序列的过程，也就是对二叉树进行 线性化
522深度优先周游二叉树 基于二叉树的递归定义,这三种深度优先周游的递归定义是 (1)前序法LR次序, preorder traversal。其递归定义是 访问根结点 按前序周游左子树; 按前序周游右子树 (2)中序法(LR次序, inorder traversa。其递归定义是 按中序周游左子树; 访问根结点; 按中序周游右子树。 (3)后序法(LR次序, postordertraversal。其递归定义是 按后序周游左子树; 按后序周游右子树; 访问根结点。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 5.2.2 深度优先周游二叉树 基于二叉树的递归定义，这三种深度优先周游的递归定义是： (1) 前序法(tLR次序，preorder traversal)。其递归定义是 访问根结点； 按前序周游左子树； 按前序周游右子树。 (2) 中序法(LtR次序，inorder traversal)。其递归定义是 按中序周游左子树； 访问根结点； 按中序周游右子树。 (3) 后序法(LRt次序，postorder traversal)。其递归定义是 按后序周游左子树； 按后序周游右子树； 访问根结点