如何在二叉樹中找出和為某一值的所有路徑
更新時(shí)間:2013年05月29日 12:02:31 作者:
本篇文章是對在二叉樹中找出和為某一值的所有路徑方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
代碼如下所示,不足之處,還望指正!
// BinaryTree.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。
//C++實(shí)現(xiàn)鏈?zhǔn)蕉鏄洌诙鏄渲姓页龊蜑槟骋恢档乃新窂?BR>#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<<"請輸入根節(jié)點(diǎn):"<<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);
};
//析構(gòu)函數(shù)
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<<"調(diào)用左孩子"<<endl;
Create(bt->lchild );
cout<<"調(diào)用右孩子"<<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;
}
輸入一棵二叉樹,從樹的根節(jié)點(diǎn)開始往下訪問,一直到葉節(jié)點(diǎn)所經(jīng)過的所有節(jié)點(diǎn)形成一條路徑。輸出和與某個(gè)數(shù)相等的所有路徑。
例如: 二叉樹
3
2 6
5 4
則和為9的,路徑有兩條,一條為3,6 另一條為3, 2, 4。
復(fù)制代碼 代碼如下:
// BinaryTree.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。
//C++實(shí)現(xiàn)鏈?zhǔn)蕉鏄洌诙鏄渲姓页龊蜑槟骋恢档乃新窂?BR>#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<<"請輸入根節(jié)點(diǎn):"<<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);
};
//析構(gòu)函數(shù)
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<<"調(diào)用左孩子"<<endl;
Create(bt->lchild );
cout<<"調(diào)用右孩子"<<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;
}
輸入一棵二叉樹,從樹的根節(jié)點(diǎn)開始往下訪問,一直到葉節(jié)點(diǎn)所經(jīng)過的所有節(jié)點(diǎn)形成一條路徑。輸出和與某個(gè)數(shù)相等的所有路徑。
例如: 二叉樹
3
2 6
5 4
則和為9的,路徑有兩條,一條為3,6 另一條為3, 2, 4。
您可能感興趣的文章:
- 平衡二叉樹AVL操作模板
- 平衡二叉樹的實(shí)現(xiàn)實(shí)例
- 二叉樹的非遞歸后序遍歷算法實(shí)例詳解
- 二叉樹先序遍歷的非遞歸算法具體實(shí)現(xiàn)
- 二叉樹先根(先序)遍歷的改進(jìn)
- c語言版本二叉樹基本操作示例(先序 遞歸 非遞歸)
- python二叉樹遍歷的實(shí)現(xiàn)方法
- python二叉樹的實(shí)現(xiàn)實(shí)例
- C++二叉樹結(jié)構(gòu)的建立與基本操作
- 二叉樹遍歷 非遞歸 C++實(shí)現(xiàn)代碼
- 先序遍歷二叉樹的遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn)深入解析
- PHP Class&Object -- 解析PHP實(shí)現(xiàn)二叉樹
- PHP Class&Object -- PHP 自排序二叉樹的深入解析
- 探討:C++實(shí)現(xiàn)鏈?zhǔn)蕉鏄?用非遞歸方式先序,中序,后序遍歷二叉樹)
- 深入理解二叉樹的非遞歸遍歷
- 深入遍歷二叉樹的各種操作詳解(非遞歸遍歷)
- 深入二叉樹兩個(gè)結(jié)點(diǎn)的最低共同父結(jié)點(diǎn)的詳解
- 二叉樹前序遍歷的非遞歸算法
相關(guān)文章
C++設(shè)計(jì)模式之裝飾模式(Decorator)
這篇文章主要為大家詳細(xì)介紹了C++設(shè)計(jì)模式之裝飾模式Decorator的相關(guān)資料,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-03-03C++基礎(chǔ)入門教程(一):基礎(chǔ)知識大雜燴
這篇文章主要介紹了C++基礎(chǔ)入門教程(一):基礎(chǔ)知識大雜燴,本文講解了注釋、頭文件、命名空間等內(nèi)容,需要的朋友可以參考下2014-11-11C++開發(fā)的Redis數(shù)據(jù)導(dǎo)入工具優(yōu)化
這篇文章主要介紹了C++開發(fā)的Redis數(shù)據(jù)導(dǎo)入工具優(yōu)化方法的相關(guān)資料,需要的朋友可以參考下2015-07-07利用C++實(shí)現(xiàn)通訊錄管理系統(tǒng)的完整代碼
通訊錄是一個(gè)可以記錄親人、好友信息的工具,下面這篇文章主要給大家介紹了關(guān)于利用C++實(shí)現(xiàn)通訊錄管理系統(tǒng)的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-06-06C++ 中重載和運(yùn)算符重載加號實(shí)現(xiàn)矩陣相加實(shí)例代碼
這篇文章主要介紹了C++ 中重載和運(yùn)算符重載加號實(shí)現(xiàn)矩陣相加實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-03-03