python - 如何找到二叉树中节点的位置？

Question

4 0 2
0 1
0 3
2 3
0
3

我正在尝试找到解决上述问题的有效方法。

给定输入第一行是:二叉树中的节点数=4，root=0，depths=2

边或边上的节点没有以任何特定顺序给出，但连接节点到左子节点的边出现在输入中。

最后两行求0和3的位置，输出为

 1 2
 3 1

树可以有超过百万个节点并使用构建树

我找不到如何以可以找到节点坐标的方式表示树

更新代码

class node:
    def __init__(self, x):
        self.x=4
        self.l=2
        self.r=0
        self.id=id


    def recurse(node,id, depth = -1, position=-1, max_depth=-1):
        depth=depth+1
        current_depth=depth
        max_depth=max(max_depth,current_depth)

        matchl=False
        matchr=False

        if node.l :
            (depthl,position,max_depth,matchl)=node.recurse(node.l,id,current_depth,position,max_depth)

        positionl = position
        position = position + 1
        current_position=position


        if node.r:
            (depth,position,max_depth,matchr)=node.recurse(node.r,id,current_depth,position,max_depth)

        if matchl:
            return (depthl,positionl,max_depth,True)

        if node.x==id:
            return (current_depth,current_position,max_depth,True)
        return (depth,position,max_depth,matchr)


n2=node(2)
n3=node(3)
n1=node(1)
n0=node(0)

n0.l=n1
n0.r=n3
n3.l=n2

(depth,position,max_depth,match)=node.recurse(n0,3)
if match:
   answer = (position, max_depth - depth )

Answer 1

给出问题的方式假设没有两个节点可以共享一列，并且首先填充左节点，因为如果您以正确的顺序遍历树(左叶，节点，右叶):

以下代码未经测试，但应该能让您对算法有所了解:

def recurse( node,  id, depth = -1, position=-1, max_depth=-1):
   depth=depth+1
   current_depth=depth

   max_depth=max(max_depth,current_depth)

   matchl=False
   matchr=False

   if node.l :
       (depthl,position,max_depth,matchl)=recurse(node.l,id,current_depth,position,max_depth)

   positionl = position
   position = position + 1
   current_position=position


   if node.r:
      (depth,position,max_depth,matchr)=recurse(node.r,id,current_depth,position,max_depth)

   if matchl:
      return (depthl,positionl,max_depth,True)

   if node.x==id:
      return (current_depth,current_position,max_depth,True)

   return (depth,position,max_depth,matchr)

用法

(depth,position,match, max_depth) = recurse(root_node,target_id)

例子:

n2=node(2)
n3=node(3)
n1=node(1)
n0=node(0)

n0.l=n1
n0.r=n3
n3.l=n2

(depth,position,max_depth,match)=recurse(n0,3)
if match:
   answer = (position, max_depth - depth )