在二叉树中怎么寻找和为某一值的所有路径
来源：爱站网时间：2021-06-02编辑：网友分享
二叉树是树形结构中一个非常重要的类型，并且有很多实际问题抽象出来的数据结构都是通过二叉树形式所呈现的，可见二叉树的重要性。那么我们要如何在二叉树中找出和为某一值的所有路径？PHP二叉树寻找路径的方法是怎么样的呢？
代码如下所示，不足之处，还望指正！
// BinaryTree.cpp : 定义控制台应用程序的入口点。
//C++实现链式二叉树，在二叉树中找出和为某一值的所有路径
#include "stdafx.h"
#include
#include
#include
using namespace std;
static int sum(0);
static int count(0);
template
struct BiNode
{
T data;
struct BiNode
};
template
class BiTree
{
public:
BiTree(){
cout Create(root);
if (NULL != root)
{
coutdata }
else
{
cout }
}
~BiTree(){Release(root);}
int Depth(){return Depth(root);}
int FindPath(T i)
{
stack
return FindPath(i, root, sta);
};
private:
BiNode
void Create(BiNode
void Release(BiNode
int Depth(BiNode
int FindPath(T i, BiNode
};
//析构函数
template
void BiTree
{
if(bt==NULL)
{
Release(bt->lchild );
Release(bt->rchild );
delete bt;
}
}
//建立二叉树
template
void BiTree
{
T ch;
cin>>ch;
if(ch== 0)bt=NULL;
else
{
bt=new BiNode
bt->data =ch;
cout Create(bt->lchild );
cout Create(bt->rchild );
}
}
//求树的深度
template
int BiTree
{
if (NULL == bt)
{
return 0;
}
int d1 = Depth(bt->lchild);
int d2 = Depth(bt->rchild);
return (d1 > d2 ? d1 : d2)+ 1;
}
template
int BiTree
{
if (NULL != bt)
{
sta.push(bt);
}
sum += bt->data;
if (sum == i && bt->lchild == NULL && bt->rchild == NULL)
{
stack
BiNode
cout while (!sta2.empty())
{
p = sta2.top();
cout data sta2.pop();
}
cout count ++;
}
if (NULL != bt->lchild)
{
FindPath(i, bt->lchild, sta);
}
if (NULL != bt->rchild)
{
FindPath(i,bt->rchild, sta);
}
sum -= bt->data;
sta.pop();
return count;
}
void main()
{
BiTree
cout }
输入一棵二叉树，从树的根节点开始往下访问，一直到叶节点所经过的所有节点形成一条路径。输出和与某个数相等的所有路径。
例如： 二叉树
3
2 6
5 4
则和为9的，路径有两条，一条为3，6 另一条为3, 2, 4。
以上内容中，爱站技术频道小编通过实例为大家详细说明了如何在二叉树中找出和为某一值的所有路径，通过上方法就可以在二叉树中寻找路径了。
上一篇：KMP算法的详细解说
