Python - 葉子節點和非葉子節點字典

---

字典是 Python 中一個重要的資料結構，它由鍵值對組成。它們最初設計為不可迭代的物件。然而，最近 Python 也擴充套件了對字典物件的迭代支援。巢狀字典具有節點、葉子節點、非葉子節點等。在本文中，我們將瞭解如何使用 Python 中的字典來操作葉子節點和非葉子節點。

什麼是葉子節點和非葉子節點？

在深入研究程式碼之前，我們首先需要了解字典資料型別中的葉子節點和非葉子節點。

• 葉子節點：那些沒有任何其他子節點的節點。它們也稱為終端節點。

• 非葉子節點：那些具有非零子節點的節點。它們始終位於葉子節點上方，因此它們從未佔據層次結構中的最低位置。

使用迭代技術

我們可以應用於查詢葉子節點和非葉子節點的一種蠻力方法是採用迭代技術。我們可以迭代巢狀字典，並在每次迭代中檢查元素是否連線任何其他節點（子節點）。如果它有子節點，我們將繼續將節點儲存在葉子節點類別中。另一方面，如果它沒有任何其他子節點，我們將將其標記為非葉子節點。

示例

在下面的示例中，我們建立了三個函式，分別是 `is_leaf_node`、`find_leaf_nodes` 和 `find_non_leaf_nodes`。它們分別查詢任何節點是否是葉子節點，查詢巢狀字典的葉子節點和非葉子節點。

def is_leaf_node(node, tree):
    if node not in tree:
        return False
    return "children" not in tree[node]
def find_leaf_nodes(tree):
    leaf_nodes = []
    for node in tree:
        if is_leaf_node(node, tree):
            leaf_nodes.append(node)
    return leaf_nodes
def find_non_leaf_nodes(tree):
    non_leaf_nodes = []
    for node in tree:
        if not is_leaf_node(node, tree):
            non_leaf_nodes.append(node)
    return non_leaf_nodes
tree = {"A": {"value": 1},"B": {"value": 2},"C": {"value": 3},"X": {"value": None,"children": ["A", "B"]},"Y": {"value": None,"children": ["C"]}}
leaf_nodes = find_leaf_nodes(tree)
print("Leaf nodes:", leaf_nodes)
non_leaf_nodes = find_non_leaf_nodes(tree)
print("Non-leaf nodes:", non_leaf_nodes)

輸出

Leaf nodes: ['A', 'B', 'C']
Non-leaf nodes: ['X', 'Y']

使用列表推導式

列表推導式是 Python 中一種流行的方法，它可以將多個表示式組合在一行中以生成列表的元素。如果巢狀字典已經將節點標記為葉子節點還是非葉子節點，那麼我們可以採用這種方法。

示例

在下面的示例中，我們建立了兩個函式 `find_leaf_nodes` 和 `find_non_leaf_nodes`，它們使用列表推導式來查詢葉子節點和非葉子節點。在列表推導式中，我們使用了表示式來檢查 `is_leaf` 的值是否為 True。如果為 True，我們將其保留為葉子節點；如果為 False，我們將其保留在非葉子節點類別中。

def find_leaf_nodes(tree):
    leaf_nodes = [node for node, data in tree.items() if data.get("is_leaf")]
    return leaf_nodes

def find_non_leaf_nodes(tree):
    non_leaf_nodes = [node for node, data in tree.items() if "children" in data]
    return non_leaf_nodes
tree = {"A": {"value": 1, "is_leaf": True},"B": {"value": 2,"is_leaf": True},"C": {"value": 3,"is_leaf": True},"X": {"value": None,"children": ["A", "B"]},"Y": {"value": None,"children": ["C"]}}
leaf_nodes = find_leaf_nodes(tree)
print("Leaf nodes:", leaf_nodes)
non_leaf_nodes = find_non_leaf_nodes(tree)
print("Non-leaf nodes:", non_leaf_nodes)

輸出

Leaf nodes: ['A', 'B', 'C']
Non-leaf nodes: ['X', 'Y']

使用父子關係

如果字典維護父子關係，我們也可以使用列表推導式或類似的方法。儘管在諸如 Node 之類的類中，我們可以使用指標和其他方法定義父子關係，但在 Python 字典中，我們只能根據鍵值對來維護關係。

示例

在下面的示例中，我們使用列表推導式來查詢葉子節點和非葉子節點。我們首先使用 Python 中的 `items` 方法獲取所有鍵值對。接下來，檢查節點是否是另一個節點的值（這意味著它是非葉子節點）。

def find_leaf_nodes(tree):
    leaf_nodes = [node for node, _ in tree.items() if node not in tree.values()]
    return leaf_nodes
def find_non_leaf_nodes(tree):
    non_leaf_nodes = [node for node, _ in tree.items() if node in tree.values()]
    return non_leaf_nodes
tree = {
    "A": None,
    "B": "X",
    "C": "Y",
    "X": "root",
    "Y": "root"
}
leaf_nodes = find_leaf_nodes(tree)
print("Leaf nodes:", leaf_nodes)
non_leaf_nodes = find_non_leaf_nodes(tree)
print("Non-leaf nodes:", non_leaf_nodes)

輸出

Leaf nodes: ['A', 'B', 'C']
Non-leaf nodes: ['X', 'Y']

結論

在本文中，我們瞭解瞭如何在巢狀字典中處理葉子節點和非葉子節點。我們使用了多種方法來執行相同的操作，例如迭代方法——這是一種蠻力方法。接下來，我們還使用了列表推導式以及 `items` 和 `values` 方法。應該應用哪種方法取決於字典的結構。