第07章2-自定义数据类型.ppt

《第07章2-自定义数据类型.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7.4二叉树类二叉树类设计如下：templateclassBiTree{private:BiTreeNode*root;//根结点指针voidDestroy(BiTreeNode*&t);voidPreOrder(BiTreeNode*&t,void(*Visit)(Titem));voidInOrder(BiTreeNode*&t,void(*Visit)(Titem));voidPostOrder(BiTreeNode*&t,void(*Visit)(Titem));public:BiTree(

2、void):root(NULL){};//构造函数~BiTree(void){};//析构函数//构造二叉树voidMakeTree(constTitem,BiTree&left,BiTree&right);voidDestroy(void);//撤消二叉树voidPreOrder(void(*Visit)(Titem));//前序遍历voidInOrder(void(*Visit)(Titem));//中序遍历voidPostOrder(void(*Visit)(Titem));//后序遍历};templatevo

3、idBiTree::MakeTree(constTitem,BiTree&left,BiTree&right)//构造数据域为item左子树为left右子树为right的二叉树{root=newBiTreeNode(item,left.root,right.root);}templatevoidBiTree::Destroy(void)//撤消二叉树{Destroy(root);}设计说明：（1）和单链表类似，一个二叉链结构的二叉树也可以由指向该二叉树的根指针表示，所以，二叉树类的成员变量为指向该二

4、叉树的根指针root，root设计为私有访问权限（2）撤消操作是一个递归执行过程，需要通过递归调用来实现，而递归调用时需要给出每次调用时的参数，因此，撤消成员函数也设计了两个，公有的撤消成员函数没有参数，私有的撤消成员函数带一个参数，公有的撤消成员函数通过调用私有的撤消成员函数实现二叉树的撤消。（3）二叉树是递归定义的，即二叉树是由根结点和左右子二叉树构成的，所以，按照上述方法建立二叉树的撤消过程不能通过析构函数来实现，因为如果二叉树首先通过自动调用析构函数撤消后，则意味着包含在该二叉树中的所有子二叉树也已被撤消，则子二叉树对象再自动调用析构函

5、数撤消子二叉树时就会出错。7.5二叉树的分步遍历二叉树的遍历有两种情况，一种是一次性遍历；另一种是分步遍历。分步遍历是指在规定了一棵二叉树的遍历方法后，每次只访问当前结点的数据域值，然后使当前结点为当前结点的后继结点，直到到达二叉树的最后一个结点为止。分步遍历方法提供了对二叉树进行循环遍历操作的工具。1.二叉树遍历游标类为满足分步遍历操作的需要，我们引入了二叉树遍历游标类。使用纯虚函数和抽象类方法，把二叉树遍历游标类设计为抽象类形式的基类，把二叉树中序遍历游标类、二叉树前序遍历游标类、二叉树后序遍历游标类和二叉树层序遍历游标类设计为该基类的派生

6、类，这样，一方面对于派生类中共同的成员变量和成员函数可一次性设计完成，另一方面，各种不同的二叉树遍历游标类由于都是基类的派生类，所以其遍历的控制过程完全相同，从而可方便使用和维护。2.二叉树中序遍历游标类二叉树的中序递归遍历算法是算法本身的不断自调用实现的，所以中序递归遍历算法是不可分解的。若借助一个堆栈模仿系统的运行时栈，非递归的二叉树中序遍历算法如下：（1）设置一个堆栈并初始化；（2）使临时指针等于二叉树根结点指针，如二叉树根结点不空令结束标记为0；否则为1；（3）当临时指针的左孩子结点指针不空时循环；否则转向步骤（4）；（3.1）把临时指

7、针入堆栈；（3.2）临时指针等于临时指针的左孩子结点指针；（4）如果临时指针不存在则令结束标记为1；（5）如果结束标记为1转步骤（8）；否则继续执行；（6）访问临时指针所指的结点；（7）如果临时指针的右孩子结点指针不空则使临时指针等于临时指针的右孩子结点指针，转到步骤（3）；否则如果堆栈不空则退栈使临时指针等于栈顶结点指针，转向步骤（5）；否则令结束标记为1，转向步骤（5）；（8）算法结束。下图给出了上述算法的一个有5个结点二叉树例子的上述算法执行过程ADECB&B&At(a)中序遍历的第一个结点访问DADECB&At访问B堆栈堆栈ADECB&

8、At(c)下一个结点访问E堆栈ADECBt(d)下一个结点访问AADECB(e)下一个结点堆栈堆栈ADECB(f)结束标记等于1堆栈t访问Ct=NUL