Блог

Существует проблема, которая хочет найти центр дерева, и я хочу удалять листья до тех пор, пока не останется более 2 вершин. Но как я могу найти листья?

PS извините за мой английский

Редактировать: я только что увидел, что у вас, вероятно, есть корневое дерево. Вы можете создать DFS дерева, и когда от текущего узла у вас нет ребра к узлу, отличному от родительского, тогда вы нашли лист.

Цитирую Википедию:

Степень вершины в графе — это количество ребер, инцидентных ей. Изолированная вершина — это вершина с нулевой степенью; то есть вершина, которая не является конечной точкой какого-либо ребра. Конечная вершина (также подвесная вершина) — это вершина с первой степенью.

Просто подсчитайте степень каждого узла. Если это так 1 , то у вас есть лист.