代码之家 › 专栏 › 技术社区 › Dawn17

在树中查找所有级别中出现频率最高的节点

tree python

Dawn17 · 技术社区 · 8 年前

我最近做了一个编码测验,要求我在树中找到一个在所有级别中出现频率最高的节点。

例如

      a
     /  \
   c    a
  / \  / \
 c  a b   c

在这棵树上, a 应该是答案,因为它出现在级别0、1和2中。

我试图使用级别顺序遍历来实现这一点,但我对如何跟踪节点出现在哪个级别感到困惑。

如何解决这个问题,最好使用Python?

树结构:

class TreeNode:
    def __init__(self, data = None):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = TreeNode(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = TreeNode(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

3 回复 | 直到 8 年前

Olivier Melançon iacob 8 年前

在遍历树时,使用 dict 跟踪每种节点类型所在的级别。这可以通过将键设置为节点,将值设置为节点所在的级别集来实现。

def most_frequent_in_levels(tree):

    counter = {}

    def level_counter(tree, counter, level):
        if tree.data not in counter:
            counter[tree.data] = {level}
        else:
            counter[tree.data].add(level)

        if tree.left:
            level_counter(tree.left, counter, level + 1)

        if tree.right:
            level_counter(tree.right, counter, level + 1)

    level_counter(tree, counter, 0)

    return max(counter.keys(), key=lambda data: len(counter[data]))

下面是一个工作示例。

tree = TreeNode(data='a')
tree.left, tree.right= TreeNode(data='a'), TreeNode(data='b')
tree.left.left, tree.left.right, tree.right.left = TreeNode(data='c'), TreeNode(data='c'), TreeNode(data='c')

# Which creates the following tree
#
#          a
#         /  \
#       a    b
#      / \  /
#     c  c c 

most_frequent_in_levels(tree) # 'a'

Olivier Melançon iacob 8 年前

我会怎么做,这基本上是psuedo代码,未经测试

countingdict = {}
for tag, element in root:
   if tag not in dict:
         countingdict.update({tag:1})
   else:
         countingdict[tag] += 1

您可以根据需要嵌套多个级别的循环

Ajax1234 8 年前

您可以使用自定义版本 Breadth-First-Search :

from collections import deque, defaultdict
def bsf(tree):
  d = deque([tree])
  levels = defaultdict(list)
  count = 0
  seen = [tree.data]
  while seen:
     listing = []
     while d:
      val = d.popleft()
      if val:
         levels[count].append(val.data)
         listing.extend([val.right, val.left])
     count += 1 
     if not any(listing):
       break
     d.extend(listing)
  return levels


result = bsf(t1)
frequencies = {i:[b for _, b in result.items() if i in b] for i in [c for h in result.values() for c in h]}
last_result = map(frequencies.items(), key=lambda x:len(x[-1]))[0]