43二叉树的抽象数据类型 /返回 current结点的右兄弟 BinaryTreeNode<t>* Rightsibling( BinaryTreeNode<T>* current) /以eem作为根结点, lefttree作为树的左子树, // rightTree作为树的右子树,构造一棵新的二叉树 void Create Tree( const T& elem, BinaryTree<T>& leftTree Binary tree<T>& rightTree); //前序周游二叉树或其子树 void PreOrder(Binary TreeNode<T>* root); /中序周游二叉树或其子树 void InOrder BinaryTreeNode<T>* root); 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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)；
43二叉树的抽象数据类型 /后序周游二叉树或其子树 void Postorder(Binary TreeNode<T>* root); /按层次周游二叉树或其子树 void LevelOrder(Binary TreeNode<T>k root); //删除二叉树或其子树 void Delete BinaryTree BinaryTreeNode<T>* rooti 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 22 4.3 二叉树的抽象数据类型 //后序周游二叉树或其子树 void PostOrder(BinaryTreeNode<T>* root)； //按层次周游二叉树或其子树 void LevelOrder(BinaryTreeNode<T>* root)； //删除二叉树或其子树 void DeleteBinaryTree(BinaryTreeNode<T>* root); };
44周游二叉树 ■周游 ■系统地访问数据结构中的结点 每个结点都正好被访问到一次 二叉树的结点的线性化 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 23 4.4 周游二叉树 周游 系统地访问数据结构中的结点 每个结点都正好被访问到一次 二叉树的结点的线性化
44周游二叉树 ■二叉树周游 441深度优先周游二叉树 442非递归深度优先周游二叉树 443广度优先周游二叉树 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 24
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 24 4.4 周游二叉树 二叉树周游 4.4.1 深度优先周游二叉树 4.4.2 非递归深度优先周游二叉树 4.4.3 广度优先周游二叉树
深度优先周游二叉树 变换根结点的周游顺序,得到三种方案: ①前序周游(tR次序):访问根结点;前 序周游左子树;前序周游右子树。 ②中序周游(LtR次序):中序周游左子 树;访问根结点;中序周游右子树。 ③后序周游(LRt次序):后序周游左子 树;后序周游右子树;访问根结点。 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 。2
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 25 深度优先周游二叉树 变换根结点的周游顺序，得到三种方案： ① 前序周游(tLR次序)：访问根结点；前 序周游左子树；前序周游右子树。 ② 中序周游(LtR次序)：中序周游左子 树；访问根结点；中序周游右子树。 ③ 后序周游(LRt次序)：后序周游左子 树；后序周游右子树；访问根结点