二叉树拓展--三叉树的遍历、路径算法

喜欢ヅ旅行 2022-05-08 09:26 174阅读 0赞

> nodes = \['a',\['b',\['e',\['k','\#','\#','\#'\],\['l','\#','\#','\#'\],'\#'\],\['f',\['m','\#','\#','\#'\],'\#','\#'\],'\#'\],\\  
> \['c',\['g',\['n',\['t','\#','\#','\#'\],\['u','\#','\#','\#'\],'\#'\],'\#','\#'\],\['h',\['o',\['v',\['y','\#','\#','\#'\],\\  
> \['z','\#','\#','\#'\],'\#'\],'\#','\#'\],\['p',\['w','\#','\#','\#'\],\['x','\#','\#','\#'\],'\#'\],'\#'\],\\  
> \['i',\['q','\#','\#','\#'\],'\#','\#'\]\],\['d',\['j',\['r','\#','\#','\#'\],\['s','\#','\#','\#'\],'\#'\],'\#','\#'\]\]  
> \# Definition for a binary tree node.  
> class TreeNode(object):  
>     def \_\_init\_\_(self, x):  
>         self.val = x  
>         self.left = None  
>         self.mid = None  
>         self.right = None  
> \#用嵌套列表构造三叉树，返回根节点  
> def buildTree(List):  
>     if List == '\#':  
>         return  
>     \#print(List\[0\],List)  
>     val,left,mid,right = List\[0\],List\[1\],List\[2\],List\[3\]  
>     root = TreeNode(val)  
>     root.left = buildTree(left)  
>     root.mid = buildTree(mid)  
>     root.right = buildTree(right)  
>     return root  
> \#递归式先序遍历  
> def preorder(root,preList):  
>     if root == None:  
>         return  
>     preList.append(root.val)  
>     preorder(root.left,preList)  
>     preorder(root.mid,preList)  
>     preorder(root.right,preList)  
>     return preList  
> \#打印到给定节点的路径  
> def printPath(root,val,path):  
>     if root == None:  
>         return  
>     path.append(root.val)  
>     if root.val == val:  
>         print(path)  
>         return   
>     printPath(root.left,val,path)  
>     printPath(root.mid,val,path)  
>     printPath(root.right,val,path)  
>     path.pop(-1)  
> \#搜索到给定节点的路径，存在则返回列表，反之返回False  
> def find(root,val,path,sign):  
>     path.append(root.val)  
>     if root.val == val:  
>         return True  
>     sign = 0  
>     if root.left != None:  
>         sign = find(root.left,val,path,sign)  
>     if not sign:  
>         if root.mid != None:  
>             sign = find(root.mid,val,path,sign)  
>         if not sign:  
>             if root.right != None:  
>                 sign = find(root.right,val,path,sign)  
>             else:  
>                    path.pop(-1)  
>     return sign  
> \#遍历所有深度为给定值的路径  
> def depthPath(root,path,res,depth):  
>     if root == None:  
>         return  
>     path += root.val  
>     depthPath(root.left,path+'-->',res,depth+3)  
>     depthPath(root.mid,path+'-->',res,depth+3)  
>     depthPath(root.right,path+'-->',res,depth+3)  
>     if len(path) == depth:  
>         res.append(path)
> 
> def rootPath(root,path,res):  
>     if root == None:  
>         return  
>     path += root.val  
>     rootPath(root.left,path+'-->',res)  
>     rootPath(root.mid,path+'-->',res)  
>     rootPath(root.right,path+'-->',res)  
>     if root.left == None and root.right == None:  
>         res.append(path)  
> \#判断两个给定节点是否相连  
> def isConnect(root,p,q):  
>     node\_p = getNode(root,p)  
>     node\_q = getNode(root,q)  
>     \#print(node\_p.val,node\_q.val)  
>     if node\_p == False or node\_q == False:  
>         return 'One of nodes does not exist...'  
>     if find(node\_p,q,\[\],0) or find(node\_q,p,\[\],0):  
>         return True  
>     else:   return False
> 
> \#查找key为给定值的结点，存在则返回对象，反之返回False  
> def getNode(root,val):  
>     if root == None:  
>         return  
>     stack,find = \[root\],0  
>     while stack:  
>         node = stack.pop()  
>         if node.val == val:  
>             return node  
>         if node.right:  
>             stack.append(node.right)  
>         if node.mid:  
>             stack.append(node.mid)  
>         if node.left:  
>             stack.append(node.left)  
>     if not find:  
>         return False
> 
> \#根据嵌套列表构造三叉树，并返回根节点  
> root = buildTree(nodes)
> 
> \#对三叉树进行先序遍历  
> print("Pre-order traversal of the tree")  
> print(preorder(root,\[\]))
> 
> \#找出到节点“d”的路径  
> print("\\n<Function 1>\\nFind the path to node i")  
> path = \[\]  
> printPath(root,'i',\[\])
> 
> \#打印所有深度为3的路径  
> path = ''  
> res = \[\]  
> depth = 4  
> print("\\n\\n<Function 2>\\nPrint all the paths whose depth is",depth)  
> depthPath(root,path,res,depth)  
> print(res)
> 
> \#打印从根节点出发的所有路径  
> print("\\n\\n<Function 3>\\nPrint all the paths from root to leaves")  
> path = ''  
> res = \[\]  
> rootPath(root,path,res)  
> print(res)
> 
> \#判断给定两个节点是否相连，参数为根节点，两个节点的值  
> print("\\n\\n<Function 4>\\nJudge if the two nodes are connected")  
> node1,node2 = 'g','h'  
> print("Test case:",node1,node2)  
> print(isConnect(root,'g','h'))