若何在二叉樹中找出和為某一值的一切途徑

若何在二叉樹中找出和為某一值的一切途徑。本站提示廣大學習愛好者：（若何在二叉樹中找出和為某一值的一切途徑）文章只能為提供參考，不一定能成為您想要的結果。以下是若何在二叉樹中找出和為某一值的一切途徑正文

---

代碼以下所示，缺乏的地方，還望斧正！

// 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。