求二叉树中核为某一值的所有路径

  1 #include <iostream>
  2 #include <assert.h>
  3 #include <stack>
  4 #include <vector>
  5 using namespace std;
  6 
  7 typedef int DataType;        //数中结点数据类型
  8 const DataType END = -1;  //结束字符
  9 
 10 typedef struct node
 11 {
 12     DataType data;
 13     node * lchild;
 14     node * rchild;
 15 }BTNode,*PBTNode;
 16 
 17 //创建二叉树
 18 PBTNode CreatBTree()
 19 {
 20     PBTNode pNode = NULL;
 21     DataType data;
 22     cout<<"please enter the data of the node ,end with "<<END<<endl;
 23     cin>>data;
 24     if (END != data)
 25     {
 26         pNode = new BTNode;
 27         assert(NULL != pNode);
 28         pNode->data = data;
 29         pNode->lchild = CreatBTree();
 30         pNode->rchild = CreatBTree();
 31         return pNode;
 32     }
 33     else
 34     {
 35         return NULL;
 36     }
 37 }
 38 
 39 void PrintPath(stack <PBTNode> pStack)
 40 {
 41     PBTNode pBTNode = NULL;
 42     while( !pStack.empty() )
 43     {
 44         pBTNode = pStack.top();
 45         pStack.pop();
 46         PrintPath(pStack);
 47         cout<<pBTNode->data<<"\t";
 48     }
 49 }
 50 //
 51 //void BinaryTreePathSum(PBTNode pRoot,int PathSum)
 52 //{
 53 //    PBTNode pCur = pRoot;
 54 //    stack <PBTNode> pStack;
 55 //    int PathSumCur = 0;
 56 //    //PBTNode pBTNode = NULL;
 57 //
 58 //    while (NULL != pCur || !pStack.empty())
 59 //    {
 60 //        while (NULL != pCur)
 61 //        {
 62 //            while (NULL != pCur)
 63 //            {
 64 //                pStack.push(pCur);
 65 //                PathSumCur = PathSumCur + pCur->data;
 66 //                pCur = pCur->lchild;
 67 //            }
 68 //
 69 //            pCur = pCur->rchild;
 70 //        }
 71 //
 72 //        if (PathSumCur == PathSum)
 73 //        {
 74 //            PrintPath(pStack);
 75 //        }
 76 //        
 77 //        if ( !pStack.empty() )
 78 //        {
 79 //            pCur = pStack.top();
 80 //            pStack.pop();
 81 //            PathSumCur = PathSumCur - pCur->data;
 82 //        }
 83 //
 84 //        if ( !pStack.empty() )
 85 //        {
 86 //            pCur = pStack.top().rchild;
 87 //        }
 88 //        else
 89 //        {
 90 //            break;
 91 //        }
 92 //    }
 93 //}
 94 
 95 //找出和为某一值的所有路径
 96 void FindPath(PBTNode pRoot,vector <int> PathVector,int ExpectedSum,int CurrentSum)
 97 {
 98     PathVector.push_back(pRoot->data);
 99     CurrentSum = CurrentSum + pRoot->data;
100 
101     bool IsLeaf = (pRoot->lchild == NULL && pRoot->rchild == NULL);
102     if ( (CurrentSum == ExpectedSum) && IsLeaf)
103     {
104         cout<<"1 path is found ,the path is :"<<endl;
105         vector<int>::iterator iter;
106         for (iter = PathVector.begin();iter != PathVector.end();++iter)
107         {
108             cout<<*iter<<"\t";
109         }
110         cout<<endl;
111     }
112 
113     if (NULL != pRoot->lchild)
114     {
115         FindPath(pRoot->lchild,PathVector,ExpectedSum,CurrentSum);
116     }
117     if (NULL != pRoot->rchild)
118     {
119         FindPath(pRoot->rchild,PathVector,ExpectedSum,CurrentSum);
120     }
121 
122     CurrentSum = CurrentSum - pRoot->data;
123     PathVector.pop_back();
124 }
125 
126 //找出和为某一值的所有路径
127 void FindPath(PBTNode pRoot,int ExpectedSum)
128 {
129     if (NULL == pRoot)
130     {
131         return;
132     }
133     vector <int> PathVector;
134     int CurrentSum = 0;
135     FindPath(pRoot,PathVector,ExpectedSum,CurrentSum);
136 }
137 
138 //前序遍历打印二叉树
139 void PrintBTree(PBTNode pRoot)
140 {
141     if (NULL != pRoot)
142     {
143         cout<<pRoot->data<<"\t";
144         PrintBTree(pRoot->lchild);
145         PrintBTree(pRoot->rchild);
146     }
147 }
148 
149 //测试代码
150 int main()
151 {
152     PBTNode pRoot = NULL;
153     int ExpectedSum;
154     //创建二叉树
155     pRoot = CreatBTree();
156     cout<<"the original binary tree is :"<<endl;
157     PrintBTree(pRoot);
158     cout<<endl;
159 
160     //测试FindPath
161     cout<<"please enter the ExpectedSum ,end with "<<END<<endl;
162     cin>>ExpectedSum;
163     while (END != ExpectedSum)
164     {
165         FindPath(pRoot,ExpectedSum);
166         cout<<"please enter the ExpectedSum ,end with "<<END<<endl;
167         cin>>ExpectedSum;
168     }
169 
170     return 0;
171 }

please enter the data of the node ,end with -1
10 5 4 -1 -1 7 -1 -1 12 -1 -1
please enter the data of the node ,end with -1
please enter the data of the node ,end with -1
please enter the data of the node ,end with -1
please enter the data of the node ,end with -1
please enter the data of the node ,end with -1
please enter the data of the node ,end with -1
please enter the data of the node ,end with -1
please enter the data of the node ,end with -1
please enter the data of the node ,end with -1
please enter the data of the node ,end with -1
the original binary tree is :
10      5       4       7       12
please enter the ExpectedSum ,end with -1
22
1 path is found ,the path is :
10      5       7
1 path is found ,the path is :
10      12
please enter the ExpectedSum ,end with -1
19
1 path is found ,the path is :
10      5       4
please enter the ExpectedSum ,end with -1
23
please enter the ExpectedSum ,end with -1
-1
请按任意键继续. . .