数据结构3(树形结构).pptVIP

裂项法求解数列。 * 非递归实现：中序遍历 思想 遇到一个节点，就把它推入栈中，并去遍历它的左子树；注意：此时不访问 遍历完左子树后，从栈顶托出这个节点并访问之，然后按照它的右链接指示的地址再去遍历该节点的右子树。 节点扩展标记位 在二叉树node结构里增加1个标记位tag记录该节点状态，初始时：tag=0。 tag=0，表示左子树未访问； tag=1，表示左子树已经访问，该访问自己了。 data Rchild Lchild tag typedef struct BiTNode { 　　　ElemType data; 　　　struct BiTNode *Lchild, *Rchild; // 左、右孩子指针 int tag=0; 　　} *BiTree;  非递归实现：中序遍历伪代码 非递归实现：后序遍历 思想 遇到一个节点，把它推入栈中，遍历它的左子树； 遍历结束后，还不能马上访问处于栈顶的该节点，而是要再按照它的右链接结构指示的地址去遍历该节点的右子树； 遍历遍右子树后才能从栈顶托出该节点并访问之。 tag语义略微发生变化 tag=0，表示左右子树均未访问； tag=1，表示左子树已经访问，该访问右子树了； tag=2，表示左右子树均已经访问，该访问自己了。 非递归实现：后序遍历伪代码 树遍历非递归算法总结 非递归算法的写法有很多种，我们只是用统一的框架来描述了这三种遍历 进栈出栈操作，出栈过程，我们根据需要设置标记位来表明该节点的左(或右)子树是否被遍历。 希望同学们理解并熟记该框架，很多应用问题只需要改变Visit(p)操作就可以实现。 二叉树遍历应用举例(1) 统计二叉树中叶子节点的数量 容易想到，实现这个操作只要对二叉树遍历一遍，并在遍历过程中对叶子节点计数即可。显然这个遍历的次序可以随意，即先序或中序或后序均可，只是为了在遍历的同时进行计数，需要在算法的参数中设一个计数器。 统计二叉树中非叶子节点的数量 void CountLeaf (BiTree T, int count) 　{ 　　// 先序遍历二叉树，以 count 返回二叉树中叶子节点的数目 　　if ( T ) { 　　　if ((!T-Lchild) (!T-Rchild)) 　　　　count++; 　　　　　　　　　　　　　// 对叶子节点计数 　　　　CountLeaf( T-Lchild, count); 　　　　CountLeaf( T-Rchild, count); 　　} // if 　} // CountLeaf  二叉树遍历应用举例(2) 求二叉树的深度和高度 任何遍历均可，每下去一层，深度加1，但是，注意，将当前最大深度保存下来。 int maxdepth=-1; //当前最大深度 void BiTreeDepth(BiTree T, int depth) 　{ 　　// T指向二叉树的根，depth 为 T 所指节点所在层次，初值为0 　　if (T){ 　　　if (depthmaxdepth) maxdepth=depth; 　　　BiTreeDepth(T-Lchild, depth+1); 　　　BiTreeDepth(T-Rchild, depth+1); 　　}// if 　}// BiTreeDepth //全局变量maxdepth最终保存的就是树的深度 二叉树遍历应用举例(3)-1 输出二叉树中每一棵树中从根到所有叶子节点的路径 从树的根节点出发，沿着各个分支可以到达所有叶子节点，由途径所有节点构成的节点序列称为从根到叶的路径，途径分支个数称作路径长度； 用递归算法就很难实现了，因为，递归算法不保存中间状态。 输出路径： A D F A D G K 二叉树遍历应用举例(3)-2 回忆后序遍历的非递归算法 当Visit(p)时，p的节点的所有祖先一定都在栈中，因为，后序决定子节点在父节点之前被访问，因此，p被访问时，他的所有父节点都未被访问，因此，必然在栈中。 据此，我们很容易修改Visit(p)函数解决这一问题： 判断p是否为叶节点，即p-Lchild==NULL p-Rchild==NULL，若是，反序打印栈中所有节点，即为根到p的路径。 留为作业，请同学们至少写出伪代码，最好上机验证。 广度优先遍历二叉树 上述三种遍历本质上是深度优先遍历。 广度优先遍历：从二叉树的第一层（根节点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对节点逐一访问。 例如：ABCDEFGHI 广度优先遍历实现方式 广度优先遍历没有递归实现方法，非递归实现依赖于队列 下一章，图的广度遍历也是如此！ 广度优先遍历二叉树：伪代码 与先序遍历非递归代码比较，区别有哪些？ 提纲 二