第六章二叉树续.ppt

现在我们使用从左子结点开始寻找替换的结点，如果删除的结点是5，从结点5的左子结点3开始往右子树找，直到到达叶结点，找到的是叶结点4. 接着删除此叶结点，其方法和情况1、2相同，最后取代原结点5成为4. 如果删除的是结点3，此时左子结点2并没有右子结点，所以符合条件的就是结点2.删除的操作就成为删除一个没有右子树的结点2，然后将原结点3的值取代成为2.其完整的图形为： * * 程序实例：7_7.c 使用递归创建一棵二叉树，然后输入一个结点值后，使用二叉查找方式寻找结点，如果找到，就调用删除函数将结点删除，最后输出删除的结果。原二叉树为如下图形： * 6.8 二叉树的复制 在二叉树的使用上常常需要备份原来的二叉树，可以使用递归的方法复制二叉树。 复制函数使用和二叉树遍历相似的递归调用。 * 程序实例：7_8.c 使用递归方式创建二叉树，然后备份原来的二叉树，最后将原来的二叉树和备份的二叉树都输出出来。 程序说明：函数copybtree( )先创建左子树，然后创建右子树。 * 6.9 线索二叉树 在重新考虑前面说明的二叉树链表结构表示法，可以看出左右指针指向NULL的情况比实际有使用的情形还多。 所以A.J.Perlis与C.Thronton两位就把这些空的指针使用线索方式取代，称为“线索二叉树”（Threaded Binary Tree） 例如：现在有一棵二叉树，下图所示： * 上述二叉树中序遍历的结果，如下所示 1,2,3,4,5,6,7,8,9 线索的使用方法是当右子树是空的时，将指针指向中序遍历时的下一个结点。 左子树为空时，就指向中序遍历的前一个结点。如图所示： * 上图的虚线就是线索。叶结点3没有右子树，所以右线索指向中序遍历的下一个结点4. 同时也没有左子树，所以左线索指向中序遍历的前一个结点2， 其他各个结点的处理方式相同。 除了结点1和9的这两条线索刚好是中序遍历的第一个和最后一个结点，此时线索无法设置，解决的方法是使用头结点，后面会详细说明。 * 线索二叉树的结点结构，除了原有的二叉树的字段外，为了区分线索和实际指针的不同，必须额外加上两个字段标示指针的用途。如下图所示： * 上述字段leftthread和rightthread是表示指针left和right的用途，如果1表示是线索，若是0就是实际的指针。完整的结构声明如下： struct t_tree { int data; int leftthread; int rightthread; struct t_tree *left; struct t_tree *right; } typedef struct t_tree treenode; typedef treenode * t_btree; rightthread; * 接着我们可以看看头结点表示法是如何解决线索无法设置的问题。 例如：一线索二叉树为空的时候，其头结点的结构如图所示。 * 在线索二叉树加上头结点后，线索二叉树的结构如图所示： * 上图的结点1和9可以把线索指向头结点。现在有了线索的指针，原来的中序遍历就不需要使用递归。只需使用一个循环就可以完成，因为线索二叉树的创建策略正是中序遍历的顺序。中序遍历的策略，如下所示： 如果任何结点的右指针不是线索，就需要从右子结点为起点，沿着左子树的路径往下直到左指针是线索为止。 例如：从头结点看来，其右指针不是线索，此时由其右子结点5开始沿着左子树的方向走。当走到结点1时，符合左指针为线索的条件，此时找到中序遍历的结点1. * 如果任何结点的右指针是线索，线索所指的结点就是下一个中序遍历的结点。 例如：从上面的结点1，因为其右指针是线索，所以下一个中序遍历的结点就是结点2. 重复上述的操作可以完成二叉树的中序遍历。至于创建线索二叉树的方法，只是跟踪整个遍历的走向记录其中序遍历的前后结点，然后链接各个结点线索。 * 程序实例 7_9.c 使用数组值创建线索二叉树，然后使用中序遍历方式将二叉树的内容输出来。 程序说明： 函数insertnode（）可以插入一个结点到线索二叉树。 函数createbtree（）是创建线索二叉树的循环。 * * 输出结果 * 程序说明 本程序并没有完全输出整个二叉树 函数printbtree（）只是使用循环遍历二叉树。 所以显示的只是二叉树的一条分支，而无法输出完整的二叉树结点。 如需完整输出整棵树，就需要借助递归技巧，详细说明请参看下一节二叉树的遍历。 * * 6.4 二叉树的遍历（续） 线性数据结构的数组和链表都只能从头至尾或从尾至头的遍历。 但是二叉树的遍历就比较复杂 二叉树的每一个结点都可以分成左右两个分支。如果把它视为一张公路图，此时的每个结点都是岔路可以选择往左或往右走。 当然如果结点没有左子树或