如何在二叉树中找出和为某一值的所有路径
更新时间:2020年4月25日 17:46 点击:1750
代码如下所示,不足之处,还望指正!
// BinaryTree.cpp : 定义控制台应用程序的入口点。
//C++实现链式二叉树,在二叉树中找出和为某一值的所有路径
#include "stdafx.h"
#include<iostream>
#include<string>
#include <stack>
using namespace std;
static int sum(0);
static int count(0);
template<class T>
struct BiNode
{
T data;
struct BiNode<T> *rchild,*lchild;
};
template<class T>
class BiTree
{
public:
BiTree(){
cout<<"请输入根节点:"<<endl;
Create(root);
if (NULL != root)
{
cout<<"root="<<root->data<<endl;
}
else
{
cout << "The BinaryTree is empty." << endl;
}
}
~BiTree(){Release(root);}
int Depth(){return Depth(root);}
int FindPath(T i)
{
stack<BiNode<T>*> sta;
return FindPath(i, root, sta);
};
private:
BiNode<T> *root;
void Create(BiNode<T>* &bt);
void Release(BiNode<T> *bt);
int Depth(BiNode<T>* bt);
int FindPath(T i, BiNode<T>* bt, stack<BiNode<T>*> &sta);
};
//析构函数
template <class T>
void BiTree<T>::Release(BiNode<T> *bt)
{
if(bt==NULL)
{
Release(bt->lchild );
Release(bt->rchild );
delete bt;
}
}
//建立二叉树
template <class T>
void BiTree<T>::Create(BiNode<T>* &bt)
{
T ch;
cin>>ch;
if(ch== 0)bt=NULL;
else
{
bt=new BiNode<T>;
bt->data =ch;
cout<<"调用左孩子"<<endl;
Create(bt->lchild );
cout<<"调用右孩子"<<endl;
Create(bt->rchild );
}
}
//求树的深度
template <class T>
int BiTree<T>::Depth(BiNode<T>* bt)
{
if (NULL == bt)
{
return 0;
}
int d1 = Depth(bt->lchild);
int d2 = Depth(bt->rchild);
return (d1 > d2 ? d1 : d2)+ 1;
}
template <class T>
int BiTree<T>::FindPath(T i, BiNode<T>* bt, stack<BiNode<T>*> &sta)
{
if (NULL != bt)
{
sta.push(bt);
}
sum += bt->data;
if (sum == i && bt->lchild == NULL && bt->rchild == NULL)
{
stack<BiNode<T>*> sta2(sta);
BiNode<T>* p;
cout << "One of the path is: " ;
while (!sta2.empty())
{
p = sta2.top();
cout << p->data << " ";
sta2.pop();
}
cout << endl;
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<int> a;
cout << "There are " << a.FindPath(9) << " path all." << endl;
}
输入一棵二叉树,从树的根节点开始往下访问,一直到叶节点所经过的所有节点形成一条路径。输出和与某个数相等的所有路径。
例如: 二叉树
3
2 6
5 4
则和为9的,路径有两条,一条为3,6 另一条为3, 2, 4。
复制代码 代码如下:
// BinaryTree.cpp : 定义控制台应用程序的入口点。
//C++实现链式二叉树,在二叉树中找出和为某一值的所有路径
#include "stdafx.h"
#include<iostream>
#include<string>
#include <stack>
using namespace std;
static int sum(0);
static int count(0);
template<class T>
struct BiNode
{
T data;
struct BiNode<T> *rchild,*lchild;
};
template<class T>
class BiTree
{
public:
BiTree(){
cout<<"请输入根节点:"<<endl;
Create(root);
if (NULL != root)
{
cout<<"root="<<root->data<<endl;
}
else
{
cout << "The BinaryTree is empty." << endl;
}
}
~BiTree(){Release(root);}
int Depth(){return Depth(root);}
int FindPath(T i)
{
stack<BiNode<T>*> sta;
return FindPath(i, root, sta);
};
private:
BiNode<T> *root;
void Create(BiNode<T>* &bt);
void Release(BiNode<T> *bt);
int Depth(BiNode<T>* bt);
int FindPath(T i, BiNode<T>* bt, stack<BiNode<T>*> &sta);
};
//析构函数
template <class T>
void BiTree<T>::Release(BiNode<T> *bt)
{
if(bt==NULL)
{
Release(bt->lchild );
Release(bt->rchild );
delete bt;
}
}
//建立二叉树
template <class T>
void BiTree<T>::Create(BiNode<T>* &bt)
{
T ch;
cin>>ch;
if(ch== 0)bt=NULL;
else
{
bt=new BiNode<T>;
bt->data =ch;
cout<<"调用左孩子"<<endl;
Create(bt->lchild );
cout<<"调用右孩子"<<endl;
Create(bt->rchild );
}
}
//求树的深度
template <class T>
int BiTree<T>::Depth(BiNode<T>* bt)
{
if (NULL == bt)
{
return 0;
}
int d1 = Depth(bt->lchild);
int d2 = Depth(bt->rchild);
return (d1 > d2 ? d1 : d2)+ 1;
}
template <class T>
int BiTree<T>::FindPath(T i, BiNode<T>* bt, stack<BiNode<T>*> &sta)
{
if (NULL != bt)
{
sta.push(bt);
}
sum += bt->data;
if (sum == i && bt->lchild == NULL && bt->rchild == NULL)
{
stack<BiNode<T>*> sta2(sta);
BiNode<T>* p;
cout << "One of the path is: " ;
while (!sta2.empty())
{
p = sta2.top();
cout << p->data << " ";
sta2.pop();
}
cout << endl;
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<int> a;
cout << "There are " << a.FindPath(9) << " path all." << endl;
}
输入一棵二叉树,从树的根节点开始往下访问,一直到叶节点所经过的所有节点形成一条路径。输出和与某个数相等的所有路径。
例如: 二叉树
3
2 6
5 4
则和为9的,路径有两条,一条为3,6 另一条为3, 2, 4。
相关文章
- 这篇文章主要介绍了在C#中使用二叉树实时计算海量用户积分排名的实现详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要介绍了举例讲解C语言程序中对二叉树数据结构的各种遍历方式,先序中序后序二叉树遍历几乎成了最老生常谈的数据结构基础知识,的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了一波二叉树遍历问题的C++解答实例分享,包括节点打印和转换为镜像等问题的解答,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构之二叉树的非递归后序遍历算法的相关资料,希望通过本文能帮助到大家,让大家实现这样的功能,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法,涉及C++二叉树的定义、遍历、统计相关操作技巧,需要的朋友可以参考下...2020-04-25
- 二叉树是数据结构中的树的一种特殊情况,有关二叉树的相关概念,这里不再赘述,如果不了解二叉树相关概念,建议先学习数据结构中的二叉树的知识点...2020-04-25
- 这篇文章主要介绍了php实现的二叉树遍历算法,结合具体实例形式分析了php针对二叉树的常用前序、中序及后序遍历算法实现技巧,需要的朋友可以参考下...2017-06-20
- 这篇文章主要介绍了如何在Python中创建二叉树,帮助大家更好的理解和学习使用python,感兴趣的朋友可以了解下...2021-03-30
- 这篇文章主要介绍了C语言 二叉查找树性质详解及实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++基于先序、中序遍历结果重建二叉树的方法,结合实例形式分析了基于C++构建二叉树的相关操作技巧,需要的朋友可以参考下...2020-04-25
C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)
这篇文章主要介绍了C++基于递归和非递归算法判定两个二叉树结构是否完全相同,若判断二叉树的结构和数据都相同则为完全相同.涉及C++二叉树的创建、遍历、比较等相关操作技巧,需要的朋友可以参考下...2020-04-25- 这篇文章主要为大家详细介绍了C++实现二叉树基本操作,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C语言实现二叉树遍历的迭代算法,包括二叉树的中序遍历、先序遍历及后序遍历等,是非常经典的算法,需要的朋友可以参考下...2020-04-25
- 在本篇文章里小编给大家分享了关于c++先序二叉树的构建的相关知识点,需要的朋友们跟着学习下。...2020-04-25
- 这篇文章主要介绍了平衡二叉树的实现实例,需要的朋友可以参考下...2020-04-25
- 这篇文章主要为大家详细介绍了C++二叉树实现词频分析功能,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历)的相关资料,这里提供实例代码来帮助大家理解掌握二叉树,需要的朋友可以参考下...2020-04-25
C++实现LeetCode(105.由先序和中序遍历建立二叉树)
这篇文章主要介绍了C++实现LeetCode(105.由先序和中序遍历建立二叉树),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-07-23- 这篇文章主要介绍了C语言二叉树的非递归遍历,包括了先序遍历、中序遍历与后序遍历,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++非递归建立二叉树的方法,实例分析了二叉树的原理与C++实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-04-25