2013-07-01 16:50:53

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

小结：

转化为二叉树的前序遍历

 

代码：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           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 "<
         
          <
          
           >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 
           
             pStack) 40 { 41 PBTNode pBTNode = NULL; 42 while( !pStack.empty() ) 43 { 44 pBTNode = pStack.top(); 45 pStack.pop(); 46 PrintPath(pStack); 47 cout<
            
             data<<"\t"; 48 } 49 } 50 // 51 //void BinaryTreePathSum(PBTNode pRoot,int PathSum) 52 //{ 53 // PBTNode pCur = pRoot; 54 // stack 
             
               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 
              
                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 :"<
               

::iterator iter;106 for (iter = PathVector.begin();iter != PathVector.end();++iter)107 {108 cout<<*iter<<"\t";109 }110 cout<

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

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<

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 :"<

>ExpectedSum;163 while (END != ExpectedSum)164 {165 FindPath(pRoot,ExpectedSum);166 cout<<"please enter the ExpectedSum ,end with "<

<

>ExpectedSum;168 }169 170 return 0;171 }