同济大学计算机编程C++ds6.pptVIP

树和森林的概念 树的定义 树是由 n (n ? 0) 个结点组成的有限集合。如果 n = 0，称为空树；如果 n 0，则 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱； 除根以外的其它结点划分为 m (m ? 0) 个 互不相交的有限集合T0, T1, …, Tm-1，每个集合又是一棵树，并且称之为根的子树。 树的特点 每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。 二叉树遍历 树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 设访问根结点记作 V 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有 前序 VLR 镜像 VRL 中序 LVR 镜像 RVL 后序 LRV 镜像 RLV 中序遍历 (Inorder Traversal) 中序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (V)； 中序遍历右子树 (R)。 遍历结果 a + b * c - d - e / f 前序遍历 (Preorder Traversal) 前序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 访问根结点 (V)； 前序遍历左子树 (L)； 前序遍历右子树 (R)。 遍历结果 - + a * b - c d / e f 后序遍历 (Postorder Traversal) 后序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (V)。 遍历结果 a b c d - * + e f / - 应用二叉树遍历的事例 后序游标类 为记忆走过的结点，设置一个工作栈： S.PopTim = 0, 1或2，表示第几次退栈，用以判断下一步向哪一个方向走。 后序遍历时，每遇到一个结点，先把它推入栈中，让 S.PopTim = 0。 在遍历其左子树前，改结点的 S.PopTim = 1，将其左子女推入栈中。在遍历完左子树后，还不能访问该结点，要继续遍历右子 二叉树的计数 由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。 例, 前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 构造二叉树过程如下： 前序序列 { ABHFDECKG } 线索化二叉树 (Threaded Binary Tree) 通过中序遍历建立中序线索化二叉树 template class Type void ThreadTreeType :: InThread ( ThreadNodeType * current, ThreadNodeType * pre ) { if ( current != NULL ) { InThread ( current-leftChild, pre ); //递归, 左子树线索化 if ( current-leftChild == NULL ) { current-leftChild = pre; current-leftThread = 1; } //建立当前结点的前驱线索 if ( pre != NULL pre-rightChild == NULL ) { pre-rightChild = current; pre-rightThread = 1; } //建立前驱结点的后继线索 pre = current; //前驱跟上当前指针 InThread ( current-rightChild, pre ); //递归, 右子树线索化 } } template class Type void ThreadTreeType :: CreateInThread ( ) { ThreadNodeType *pre = NULL; //前驱指针 if ( root != NULL ) { //非空二叉树, 线索化 InThread ( root, pre ); //中序遍历线索化二叉树