Как выбрать случайный узел от дерева

Это не так. Чтобы выбрать узел равномерно случайным образом, просто пройдитесь по дереву в любом порядке. Пусть n-й рассмотренный узел будет выбран с вероятностью 1/n. То есть, сохраните в переменной запись об узле, который вы бы вернули, и когда вы смотрите на n-й узел, замените текущий узел на n-й с вероятностью 1/n. Индукцией можно показать, что это возвращает узел равномерно случайным образом без необходимости заранее знать их количество.

Если вы структурировали свои листья так, чтобы они сами хранились в индексируемом типе данных, например в массиве, то вы можете легко (псевдокод):

random_leaf = leaf_pile[ random( size of leaf pile ) ]

Это хороший, освежающий O (1): -)

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

Просто предлагаю альтернативу очевидному. Это действительно зависит от вашей структуры данных и вашего наиболее распространенного варианта использования.

Просто сделайте для каждого узла случайный вызов в диапазоне от 0 до (количество детей)-1 и выберите следующего ребенка после этого числа.

Повторяйте это до тех пор, пока не окажетесь в листе.