C++实现查找二叉树中和为某一值的所有路径的示例
更新时间:2020年4月25日 17:36 点击:1552
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如 输入整数22和如下二元树
则打印出两条路径:10, 12和10, 5, 7。
先序遍历树即可得到结果。
算法: FindPath(BTree * root,int sum,int target,Stack * s) 用来计算,sum为栈中的元素的和,target为目标值。
到达一个节点之后计算当前节点和sum的和,如果为target,输出路径返回,如果大于target,则直接返回,如果小于,则将当前节点的值入栈,更新sum的值,继续遍历,遍历完成之后,也就是从当前节点返回的时候,将其从栈中弹出,更新sum
代码如下(GCC编译通过):
#include "stdio.h" #include "stdlib.h" #define MAXSIZE 8 typedef struct node { int data; struct node * left; struct node * right; }BTree; typedef struct { int top; int data[MAXSIZE]; }Stack; BTree * CreatTree(int a[],int n); void Iorder(BTree * root); void Porder(BTree * root); void FindPath(BTree * root,int sum,int target,Stack * stack); void InitStack(Stack * stack); void Push(Stack * s,int val); int Pop(Stack *s); int main(void) { int array[MAXSIZE] = {5,3,8,7,2,4,1,9},target; BTree * root; Stack stack; target = 12; root = CreatTree(array,MAXSIZE); InitStack(&stack); printf("二叉树内元素升序排列:"); Iorder(root); printf("\n"); printf("目标值:%d,路径:",target); FindPath(root,0,target,&stack); printf("\n"); return 0; } //根据数组生成二叉排序树 BTree * CreatTree(int a[],int n) { BTree * root ,*p,*cu,*pa; int i; root = (BTree *)malloc(sizeof(BTree)); root->data = a[0]; root->left = root->right =NULL; for(i=1;i<n;i++) { p = (BTree *)malloc(sizeof(BTree)); p->data = a[i]; p->left = p->right =NULL; cu = root; while(cu) { pa = cu; if(cu->data > p->data) cu = cu->left; else cu = cu->right; } if(pa->data > p->data) pa->left = p; else pa->right = p; } return root; } //中根遍历,打印二叉树 void Iorder(BTree * root) { if(root) { Iorder(root->left); printf("%3d",root->data); Iorder(root->right); } } //寻找路径 void FindPath(BTree * root,int sum,int target,Stack * s) { int i; if(!root) return ; if(sum + root->data == target) { Push(s,root->data); for(i = 0;i<s->top;i++) printf("%3d",s->data[i]); return; } else if(sum + root->data > target) { return; } else { Push(s,root->data); sum += root->data; FindPath(root->left,sum,target,s); FindPath(root->right,sum,target,s); sum -= root->data; Pop(s); } } //初始化栈 void InitStack(Stack * s) { s->top = 0; } //入栈 void Push(Stack *s,int val) { if(s->top == MAXSIZE) { printf("栈满,无法入栈!\n"); return; } s->data[(s->top)++] = val; } //出栈 int Pop(Stack *s) { if(s->top == 0) { printf("栈空,无法出栈!\n"); return; } return s->data[--(s->top)]; }
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 在本篇内容里小编给大家分享了关于C++实现递归函数的教学步骤,需要的朋友跟着参考下。...2020-04-25