//在二叉树中找出和为某一值的所有路径 #include <iostream> #include <vector> using namespace std; //树结构 struct BTreeNode { int m_nValue; BTreeNode *m_pLeft; BTreeNode *m_pRight; }*BiTree; //按照先序创建二叉树,0表示空 BTreeNode *Create() { int ch; cin>> ch; if(ch == 0) { return NULL; } else { BTreeNode *root = new BTreeNode(); root->m_nValue = ch; root->m_pLeft = Create(); root->m_pRight = Create(); return root; } } //按照先序 打印 树 void printBTree(BTreeNode *root) { if(!root) { return ; } cout << root->m_nValue <<" "; printBTree(root->m_pLeft); printBTree(root->m_pRight); } //查找路径 void FindPath(BTreeNode *pTreeNode,int expectedSum,vector<int> &path,int ¤tSum) { if(!pTreeNode) { return ; } //累加到和里 currentSum += pTreeNode->m_nValue; //将该节点的数据域入栈 path.push_back(pTreeNode->m_nValue); bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight); //若当前为叶子节点,并且和恰好达到,则输出 if(currentSum == expectedSum && isLeaf) { for(vector<int>::iterator iter = path.begin(); iter != path.end(); ++iter) { cout << *iter << '\t'; } cout << endl; } //若不是叶子节点,则或者有左孩子 if(pTreeNode->m_pLeft) { FindPath(pTreeNode->m_pLeft,expectedSum,path,currentSum); } //或者有右孩子 if(pTreeNode->m_pRight) { FindPath(pTreeNode->m_pRight,expectedSum,path,currentSum); } // currentSum -= pTreeNode->m_nValue; path.pop_back(); return ; } void main() { BTreeNode *root=NULL; cout << "创建树:"<<endl; root = Create(); cout << "打印树:"<<endl; printBTree(root); vector<int> temp; int b = 0; int expectedSum; int &a = b; cout <<endl<<"请输入期望的和:"; cin >> expectedSum; cout << "满足条件的路径有:"<<endl; FindPath(root,expectedSum,temp,a); }
运行结果:
创建树:
1 3 4 0 0 5 0 0 2 6 0 0 7 0 0
打印树:
1 3 4 5 2 6 7
请输入期望的和:9
满足条件的路径有:
1 3 5
1 2 6
请按任意键继续. . .