python实现在二叉树中找出与输入相等的所有路径

广告位

python实现在二叉树中找出与输入相等的所有路径 题目描述: 从树的根结点开始往下访问 一直到叶子结点经过的…

python实现在二叉树中找出与输入相等的所有路径

题目描述:
从树的根结点开始往下访问 一直到叶子结点经过的所有结点形成一条路径 。 找出所有的
这些路径,使其满足这条路径上所有结点数据的和等于给定的整数 。 例如:给定如下 二 叉树 与整数 8,满足条件的路径为6>3>-1 (6+3一1=8)。
python实现在二叉树中找出与输入相等的所有路径
分析与解答:
可以通过对二叉树的遍历找出所有的路径,然后判断各条路径上所有结点的值的和是否 与给定的整数相等,如果相等,则打印出这条路径。具体实现方法可以通过对二叉树进行先 序遍历来实现,实现思路为:对 二 叉树进行先序遍历,把遍历的路径记录下来,当遍历到叶 子结点时,判断当前的路径上所有结点数据的和是否等于给定的整数,如果相等则输出路径 信息,示例代码如下 :

class BiTNode:     def __init__(self):         self.data=None         self.lchild=None         self.rchild=None def findroad(root,num,sums,v):     sums+=root.data     v.append(root.data)     if root.lchild==None and root.rchild==None and sums==num:         i=0         while i<len(v):             print(v[i])             i+=1         print('n')     if root.lchild!=None:         findroad(root.lchild,num,sums,v)     if root.rchild!=None:         findroad(root.rchild,num,sums,v)     sums-=v[-1]     v.remove(v[-1]) def constructTree():     root=BiTNode()     node1=BiTNode()     node2=BiTNode()     node3=BiTNode()     node4=BiTNode()     root.data=6     node1.data=3     node2.data=7     node3.data=-1     node4.data=9     root.lchild=node1     root.rchild=node2     node1.lchild=node3     node1.rchild=node4     node2.lchild=node2.rchild=node3.lchild=node3.rchild=node4.lchild=node4.rchild=None     return root if __name__=='__main__':     root=constructTree()     s=[]     print('满足路径结点和为8的路径为:')     findroad(root,8,0,s) 
满足路径结点和为8的路径为: 6 3 -1 

剪烛西窗, 程

关于作者: 剪烛西窗

为您推荐