資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究用 Python 尋找 n 叉樹根節點的程式
假設我們以陣列的形式獲得了 n 叉樹的節點。我們必須透過重建它來找到並返回樹的根節點。完整的樹必須以先序表示法顯示在返回節點中。
所以，如果輸入如下
那麼輸出將是
[14, 27, 32, 42, 56, 65]
我們將使用樹的根來顯示樹的先序遍歷。因此，輸出便是樹的先序遍歷。
為了解決這個問題，我們將遵循以下步驟 −
indegree := 包含整數值的新對映
對於樹中的每個節點，執行操作
對於節點的每個子節點指標，執行操作
indegree[子節點值] := indegree[子節點值] + 1
對於樹中的每個節點，執行操作
如果 indegree[節點值] 與 0 相同，則
返回 node
返回 null
示例（Python）
讓我們看看以下實現，以便更好地理解 −
import collections
class Node:
def __init__(self, value, child = None) -> None:
self.val = value
self.children = []
if child != None:
for value in child:
self.children.append(value)
def solve(tree):
indegree = collections.defaultdict(int)
for node in tree:
for child in node.children:
indegree[child.val] += 1
for node in tree:
if indegree[node.val] == 0:
return node
return None
def treeprint(node, tree):
if node == None:
tree.append("None")
return tree
if tree == None:
tree = []
tree.append(node.val)
for child in node.children:
treeprint(child, tree)
return tree
node6 = Node(65)
node5 = Node(56)
node4 = Node(42, [node5, node6])
node3 = Node(32)
node2 = Node(27)
node1 = Node(14, [node2, node3, node4])
tree = [node2, node1, node5, node3, node6, node4]
root = solve(tree)
print(treeprint(root, None))輸入
node6 = Node(65) node5 = Node(56) node4 = Node(42, [node5, node6]) node3 = Node(32) node2 = Node(27) node1 = Node(14, [node2, node3, node4]) tree = [node2, node1, node5, node3, node6, node4]
輸出
[14, 27, 32, 42, 56, 65]
更新於：18-5-2021
545 次瀏覽
廣告