高等教育出版社数据结构C++语言描述朱战立第07章1.ppt

(3)二叉树遍历的实现 template class T void PreOrder(BiTreeNodeT *t, void Visit(T item)) //使用Visit(item)函数前序遍历二叉树t { if(t != NULL) { Visit(t-data); PreOrder(t-Left(), Visit); PreOrder(t-Right(), Visit); } } 为了通用性，把访问操作设计成前序遍历二叉树函数的一个函数虚参 Visit()。 template class T void InOrder(BiTreeNodeT *t, void Visit(T item)) //使用Visit(item)函数中序遍历二叉树t { if(t != NULL) { InOrder(t-Left(), Visit); Visit(t-data); InOrder(t-Right(), Visit); } } ? template class T void PostOrder(BiTreeNodeT *t, void Visit(T item)) //使用Visit(item)函数后序遍历二叉树t { if(t != NULL) { PostOrder(t-Left(), Visit); PostOrder(t-Right(), Visit); Visit(t-data); } } 3.二叉树遍历的应用 (1)二叉树的撤消操作 在释放某个结点的存储空间前必须先释放该结点左孩子结点的存储空间和右孩子结点的存储空间，因此，二叉树撤消操作必须是后序遍历的具体应用。撤消操作函数实现如下： template class T void Destroy(BiTreeNodeT *root) { if((root) != NULL (root)-Left() != NULL) Destroy(root-Left()); ? if((root) != NULL (root)-Right() != NULL) Destroy(root-Right()); ? cout root-data ; //此语句只是为了方便测试 delete root; } (2) 打印二叉树 把二叉树逆时针旋转900C，按照二叉树的凹入表示法打印二叉树。可把此函数设计成递归函数。由于把二叉树逆时针旋转900C后，在屏幕上方的首先是右子树，然后是根结点，最后是左子树，所以打印二叉树算法是一种特殊的中序遍历算法。 template class T void PrintBiTree(BiTreeNodeT* root, int level) //二叉树root第level层结点数据域值的横向显示 { if(root != NULL) //如果二叉树不空 { //二叉树root-Right()第level+1层结点数据域值的横向显示 PrintBiTree(root-Right(), level+1); ? if(level != 0) { //走过6*(level-1)个空格 for(int i = 0; i 6*(level-1); i++) cout ; cout ----; //显示横线---- } cout root-data endl; //显示结点的数据域值 ? //二叉树root-Left()第level+1层结点数据域值的横向显示 PrintBiTree(root-Left(), level+1); } } (3)查找数据元素 在二叉树中查找数据元素操作的要求是：在bt为根结点指针的二叉树中查找数据元素x，若查找到数据元素x时返回该结点的指针；若查找不到数据元素x时返回空指针。 在二叉树bt中查找数据元素x函数可设计成先序遍历函数，此时查找结点的次序是：首先在根结点查找，然后在左子树查找，最后在右子树查找。但是，和常规递归算法不同的是，此函数当一个分支上的结点比较完仍未查找到数据元素x时，要返回到该结点的双亲结点处继续查找。因此，这是回溯算法的一个应用。 实现如下： template class T BiTreeNodeT *Search(BiTreeNodeT *t, T x) { BiTreeNodeT *p; ? if(t == NULL) return NULL; //空二叉树时的查找失败出口 if(t-data == x) return t; //查找成功出口 ? if(t-Left