保存一個b-tree檔案以供稍后使用python讀取

我有一個使用 python 創建 B 樹的演算法，我需要的是一種將這個 B 樹保存在光碟中的方法，以后可以用 python 讀取它，最好的方法是什么？

uj5u.com熱心網友回復：

將樹寫入檔案的一種方法是提出一個記錄結構（基于文本或二進制）并遍歷樹中的所有節點，從葉子開始一直到根。當您寫入每個節點時，您將值及其鄰居寫入檔案，并記下該節點在節點上寫入的位置。在寫入其鄰居時，您將地址寫入檔案中。

加載檔案時，從根記錄開始，設定其值，獲取左鄰居的地址，獲取該記錄，設定其值等，右鄰居也是如此。

我不會為您鏈接的現有代碼撰寫和測驗所有代碼，但這里有一個簡單的示例，展示了基本思想：

from random import randint
from dataclasses import dataclass
from typing import BinaryIO, ClassVar, Union

# A simple unbalanced tree node with an add method
@dataclass
class Node:
    # write to file as 2-byte integers
    int_size: ClassVar[int] = 2
    value: int = None
    address: int = None
    left: Union['Node', int] = None
    right: Union['Node', int] = None

    def add(self, value):
        p = self
        while True:
            if value > p.value:
                if p.right is None:
                    p.right = Node(value=value)
                    break
                else:
                    p = p.right
            elif value < p.value:
                if p.left is None:
                    p.left = Node(value=value)
                    break
                else:
                    p = p.left
            else:
                # value already in tree
                break

    @classmethod
    def _write_int(cls, f: BinaryIO, i: int):
        f.write(i.to_bytes(length=cls.int_size, byteorder='big'))

    @classmethod
    def _write_node(cls, f: BinaryIO, node: 'Node'):
        f.write(node.value.to_bytes(length=cls.int_size, byteorder='big'))
        f.write((node.left.address if node.left is not None else 0).to_bytes(length=cls.int_size, byteorder='big'))
        f.write((node.right.address if node.right is not None else 0).to_bytes(length=cls.int_size, byteorder='big'))

    @classmethod
    def _read_int(cls, f: BinaryIO):
        return int.from_bytes(f.read(cls.int_size), byteorder='big')

    @classmethod
    def _read_node(cls, f: BinaryIO, node: 'Node'):
        node.value = int.from_bytes(f.read(cls.int_size), byteorder='big')
        node.left = int.from_bytes(f.read(cls.int_size), byteorder='big')
        node.right = int.from_bytes(f.read(cls.int_size), byteorder='big')

    def save(self, f: BinaryIO):
        # seek the start of the file and write a dummy root record
        f.seek(0)
        self._write_int(f, self.value)
        self._write_int(f, 0)
        self._write_int(f, 0)

        stack = []
        p = self
        while True:
            if p.left is not None and p.left.address is None:
                stack.append(p)
                p = p.left
            elif p.right is not None and p.right.address is None:
                stack.append(p)
                p = p.right
            else:
                p.address = f.tell()
                self._write_node(f, p)
                if stack:
                    p = stack.pop()
                else:
                    break

        # rewrite root node with correct location of left and right nodes
        f.seek(0)
        self._write_node(f, self)

    def load(self, f: BinaryIO):
        f.seek(0)
        self.address = 0

        def load_side(side: str):
            # this function avoids repeating this code twice for .left and .right,
            # working around Python not having pointers, otherwise you'd just point at the attributes
            nonlocal f, p, stack
            if not isinstance(getattr(p, side), int):
                return False
            if not getattr(p, side):
                setattr(p, side, None)
            else:
                f.seek(getattr(p, side))
                setattr(p, side, Node())
                stack.append(p)
                p = getattr(p, side)
                self._read_node(f, p)
            return True

        stack = []
        p = self
        self._read_node(f, p)
        while True:
            if not load_side('left') and not load_side('right'):
                if stack:
                    p = stack.pop()
                else:
                    break

    def print(self):
        stack = []
        p = self
        left_done = False
        right_done = False
        while True:
            if not left_done and p.left is not None:
                stack.append((p, True, False))
                p, left_done, right_done = p.left, False, False
            elif not right_done and p.right is not None:
                stack.append((p, True, True))
                p, left_done, right_done = p.right, False, False
            else:
                print(f'value: {p.value}, '
                      f'left: {p.left.value if p.left else "none"}, '
                      f'right: {p.right.value if p.right else "none"}')
                if stack:
                    p, left_done, right_done = stack.pop()
                else:
                    break


values = [randint(0, 100) for __ in range(10)]
root = Node(values[0])
for v in values[1:]:
    root.add(v)
print('\nTree after construction:')
root.print()

# save the tree
with open('tree.bin', 'wb') as f:
    root.save(f)

# start a new and empty tree
root = Node()
# read the tree
with open('tree.bin', 'rb') as f:
    root.load(f)
print('\nResult after load:')
root.print()

這會將樹寫入 2 位元組無符號整數二進制檔案（更改該大小是微不足道的），其中對左子和右子的參考表示為檔案中記錄的檔案位置。

該示例避免了遞回呼叫，因為嚴重不平衡的 b 樹可能會迅速接近最大遞回深度。

示例結果（列印函式最終在底部列印根，當然可以列印更好的，但這只是為了演示它的作業原理）：

Tree after construction:
value: 15, left: none, right: none
value: 18, left: 15, right: none
value: 30, left: 18, right: none
value: 41, left: 30, right: none
value: 11, left: none, right: 41
value: 54, left: none, right: none
value: 74, left: 54, right: none
value: 81, left: none, right: none
value: 78, left: 74, right: 81
value: 45, left: 11, right: 78

Result after load:
value: 15, left: none, right: none
value: 18, left: 15, right: none
value: 30, left: 18, right: none
value: 41, left: 30, right: none
value: 11, left: none, right: 41
value: 54, left: none, right: none
value: 74, left: 54, right: none
value: 81, left: none, right: none
value: 78, left: 74, right: 81
value: 45, left: 11, right: 78

請注意，即使是基本示例，也需要相當多的代碼。在這個特定的例子中，將值存盤在一個檔案中并按照最初構造樹的方式重建樹可能更有意義，因為樹的結構是完全確定的。

但是在某些情況下您可能不想這樣做 - 例如，如果您添加允許在檔案中重寫節點值的功能，重建將導致不同的（盡管仍然正確）樹。

還要注意上面提供的代碼有一個缺陷：如果你嘗試保存同一棵樹兩次，它會失敗，因為它使用地址來確定一個節點是否已經被寫入——這留給讀者作為練習來解決這個問題. 您可以單獨跟蹤，也可以在保存之前重置整個樹的地址。

標籤：Python 文件

上一篇：PHP查看檔案夾內容

下一篇：如何使用JavaPrintWriter將void型別方法的結果列印到檔案中