二叉树的链式储存结构

### 二叉树的链式存储结构概述

在计算机科学中，二叉树是一种重要的非线性数据结构。当采用链式存储时，每个节点由三部分组成：左子树指针、节点的数据域以及右子树指针[^1]。

这种表示法允许灵活地处理任意形状的二叉树而不会造成不必要的内存浪费，尤其适合那些不是完全或接近满状态下的情况[^2]。

### 节点定义

为了实现二叉树的链式存储，在编程语言层面通常会创建一个类来描述单个节点：

struct TreeNode {
    int val;                    // 存储节点值
    struct TreeNode *left;      // 左孩子指向
    struct TreeNode *right;     // 右孩子指向
    
    TreeNode(int x):val(x), left(nullptr), right(nullptr){}  
};

上述代码片段展示了如何用C++定义一棵二叉树中的节点。这里`TreeNode`是一个自定义类型的结构体，它包含了三个成员变量用于保存当前节点的信息及其两个孩子的链接地址[^4]。

### 创建与初始化

构建具体的实例可以通过动态分配内存并设置相应属性完成:

// 构建根节点
TreeNode* root = new TreeNode(1);

// 添加左右子节点
root->left = new TreeNode(2);
root->right = new TreeNode(3);

这段简单的例子说明了怎样建立一颗具有三个元素的小型二叉树，并为其指定初始数值。

### 插入新节点

向已有的二叉树中添加新的叶子节点可以依据具体需求设计不同的算法逻辑；常见的做法是从根部开始逐层查找合适的位置再执行插入动作。下面给出了一种可能的方法框架：

void insert(TreeNode*& node, int value){
    if (node == nullptr){
        node = new TreeNode(value);    
    }else{
        queue<TreeNode*> q;
        q.push(node);
        
        while(!q.empty()){
            TreeNode* temp = q.front();
            q.pop();

            if(temp->left != NULL)
                q.push(temp->left);
            else{
                temp->left = new TreeNode(value);
                break;
            }

            if(temp->right != NULL)
                q.push(temp->right);
            else{
                temp->right = new TreeNode(value);
                break;
            }
        }
    }
}

此函数实现了广度优先搜索策略以找到第一个可用位置并将给定值作为新叶加入其中[^3]。