输入一个二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
如上图的二叉树,当输入根结点和一个数值12的时候,就有两条路径“1->2->4->5”和“1->3->8”,如果存在,就输出上述路径,如果没有任何一条路径满足就不输出路径并提示;
首先,路径一定是从根结点开始到某个叶子结点结束,这才是一条路径,因此,应该最先访问的就是根结点,而在二叉树的先中后序遍历中只有先序遍历是最先访根结点的,所以可以用如下方法:用先序遍历方法遍历二叉树,每当经过一个结点的时候就将其值进行保存相加,如果中途发现或者到达叶子结点之后,当前路径相加得到的值并不满足要求的值,则往回退并将值减去,或者当前路径已经满足,则需要再去换一条路径访问看是否还有其他路径满足条件,而能够提供往回退的方法就只有递归了,直至遍历完毕二叉树;
程序设计如下:
#include#include #include using namespace std; struct BinaryTreeNode//二叉树结点数据结构 { int _val; BinaryTreeNode *_Lnode; BinaryTreeNode *_Rnode; BinaryTreeNode(int val) :_val(val) ,_Lnode(NULL) ,_Rnode(NULL) {} }; BinaryTreeNode* _Create(int *arr, size_t& index, size_t size)//创建二叉树 { if((index < size) && (arr[index] != '#')) { BinaryTreeNode *root = new BinaryTreeNode(arr[index]); root->_Lnode = _Create(arr, ++index, size); root->_Rnode = _Create(arr, ++index, size); return root; } else return NULL; } BinaryTreeNode* CreateBinaryTree(int *arr, size_t size) { assert(arr && size); size_t index = 0; return _Create(arr, index, size); } void DestoryBinaryTree(BinaryTreeNode *root)//销毁二叉树 { if(root != NULL) { DestoryBinaryTree(root->_Lnode); DestoryBinaryTree(root->_Rnode); delete root; } } void PrevOrder(BinaryTreeNode *root)//前序遍历打印出二叉树 { if(root != NULL) { cout< _val<<" "; PrevOrder(root->_Lnode); PrevOrder(root->_Rnode); } } void _Count(BinaryTreeNode* root, vector *pv, int& count, int num) { if(root != NULL) { count += root->_val;//每当一个结点不为NULL的时候,就将其放入容器中且加上其值 (*pv).push_back(root->_val); _Count(root->_Lnode, pv, count, num); _Count(root->_Rnode, pv, count, num); if(count == num)//当找到一个路径的时候就将其打印出来 { cout<<"A Path Is : "; for(size_t i = 0; i < (*pv).size(); ++i) cout<<(*pv)[i]<<"->"; cout<<"NULL"< v;//用一个容器来存放路径 int count = 0;//用一个计数器计算和 _Count(root, &v, count, num); } int main() { int arr[] = {1,2,6,'#','#',4,5,'#','#','#',3,7,'#','#',8,'#','#'}; int num = 12; BinaryTreeNode *root = CreateBinaryTree(arr, sizeof(arr)/sizeof(arr[0])); cout<<"PrevOrder:"; PrevOrder(root); cout< 运行程序:
《完》
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网页标题:二叉树中和为某一值的路径——25-创新互联
本文地址:http://cdkjz.cn/article/jggjo.html