题目:输入一个整数和一棵二叉树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出节点和等于输入整数的所有路径。
例如 输入整数22和如下二叉树
10
/ \
5 12
/\
4 7
则打印出两条路径:10, 12和10, 5, 7。
二叉树节点的数据结构定义为:
struct BinaryTreeNode //二叉树节点结构
{
int m_nValue;
BinaryTreeNode *m_pLeft;
BinaryTreeNode *m_pRight;
};
源码:(可以运行,但是还有些问题没搞明白……持续更新中)
#include "stdio.h"
#include "malloc.h"
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
//打印路径
void printPath(BinaryTreeNode *path);
/**
*sum为要求的整数和
*curSum为从根节点到tree父节点,路径上所有数的和
*path指向当前路径的最后一个节点,该路径有BinaryTreeNode组成双向链表
*m_pRight指向路径下一节点,m_pLeft指向上一节点
**/
void searchPath(BinaryTreeNode *tree,BinaryTreeNode *path,int curSum,int sum)
{
curSum += tree->m_nValue;
if(curSum>sum)//路径值已经大于所求和,返回
return;
//如果没有返回 说明 当前值<输入值
BinaryTreeNode *root=new BinaryTreeNode();
//BinaryTreeNode *root=(BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
// root=NULL;
root->m_nValue=tree->m_nValue;
//将当前节点的值加入到路径中
if(path==NULL)//第一次加入
path=root;
else
{
path->m_pRight=root;
root->m_pLeft=path;
path=root; //采用尾插法,标记的是尾部
}
//如果 当前值=输入值
if(curSum==sum)
{
//路径结束且和=sum,为所求
if(tree->m_pLeft==NULL&&tree->m_pRight==NULL)
{
//获得路径头节点,用于打印
while(path->m_pLeft)
path=path->m_pLeft;
printPath(path);
}
//若当前路径的和=sum,但路径还未到达叶节点,此路径不可行
//delete node;
//free(node);
//node=NULL;
return;
}
//curSum<sum,继续搜寻路径
if(tree->m_pLeft!=NULL)
searchPath(tree->m_pLeft,path,curSum,sum);
if(tree->m_pRight!=NULL)
searchPath(tree->m_pRight,path,curSum,sum);
//delete node;
// free(node);
//node=NULL;
}
void printPath(BinaryTreeNode *path)
{
while(path)
{
printf("%5d",path->m_nValue);
//cout<<path->m_nValue<<" ";
path=path->m_pRight;
}
printf("\n");
//cout<<endl;
}
int main()
{
BinaryTreeNode *root=NULL;
BinaryTreeNode node10;
node10.m_nValue=10;
BinaryTreeNode node5;
node5.m_nValue=5;
BinaryTreeNode node12;
node12.m_nValue=12;
BinaryTreeNode node4;
node4.m_nValue=4;
BinaryTreeNode node7;
node7.m_nValue=7;
node10.m_pLeft=&node5;
node10.m_pRight=&node12;
node5.m_pLeft=&node4;
node5.m_pRight=&node7;
node12.m_pLeft=node12.m_pRight=NULL;
node4.m_pLeft=node4.m_pRight=NULL;
node7.m_pLeft=node7.m_pRight=NULL;
root=&node10;
//BinaryTreeNode *path=(BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
BinaryTreeNode *path=NULL;
printf("搜寻值为22的路径有如下几条:");
searchPath(root,path,0,22);
}
分享到:
相关推荐
02第三章第四章D30-p59.ram 03第五章第五章P60-P85.rar 04第六章第章第八章P85-P8113.ram 05第九章第十章p114-P137.rar 06第十章第章P138-P165.rar 07第十■章第十■章D165-P185.ram 08第十三章第十四章p186-P218....
微软等公司数据结构+算法面试100题之第41-60题答案 --- 答案V0.4版 My Blog:http://blog.csdn.net/v_JULY_v 微软等100题系列,整理资源下载地址:题目系列: 1.[最新整理公布][汇总II]微软等数据结构+算法面试100...
02 第三章 第四章P30-P59 03 第五章 第五章P60-P85 04 第六章 第七章第八章P85-P8113 05 第九章 第十章P114-P137 06 第十一章 第十二章P138-P165 07 第十二章 第十二章P165-P185 08 第十三章 第十四章P186-P218 09 ...
5. **旋转与角度**:第4题和第13题涉及到图形的旋转,如逆时针旋转90度,并结合图形的变化来推断下一个图形。 6. **颜色合并**:第5题中,异色相加为黑,同色相加为白,考察颜色的组合规则。 7. **线条计算**:第6...
根据提供的信息,我们可以总结出这份文档包含了从第41题到第60题的数据结构与算法面试题目。这些题目是从微软等知名公司的面试题目中精选出来的,并由原作者进行了整理和发布。以下是对这些题目的详细解读: ### 第...
第四题是一个日期转换问题,要求根据输入的年、月、日计算出这是当年的第几天。程序通过处理不同月份天数的特殊情况,如2月的闰年情况,以及累加前几个月的天数来实现计算功能。 这些题目展示了C语言的基础应用,如...
【运筹学习题答案 (第四版)】 运筹学是一门应用广泛的数学学科,它主要研究如何通过优化方法解决实际问题。第四版的运筹学习题答案提供了对一系列运筹学理论与方法的实践应用解析,帮助学生和研究人员理解并掌握...
* 问题描述:有四个数字:1、2、3、4,能组成多少个互不相同且无重复数字的三位数?各是多少? * 解决方案:使用遍历方法遍历全部可能,并将有重复的剃掉。也可以使用 itertools 中的 permutations 方法。 实例 002...
第4题 函数fun的功能是统计在tt字符串中"a"到"z"26各字母各自出现的次数,并依次放在pp所指的数组中。知识点: * 字符串的使用 * switch语句的使用 * 数组的使用 * 字符的判断 第5题 函数fun的功能是将大于整数m且...
高中联赛难度几何题100道(精华双图版) 本资源包含100道高中联赛难度的几何题,涵盖圆、线、角、点等基本几何元素的性质和关系。本资源可以帮助学生深入理解几何知识,提高解题能力和空间想象力。 知识点: 1. ...
4. **第四题**:这个题目要求统计字符串中每个小写字母出现的次数。它使用了字符数组、计数器和`switch`语句。在C语言中,字符串是以`\0`结尾的字符数组,`switch`语句则用于根据不同的字符执行相应的计数操作。 5....
在第四题中,利用了圆的外切三角形和对称性的知识,来证明AP是三角形PCK外接圆的切线。这需要对圆的性质有深入的理解。 第五题中,证明了KG垂直于BG,这一过程中用到了圆内接四边形的性质以及角度的对称性。这说明...
南开100题是针对计算机三级网络技术机试的一个复习资料集,它包含了过去考试中出现过的实际题目。这些题目旨在帮助考生熟悉考试内容和题型,提高备考效率。 ### 2. 题目分类 题目分为两大类:带有特殊标记的题目...
python 面试宝典 100 题 本资源为 python 面试宝典,共收录 100 道题目,涵盖了 python 语言的多个方面,从基础知识到高级应用,覆盖了 python 开发者在实际工作中常见的问题和挑战。本资源适合 python 开发者、...
4. 乘法和倍数关系:第4题中,桌子的价格是椅子的3倍,需要计算总价格。 5. 平均数概念:第5题求平均每层放多少本书,需要将总数除以层数。 6. 工作效率:第6题涉及工作效率的乘法运算,计算两人合作完成的总量。 7....
4. "大方之家"是指懂得大道理的人,并非指慷慨大方,因此第四题使用不当。 5. "江河日下"形容事物逐渐衰落,第五题中误用,应理解为环境恶化。 6. "炙手可热"形容权势显赫,第六题中用于"规范化"讨论,用词不妥。 7....
这份文档是针对冀教版三年级英语下册第四单元的一份精选测试题,旨在评估学生对本单元英语知识的掌握情况。测试题分为听力和笔试两大部分,共计100分,时间为40分钟。 听力部分主要考察学生的听力理解和快速反应...
背题当然就是背前面说的南开100题啦,其实虽然号称100题,也不过10多个题型而已,这个在我提供的下载地址里已经分好类别了。把这些题型背下来就可以了;网络上有精简版以及笔者的背诵版可供参考。背诵要在理解的基础...
第十四届蓝桥杯EDA赛模拟题一 第十四届蓝桥杯EDA赛模拟题二 第十四届蓝桥杯EDA省赛真题 第十五届蓝桥杯EDA赛模拟试题一(嘉立创EDA提供) 第十五届蓝桥杯EDA赛模拟试题二(嘉立创EDA提供) 4T十五届模拟三