題目：輸入一個整數和一棵二元樹。從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑。打印出和與輸入整數相等的所有路徑。
例如輸入整數22和如下二元樹
10
/ \
5 12
/ \
4 7
則打印出兩條路徑：10, 12和10, 5, 7。
我的思路，貌似有點復雜了，用一個vector和stack存儲數據，vector輸出路徑，stack用來保存路徑，因為用stack輸出就要全部出棧，數據會丟失。
網上的答案，包括某些大神寫的，都是有部分問題的，度為1的節點輸入就出bug了。突然想到想糾正bug，於是寫了如下程序。
[cpp]
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
//節點
struct node
{
node *lchild,*rchild;
int value;
};
//二元查找樹
class list
{
public:
list();
//這裡的m_print函數用做遞歸，print函數相當於外面的一個套子
void print(int num);
private:
//將遞歸函數私有化
void m_print(node *p,int value,int num,bool flag);
private:
node* root;
vector<int> v;
stack<node*> s;
};
void list::m_print(node *p,int value,int num,bool flag)
{
if(p==NULL)
return;
value+=p->value;
v.push_back(p->value);
s.push(p);
//到葉子節點返回
if(NULL==p->lchild && NULL==p->rchild){
if(value==num){
for(vector<int>::iterator iter=v.begin();iter!=v.end();iter++)
cout<<*iter<<" ";
cout<<endl;
}
v.pop_back();
s.pop();
if(flag==1){
v.pop_back();
s.pop();
}
while(1){
if(!s.empty() && !s.top()->rchild){
s.pop();
v.pop_back();
}
else
break;
}
return;
}
//向左右方向遞歸
m_print(p->lchild,value,num,0);
m_print(p->rchild,value,num,1);
}
void list::print(int num)
{
v.clear();
m_print(root,0,num,0);
}
list::list()
{
cout<<"請輸入您要輸入的節點,按'#'退出:"<<endl;
int i;
//用cin.fail(),cin.bad()判斷也行
if(cin>>i==NULL){
cout<<"您的輸入有誤"<<endl;
exit(-1);
}
//創建根節點
root=new node;
root->value=i;
root->lchild=NULL;
root->rchild=NULL;
//建立兩個臨時節點，p開辟新節點，q為二元查找定位
node *p,*q;
while(cin>>i!=NULL){
//開辟新節點
p=new node;
p->value=i;
p->lchild=NULL;
p->rchild=NULL;
//二元查找樹比較從q=root開始，小則轉左，大則轉右，如果有位置就插入
q=root;
while(1){
//插入節點小於該節點比較值，左節點為空則插入，否則q=q->lchild繼續判斷
if(p->value<q->value){
if(q->lchild)
q=q->lchild;
else{
q->lchild=p;
break;
}
}
//插入節點大於該節點比較值，右節點為空則插入，否則q=q->rchild繼續判斷
else if(p->value>q->value){
if(q->rchild)
q=q->rchild;
else{
q->rchild=p;
break;
}
}
//如果兩節點相等，直接退出程序(有些暴力）
else{
cout<<"node repeated!!"<<endl;
exit(-1);
}
}
}
}
void main()
{
list test;
//這裡的print函數打印出所有的根節點到所有葉子節點的長度
test.print(22);
system("pause");
}
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
//節點
struct node
{
node *lchild,*rchild;
int value;
};
//二元查找樹
class list
{
public:
list();
//這裡的m_print函數用做遞歸，print函數相當於外面的一個套子
void print(int num);
private:
//將遞歸函數私有化
void m_print(node *p,int value,int num,bool flag);
private:
node* root;
vector<int> v;
stack<node*> s;
};
void list::m_print(node *p,int value,int num,bool flag)
{
if(p==NULL)
return;
value+=p->value;
v.push_back(p->value);
s.push(p);
//到葉子節點返回
if(NULL==p->lchild && NULL==p->rchild){
if(value==num){
for(vector<int>::iterator iter=v.begin();iter!=v.end();iter++)
cout<<*iter<<" ";
cout<<endl;
}
v.pop_back();
s.pop();
if(flag==1){
v.pop_back();
s.pop();
}
while(1){
if(!s.empty() && !s.top()->rchild){
s.pop();
v.pop_back();
}
else
break;
}
return;
}
//向左右方向遞歸
m_print(p->lchild,value,num,0);
m_print(p->rchild,value,num,1);
}
void list::print(int num)
{
v.clear();
m_print(root,0,num,0);
}
list::list()
{
cout<<"請輸入您要輸入的節點,按'#'退出:"<<endl;
int i;
//用cin.fail(),cin.bad()判斷也行
if(cin>>i==NULL){
cout<<"您的輸入有誤"<<endl;
exit(-1);
}
//創建根節點
root=new node;
root->value=i;
root->lchild=NULL;
root->rchild=NULL;
//建立兩個臨時節點，p開辟新節點，q為二元查找定位
node *p,*q;
while(cin>>i!=NULL){
//開辟新節點
p=new node;
p->value=i;
p->lchild=NULL;
p->rchild=NULL;
//二元查找樹比較從q=root開始，小則轉左，大則轉右，如果有位置就插入
q=root;
while(1){
//插入節點小於該節點比較值，左節點為空則插入，否則q=q->lchild繼續判斷
if(p->value<q->value){
if(q->lchild)
q=q->lchild;
else{
q->lchild=p;
break;
}
}
//插入節點大於該節點比較值，右節點為空則插入，否則q=q->rchild繼續判斷
else if(p->value>q->value){
if(q->rchild)
q=q->rchild;
else{
q->rchild=p;
break;
}
}
//如果兩節點相等，直接退出程序(有些暴力）
else{
cout<<"node repeated!!"<<endl;
exit(-1);
}
}
}
}
void main()
{
list test;
//這裡的print函數打印出所有的根節點到所有葉子節點的長度
test.print(22);
system("pause");
}
