1、用创建结点方法创建二叉树； 2、层次遍历算法实现； 3、将二叉树的顺序存储结构转换为链式存储结构非递归算法和递归算法； 4、垂直输出二叉树；

1. **创建结点方法创建二叉树**:
创建二叉树通常涉及定义一个包含数据和指向子节点指针的结点类。例如：

class Node {
public:
    int data;
    Node* left;
    Node* right;

    // 构造函数
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

要构建二叉树，你可以按照已知的值或特定规则递归地创建节点。这里是一个简单的插入函数示例：

Node* insert(Node* root, int value) {
    if (root == nullptr) return new Node(value); // 新的根节点
    if (value < root->data) root->left = insert(root->left, value);
    else root->right = insert(root->right, value);
    return root;
}

2. **层次遍历（广度优先搜索）算法实现**:
使用队列进行层次遍历，先进先出的特性保证了按层访问：

void levelOrderTraversal(Node* root) {
    if (root == nullptr) return;

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* node = q.front();
        cout << node->data << " ";
        q.pop();

        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

3. **顺序存储结构转链式存储结构**:
- 非递归方法：
遍历数组，每次移动到下一个元素时，将当前元素连接到前一个元素的右子节点上。

- 递归方法：
可以使用递归辅助函数，对每个元素创建新的节点并将其添加到前一个节点的链表中。

4. **垂直输出二叉树（也称树的锯齿形输出）**:
这种方式通常用于打印二叉树，让每个节点的左孩子在该节点上方，右孩子在下方。可以借助二维数组记录左右孩子的行差，然后依次打印节点：

void verticalPrint(Node* root, int& maxLevel, vector<vector<int>>& output) {
    if (root == nullptr) return;

    maxLevel = max(maxLevel, root->level);
    output[root->level].push_back(root->data);

    verticalPrint(root->left, maxLevel, output);
    verticalPrint(root->right, maxLevel, output);
}

// 主函数调用
int main() {
    // 初始化二维数组和最大级数
    vector<vector<int>> output(maxLevel, vector<int>());
    int maxLevel = 0;

    // 打印树
    verticalPrint(root, maxLevel, output);
    for (const auto& row : output)
        for (auto val : row)
            cout << val << " ";
    return 0;
}