《第9周树和二叉树（下）第2讲-二叉树遍历的应用.pdf》由会员分享，可在线阅读，更多相关《第9周树和二叉树（下）第2讲-二叉树遍历的应用.pdf（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、f(b) f(b- -lchild)f(b- -rchild) N LR 基本思路基本思路 大问题大问题 两个小问题两个小问题 求解过程相似，仅仅是求解过程相似，仅仅是 大小规模的不同大小规模的不同 b 【例例7- -4】假设假设二叉树采用二叉链存储结构二叉树采用二叉链存储结构存储存储，设计，设计一个算一个算 法，计算一棵给定二叉树的所有节点个数。法，计算一棵给定二叉树的所有节点个数。 解：解：计算一棵二叉树计算一棵二叉树b中所有节点个数的递归模型中所有节点个数的递归模型f(b)如下：如下： f(b) f(b- -lchild)f(b- -rchild) N LR f(b)=0若若b=NULL
2、 f(b)=f(b-lchild)+f(b-rchild)+1其他其他情况情况 算 法 思 路 算 法 思 路 int Nodes(BTNode *b) int num1,num2; if (b=NULL) return 0; else return Nodes(b-lchild)+Nodes(b-rchild)+1 提示提示：本例算法本例算法可以基于任何一种遍历算法。可以基于任何一种遍历算法。 对应的递归算法如下：对应的递归算法如下： 先左子树、再右子树，最后根节点（计1）， 是后序遍历的思路。 f(b)=0若若b=NULL f(b)=1若若*b为叶子节点为叶子节点 f(b)=f(b-lch
3、ild)+f(b-rchild)其他情况其他情况 【例例7- -5】假设二叉树采用二叉链存储结构假设二叉树采用二叉链存储结构存储存储，设计，设计一个算一个算 法，计算一棵给定二叉树的法，计算一棵给定二叉树的所有叶子节点个数所有叶子节点个数。 解解：计算一棵二叉树计算一棵二叉树b中所有叶子节点个数的递归模型中所有叶子节点个数的递归模型f(b)如下：如下： f(b) f(b- -lchild)f(b- -rchild) N LR 算 法 思 路 算 法 思 路 int LeafNodes(BTNode *b) int num1,num2; if (b=NULL) return 0; else if
4、 (b-lchild=NULL else num1=LeafNodes(b-lchild); num2=LeafNodes(b-rchild); return (num1+num2); 对应的递归算法如下：对应的递归算法如下： 先左子树、再右子树，最后根节点（计0）， 是后序遍历的思路。 提示提示：同样同样本例算法本例算法可以基于任何一种遍历算法。可以基于任何一种遍历算法。 【例例7- -6】假设二叉树采用二叉链存储结构，设计一个算法把二叉假设二叉树采用二叉链存储结构，设计一个算法把二叉 树树b复制到二叉树复制到二叉树t中。中。 LR t LR b f(b,t)：大问题大问题 f(b- -rc
5、hild,t- -rchild) 小问题小问题 f(b- -lchild,t- -lchild) 小问题小问题 f(b,t) t=NULL若若b=NULL f(b,t) 复制根节点复制根节点*b产生产生*t节点节点;其他其他情况情况 f(b-lchild,t-lchild); f(b-rchild,t-rchild); 其递归模型如下：其递归模型如下： 算 法 思 路 算 法 思 路 void Copy(BTNode *b,BTNode * else t=(BTNode *)malloc(sizeof(BTNode); t-data=b-data;/复制一个根节点复制一个根节点*t Copy(
6、b-lchild,t-lchild); /递归复制左子树递归复制左子树 Copy(b-rchild,t-rchild)；/递归复制右子树递归复制右子树 对应的递归算法如下：对应的递归算法如下： 先根节点、再左子树，最后右子树， 是先序遍历的思路。 【例例7- -7】设二叉树采用二叉链存储结构，设计一个算法把二设二叉树采用二叉链存储结构，设计一个算法把二 叉树叉树b的左、右子树进行交换。要求的左、右子树进行交换。要求不破坏原二叉树不破坏原二叉树。 解：解：本题要求不破坏原有二叉树，实际上就是建立一个新的本题要求不破坏原有二叉树，实际上就是建立一个新的 二叉树二叉树t，它交换了二叉树，它交换了二叉
7、树b的左、右子树。其递归模型如下：的左、右子树。其递归模型如下： f(b,t) t=NULL若若b=NULL f(b,t) 复制复制根节点根节点*b产生产生*t节点节点;其他其他情况情况 f(b-lchild,t-rchild); f(b-rchild,t-lchild); void Swap(BTNode *b,BTNode * else t=(BTNode *)malloc(sizeof(BTNode); t-data=b-data;/复制一个根节点复制一个根节点*t Swap(b-lchild,t-rchild);/递归交换左子树递归交换左子树 Swap(b-rchild,t-lchil
8、d);/递归交换右子树递归交换右子树 对应的递归算法如下：对应的递归算法如下： void Copy(BTNode *b,BTNode * else t=(BTNode *)malloc(sizeof(BTNode); t-data=b-data;/复制一个根节点复制一个根节点*t Copy(b-lchild,t-lchild); /递归复制左子树递归复制左子树 Copy(b-rchild,t-rchild)；/递归复制右子树递归复制右子树 两 个 算 法 比 较 两 个 算 法 比 较 【例例7- -8】假设假设二叉树采用二叉链存储结构二叉树采用二叉链存储结构，设计一个算法设计一个算法 Lev
9、el()求求二叉树二叉树b中中值为值为x的节点的的节点的层次层次（假设所有节点值假设所有节点值唯一唯一）。 设设 Level(b，x，h)返回返回二叉树二叉树b中中data值为值为x的节点的层次，的节点的层次，其其 中中h表示表示b所所指节点的指节点的层数层数。 当在二叉树当在二叉树b中找到中找到data值为值为x的节点，返回其层次（一个大于的节点，返回其层次（一个大于0 的整数）；若没有找到，返回的整数）；若没有找到，返回0。 b b- -lchildb- -rchild 初始调用：初始调用：Level(b，x，1） b指指 向根向根 节点节点 根节根节 点的点的 层次层次 为为1 对于其他
10、情况对于其他情况: :首先在左子首先在左子树中树中找。若找到找。若找到了直接返回。了直接返回。 b b- -lchildb- -rchild 空二叉树中空二叉树中找不到值为找不到值为x的节点的节点Level(b，x，h)=0 若若b=NULL 若若b指向指向值为值为x的节点的节点Level(b，x，h)=h 若若b-data=x 因为假设“因为假设“h表示表示b所指节点所指节点的层次”的层次” 否则否则返回在右返回在右左子左子树中的查找结果。树中的查找结果。 Level(b,x,h)=l 当当l=Level (b-lchild,x,h+1)0 Level(b,x,h)=Level(b-rchi
11、ld,x,h+1) 其他情况其他情况 递归递归模型模型f(b，x，h)如下：如下： int Level(BTNode *b,ElemType x,int h) /找到找到*p节点后节点后h为其层次为其层次,否则为否则为0 if (b=NULL) return 0;/空树时返回空树时返回0 else if (b-data=x) return h;/找到节点时找到节点时 else l=Level(b-lchild,x,h+1);/在左子树中查找在左子树中查找 if (l=0)/左子树中未找到时在右子树中查找左子树中未找到时在右子树中查找 return Level(b-rchild,x,h+1);
12、else return l; 注意：注意：基于基于先序遍历先序遍历算法思想。算法思想。 对应的递归算法如下：对应的递归算法如下： 【例例7-10】假设二叉树采用二叉链存储结构，设计一个算法假设二叉树采用二叉链存储结构，设计一个算法 输出从根节点到每个叶子节点的逆路径。输出从根节点到每个叶子节点的逆路径。 A BC DE G F 例如：例如： 解：解：设计的队列为非环形队列设计的队列为非环形队列qu，将所有已访问过的节点指针进，将所有已访问过的节点指针进 队，并在队列中保存双亲节点的位置。队，并在队列中保存双亲节点的位置。 说明：说明：类似于用队列求解迷宫问题。类似于用队列求解迷宫问题。 当找到一个叶子节点时，在队列中通过双亲节点的位置输出当找到一个叶子节点时，在队列中通过双亲节点的位置输出 根节点到该叶子节点的逆路径。根节点到该叶子节点的逆路径。 struct snode BTNode *node;/存放当前节点指针存放当前节点指针 int parent;/存放双亲节点在队列中的位置存放双亲节点在队列中的位置 quMaxSize;/定义非环形队列定义非环形队列 int front = rear = -1;/置队列为空队列置队列为空队列 对应算法如下：对应算法如下： 本讲完本讲完