本文共 8017 字，大约阅读时间需要 26 分钟。
对于线性表、栈、队列等数据结构，数据都可以使用物理有序和逻辑有序的方式存储，二叉树也可以使用这两种方式存储。然而，二叉树的特点决定了其存储结构与传统线性数据结构有所不同。
物理有序将数据存储在连续的内存空间中，例如存储在一个列表中，这种方式在遍历速度上有一定优势。然而，二叉树的节点通过父子关系连接，直接使用线性列表存储不容易体现树的结构。因此，二叉树通常以链式方式存储，反映其层次结构。
完全二叉树是一种特殊的二叉树，其节点按从上到下、从左到右的顺序依次排列，且不存在空隙。为了从简到繁地实现完全二叉树，我们先定义一个节点类Node。
class Node(object): def __init__(self, data): self.data = data self.parent = None self.left_child = None self.right_child = None
节点类中，data属性存储节点的值，parent属性指向父节点，left_child和right_child属性分别指向左、右子节点。
接下来，我们定义一个完全二叉树类PerfectBinaryTree。
class PerfectBinaryTree(object): def __init__(self): self.__root = None self.prefix_branch = '├' self.prefix_trunk = '|' self.prefix_leaf = '└' self.prefix_empty = '' self.prefix_left = '─L─' self.prefix_right = '─R─' def is_empty(self): return not self.__root
为了在完全二叉树中添加节点，我们需要找到添加的位置。我们使用队列来实现层次遍历，确保从上到下、从左到右依次找到空位。
class TreeQueue(object): def __init__(self): self.__members = list() def is_empty(self): return not len(self.__members) def enter(self, data): self.__members.insert(0, data) def outer(self): if self.is_empty(): return return self.__members.pop()
接下来实现append方法，用于将节点添加到完全二叉树中。
def append(self, data): node = Node(data) if self.is_empty(): self.__root = node return queue = TreeQueue() queue.enter(self.__root) while not queue.is_empty(): cur = queue.outer() if cur.left_child is None: cur.left_child = node node.parent = cur return queue.enter(cur.left_child) if cur.right_child is None: cur.right_child = node node.parent = cur return queue.enter(cur.right_child)
为了方便展示数据，我们实现show方法。
def show(self): if self.is_empty(): print('空二叉树') return queue = TreeQueue() queue.enter(self.__root) while not queue.is_empty(): cur = queue.outer() print(cur.data, end=' ') if cur.left_child is not None: queue.enter(cur.left_child) if cur.right_child is not None: queue.enter(cur.right_child) print() 为了判断节点是否存在，我们实现is_exist方法。
def is_exist(self, data): if self.is_empty(): return False queue = TreeQueue() queue.enter(self.__root) while not queue.is_empty(): cur = queue.outer() if cur.data == data: return True if cur.left_child is not None: queue.enter(cur.left_child) if cur.right_child is not None: queue.enter(cur.right_child) return False
为了展示树形结构，我们实现show_tree方法。
def show_tree(self): if self.is_empty(): print('空二叉树') return print(self.__root.data) self.__print_tree(self.__root) def __print_tree(self, node, prefix=None): if prefix is None: prefix = '' prefix_left_child = '' else: prefix = prefix.replace(self.prefix_branch, self.prefix_trunk) prefix = prefix.replace(self.prefix_leaf, self.prefix_empty) prefix_left_child = prefix.replace(self.prefix_leaf, self.prefix_empty) if self.has_child(node): if node.right_child is not None: print(prefix + self.prefix_branch + self.prefix_right + str(node.right_child.data)) if self.has_child(node.right_child): self.__print_tree(node.right_child, prefix + self.prefix_branch + ' ') else: print(prefix + self.prefix_branch + self.prefix_right) if node.left_child is not None: print(prefix + self.prefix_leaf + self.prefix_left + str(node.left_child.data)) if self.has_child(node.left_child): prefix_left_child += ' ' self.__print_tree(node.left_child, self.prefix_leaf + prefix_left_child) else: print(prefix + self.prefix_leaf + self.prefix_left)def has_child(self, node): return node.left_child is not None or node.right_child is not None
class Node(object): def __init__(self, data): self.data = data self.parent = None self.left_child = None self.right_child = Noneclass TreeQueue(object): def __init__(self): self.__members = list() def is_empty(self): return not len(self.__members) def enter(self, data): self.__members.insert(0, data) def outer(self): if self.is_empty(): return return self.__members.pop()class PerfectBinaryTree(object): def __init__(self): self.__root = None self.prefix_branch = '├' self.prefix_trunk = '|' self.prefix_leaf = '└' self.prefix_empty = '' self.prefix_left = '─L─' self.prefix_right = '─R─' def is_empty(self): return not self.__root def append(self, data): node = Node(data) if self.is_empty(): self.__root = node return queue = TreeQueue() queue.enter(self.__root) while not queue.is_empty(): cur = queue.outer() if cur.left_child is None: cur.left_child = node node.parent = cur return queue.enter(cur.left_child) if cur.right_child is None: cur.right_child = node node.parent = cur return queue.enter(cur.right_child) def show(self): if self.is_empty(): print('空二叉树') return queue = TreeQueue() queue.enter(self.__root) while not queue.is_empty(): cur = queue.outer() print(cur.data, end=' ') if cur.left_child is not None: queue.enter(cur.left_child) if cur.right_child is not None: queue.enter(cur.right_child) print() def is_exist(self, data): if self.is_empty(): return False queue = TreeQueue() queue.enter(self.__root) while not queue.is_empty(): cur = queue.outer() if cur.data == data: return True if cur.left_child is not None: queue.enter(cur.left_child) if cur.right_child is not None: queue.enter(cur.right_child) return False def show_tree(self): if self.is_empty(): print('空二叉树') return print(self.__root.data) self.__print_tree(self.__root) def __print_tree(self, node, prefix=None): if prefix is None: prefix = '' prefix_left_child = '' else: prefix = prefix.replace(self.prefix_branch, self.prefix_trunk) prefix = prefix.replace(self.prefix_leaf, self.prefix_empty) prefix_left_child = prefix.replace(self.prefix_leaf, self.prefix_empty) if self.has_child(node): if node.right_child is not None: print(prefix + self.prefix_branch + self.prefix_right + str(node.right_child.data)) if self.has_child(node.right_child): self.__print_tree(node.right_child, prefix + self.prefix_branch + ' ') else: print(prefix + self.prefix_branch + self.prefix_right) if node.left_child is not None: print(prefix + self.prefix_leaf + self.prefix_left + str(node.left_child.data)) if self.has_child(node.left_child): prefix_left_child += ' ' self.__print_tree(node.left_child, self.prefix_leaf + prefix_left_child) else: print(prefix + self.prefix_leaf + self.prefix_left) def has_child(self, node): return node.left_child is not None or node.right_child is not Noneif __name__ == '__main__': tree = PerfectBinaryTree() print(tree) print("is_empty: ", tree.is_empty()) tree.show() for i in range(15): tree.append(i) tree.show() print(tree.is_exist(2)) print(tree.is_exist(200)) tree.show_tree() 转载地址：http://kzppz.baihongyu.com/