二叉树顺序存储结构和链式存储结构

### 二叉树的两种存储方式

#### 顺序存储结构的特点及实现

对于完全二叉树和满二叉树，顺序存储结构能够最大化地利用存储空间，并且方便通过数组下标快速访问节点[^1]。然而，这种存储方法并不适用于所有的二叉树形态。对于一般的二叉树，尤其是那些深度较大但节点数量较少的情况（例如右单支树），顺序存储将会造成大量不必要的空间浪费，因为需要为不存在的节点预留位置。

在实际编程中，可以使用一维数组来表示一棵二叉树：

class BinaryTreeArray:
    def __init__(self, size):
        self.tree = [None] * size
    
    def set_value(self, index, value):
        if index >= 0 and index < len(self.tree):
            self.tree[index] = value
            
    def get_parent_index(self, child_index):
        return (child_index - 1) // 2
        
    def get_left_child_index(self, parent_index):
        return 2 * parent_index + 1
        
    def get_right_child_index(self, parent_index):
        return 2 * parent_index + 2

此代码片段展示了如何创建一个基于数组的简单二叉树类以及一些基本的操作函数[^2]。

#### 链式存储结构的特点及实现

链式存储允许元素被随机放置于内存中的不同位置，这使得它更适合处理各种形状不规则的二叉树。但是，由于每个节点除了保存自身的数据外还需要额外记录指向子节点的链接信息，因此整体上占用的空间更多。此外，在查找特定节点时可能需要遍历整个列表才能找到目标项，效率相对较低。

下面是一个简单的Python版本的二叉树节点定义及其插入新节点的方法：

class TreeNode:
    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None


def insert_node(root, new_key):
    queue = []
    queue.append(root)

    while(len(queue)):
        temp = queue.pop(0)

        if not temp.left:
            temp.left = TreeNode(new_key)
            break
        else:
            queue.append(temp.left)

        if not temp.right:
            temp.right = TreeNode(new_key)
            break
        else:
            queue.append(temp.right)

这段程序实现了向给定根节点`root`对应的二叉树中添加新的键值`new_key`的功能。