Nano Hash - криптовалюты, майнинг, программирование

Обход дерева Python и сортировка групп элементов внутри отсортированного списка

Я просматриваю небинарное дерево, у меня есть функция для вычисления высоты узла и количества дочерних элементов. Что я хочу сделать, так это сначала отсортировать дочерние элементы моего узла по высоте, а внутри каждой группы высоты я хочу, чтобы она сортировалась по количеству дочерних элементов.

eg: 

      a
   /     \
  b       c
 /|\     /
d e f   g
       /
      h

поэтому, когда я пересекаю дерево:

def orderTree(node):        
   if "children" in node:
        if node['children']:
            node['children'].sort(key=findHeight)
            node['children'].sort(key=countChildren)

            for child in node['children']:
                print(child['name'])
                orderTree(child)

с этим кодом я иду = > a, c, g, h, b, d, e, f, но мне нужно = > a, b, d, e, f, c, g, h

Любая идея, как сортировать отсортированную группу элементов внутри списка python?

python sorting algorithm data-structures tree
09.10.2017

Ответы:


1

То, что вы хотите сделать, называется «сортировка по нескольким полям»,

Чтобы отсортировать список узлов по их высоте, а затем по количеству дочерних элементов, просто дайте sort следующую функцию как key:

lambda x : (findHeight(x), children(x))

Это просто возвращает кортеж (высота, дети). И затем sort использует этот кортеж для сравнения двух узлов.

Код:

def orderTree(node):
   # I combined the two ifs
   if "children" in node and node['children']:
        node['children'].sort(key= lambda x : (findHeight(x), children(x) ) )

        for child in node['children']:
            print(child['name'])
            orderTree(child)

Допустим, у меня есть A = (a,b) и B = (x, y)

Эти два кортежа будут сравниваться следующим образом:

def compare_tuple(A, B):
    if A[0] != B[0]: return A[0] < B[0]
    else: return A[1] < B[1]
10.10.2017

2

Тип обхода дерева, который вам нужен, называется предварительным порядком. Трудно понять ваш код, не зная его полной структуры. Но похоже, что вы сначала смотрите на дочерние элементы из корневого узла, а затем перемещаетесь вниз.

Я думаю, вы хотите открыть первый дочерний узел, а затем продолжать проходить через него. Для предзаказа должно быть что-то вроде.

node
node.left
node.right

Это хороший справочник http://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

09.10.2017
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..