// 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。
程序代码如上所示,不足之处,还望指正!