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

Question

我正在努力寻找解决上述问题的有效方法。

给定输入的第一行是：number of nodes in binary tree=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 )

Answer 2

您的问题似乎暗示树的图形表示是唯一的，但事实并非如此。您应该搜索 "Tree Drawing Algorithms".

例如，快速搜索得到 http://cs.brown.edu/~rt/gdhandbook/chapters/trees.pdf and http://www.cs.unc.edu/techreports/89-034.pdf

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

How to find position of nodes in binary tree?

python

algorithm

binary-tree