第六章 算法.docVIP

二叉树的操作 二叉树的建立 二叉链表的存储结构，对应的结点类型定义： 利用完全前序序列建立二叉树 【解析】如上图所示的二叉树的完全前序序列为：AB?C??D?EF???(?用空格表示)，可按照完全前序序列建立二叉链表。 【算法】 或者写成： 利用前序和中序序列建立二叉树（利用中序和后序序列建立二叉树） 【解析】假设二叉树的每个结点值为单个字符，且没有相同值，则由前序（先序）序 列和中序序列可以确定二叉树。假设对二叉树进行遍历的前序序列和中序序列已经分别存储在pre和in两个数组中，n为二叉树的结点数。 【算法1】利用前序和中序序列建立二叉树 【算法2】利用中序和后序序列建立二叉树 建立二叉树链表的每个结点，对其数据域赋值，在更改每个结点的左右孩子指针信息（适合结点少的情况） 类似的题目 有n个结点的完全二叉树存放在一维数组A[1..n]中，请建立一棵用二叉链式表示的二叉树，根由b指向。 二叉树的遍历 层次遍历（用队列） 假设二叉树采用二叉链表作为存储结构，求按层次顺序遍历二叉树的算法。 【解析】使用队列qu [ ]，先将二叉树的根结点入队。当队列不空时做下列循环：从队列中取出一个结点，访问之，同时将其不空的左和右孩子入队。 【算法】 深度遍历（递归） 1)前序遍历（先序遍历） 【解析】如果二叉树为空树，则什么都不做； 否则： （1）访问根结点 （2）先序遍历左子树 （3）先序遍历右子树 【算法1】递归 【算法2】非递归 二叉树的的遍历的递归算法中都用到了系统栈，我们要写出遍历的非递归算法，则必须用自己申请的栈来代替系统栈的功能。系统栈在遍历过程中起到什么作用呢？ 上图的这棵二叉树，对其进行先序遍历，可得遍历序列ABCED，我们可以看到在访问B结点的下一个结点是C结点，但是B结点的另一个分支结点（孩子）E结点还没有访问，所以我们要保存B结点的位置信息，待C结点访问完以后在返回B结点继续遍历它的另一个结点E。这就是系统栈在遍历中起到的作用，这里利用了栈的记忆特性。 对上图进行先序遍历，各个结点进栈和出栈的情况如下： 初态为空 结点A进栈； 出栈，输出栈顶元素A，并将A的右、左孩子结点（B和D）入栈；右孩子先入栈，左孩子后入栈，因为对左孩子的访问要先于右孩子； 出栈，输出栈顶元素B，并将B的右、左孩子结点（E和C）入栈； 出栈，输出栈顶元素C，因为C是叶子结点，所以没有结点入栈； 出栈，输出栈顶元素E，因为E是叶子结点，所以没有结点入栈； 出栈，输出栈顶元素D，因为D是叶子结点，所以没有结点入栈； 栈空，进入终态。 2)中序遍历 【解析】如果二叉树为空树，则什么都不做； 否则： （1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树 【算法】 3)后序遍历 【解析】如果二叉树为空树，则什么都不做； 否则： （1）后序遍历左子树 （2）后序遍历右子树 （3）访问根结点 【算法】 深度遍历（非递归） 1)前序遍历 2)中序遍历 【解析】递归的深度遍历算算法用到系统栈来解决问题，如果要写非递归的算法，就要自己申请栈来代替系统栈的功能。 3)后序遍历 类似算法： 求data域值为x的结点，并返回指向该结点的指针 在一棵以二叉链表为存储结构的二叉树中，查找data域值等于key的结点是否存在，如果存在则将指针p指向该结点，否则p的赋值为NULL。 【解析】任意选取一种遍历方式来访问二叉树即可，这里选取先序遍历方式。 【算法】 求二叉树结点*p的左孩子结点和右孩子结点 假设二叉树以二叉链表表示，找出树中一个非根结点（由指针p指向），并求它的兄弟结点（用指针q指向；如果没有兄结点，则q为空）。 【解析】先采用某种遍历方式（例如用先序遍历）找出*p的双亲结点，再求*q结点 【算法】 求二叉树的结点总数 假设二叉树采用二叉链式存储结构，设计一个算法给出一棵二叉树的结点总数。 【解析】方法1：在函数中设置一个变量，初值为0，采用任意遍历方式访问此二叉树，每访问一个结点，变量就增1，这样可以得到结点总数。 方法2：如果这是一棵空树，则结点总数为0，否则结点总数等于左子树的结点数n1，加上右子树的结点数n2，再加上1（即n1+n2+1）。 【算法1】 【算法2】 求二叉树的叶子总数 假设二叉树采用二叉链式存储结构，设计一个算法给出一棵二叉树的叶子总数。 【解析】在上一题的基础上，加上叶子的特点即可，叶子就是左右子树均为空的结点。 【算法1】 【算法2】 二叉树结点的插入 二叉树结点的删除 求二叉树的高度（递归与非递归