二元樹建立、追踪、求樹高例

 class Node:

    def __init__(self, value):

        self.value = value

        self.left = None

        self.right = None

class BinarySearchTree:

    def __init__(self):

        self.root = None

    def insert(self, value):

        if self.root is None:

            self.root = Node(value)

        else:

            self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):

        if value < node.value:

            if node.left is None:

                node.left = Node(value)

            else:

                self._insert_recursive(node.left, value)

        else:

            if node.right is None:

                node.right = Node(value)

            else:

                self._insert_recursive(node.right, value)

    def search(self, value):

        return self._search_recursive(self.root, value)

    def _search_recursive(self, node, value):

        if node is None:

            return False

        if node.value == value:

            return True

        elif value < node.value:

            return self._search_recursive(node.left, value)

        else:

            return self._search_recursive(node.right, value)

    def preorder_traversal(self):

        result = []

        self._preorder_recursive(self.root, result)

        return result

    def _preorder_recursive(self, node, result):

        if node:

            result.append(node.value)

            self._preorder_recursive(node.left, result)

            self._preorder_recursive(node.right, result)

    def inorder_traversal(self):

        result = []

        self._inorder_recursive(self.root, result)

        return result

    def _inorder_recursive(self, node, result):

        if node:

            self._inorder_recursive(node.left, result)

            result.append(node.value)

            self._inorder_recursive(node.right, result)

    def postorder_traversal(self):

        result = []

        self._postorder_recursive(self.root, result)

        return result

    def _postorder_recursive(self, node, result):

        if node:

            self._postorder_recursive(node.left, result)

            self._postorder_recursive(node.right, result)

            result.append(node.value)

    def height(self):

        return self._height_recursive(self.root)

    def _height_recursive(self, node):

        if node is None:

            return 0

        else:

            left_height = self._height_recursive(node.left)

            right_height = self._height_recursive(node.right)

            return 1 + max(left_height, right_height)

    def diameter(self):

        return self._diameter_recursive(self.root)[1]

    def _diameter_recursive(self, node):

        if node is None:

            return 0, 0

        left_height, left_diameter = self._diameter_recursive(node.left)

        right_height, right_diameter = self._diameter_recursive(node.right)

        current_diameter = left_height + right_height

        max_diameter = max(current_diameter, left_diameter, right_diameter)

        current_height = 1 + max(left_height, right_height)

        return current_height, max_diameter

# 測試

bst = BinarySearchTree()

for value in [5, 3, 2, 7, 1, 6, 4]:

    bst.insert(value)

print('搜尋 5:', bst.search(5))

print('搜尋 2:', bst.search(2))

print('前序遍歷:', bst.preorder_traversal())

print('中序遍歷:', bst.inorder_traversal())

print('後序遍歷:', bst.postorder_traversal())

print('樹的高度:', bst.height())

print('樹的直徑（最大距離）:', bst.diameter())

# 執行結果：

# 搜尋 5: True

# 搜尋 2: True

# 前序遍歷: [5, 3, 2, 1, 4, 7, 6]

# 中序遍歷: [1, 2, 3, 4, 5, 6, 7]

# 後序遍歷: [1, 2, 4, 3, 6, 7, 5]

# 樹的高度: 4

# 樹的直徑（最大距離）: 5