写一个C++代码树和二叉树的各种存储结构，各种操作的算法实现（建立、遍历、二叉树的线索化、最优

在C++中，我们通常会使用`TreeNode`结构体来表示树和二叉树的节点，并分别使用不同的存储结构来实现。这里是一个简单的例子展示了三种常见的存储结构：数组表示法（顺序存储）、链表表示法（无序存储）以及链式存储下的线索化二叉树。请注意，这只是基础版的实现，更复杂的操作（如平衡二叉树）通常会有更复杂的算法。

**1. 数组表示法（顺序存储）**

struct TreeNode {
    int val;
    int left, right;
};

void buildArrayTree(int arr[], int n, TreeNode** &root) {
    if (n == 0) return;
    root = new TreeNode(arr[0]);
    buildArrayTree(arr + 1, n - 1, &root->left);
    buildArrayTree(arr + n / 2 + 1, n - n / 2 - 1, &root->right);
}

// 示例遍历（假设arr[]代表已排序的数组）
void inorderTraversal(TreeNode* root, vector<int>& result) {
    stack<TreeNode*> s;
    while (root || !s.empty()) {
        while (root) {
            s.push(root);
            root = root->left;
        }
        root = s.top();
        s.pop();
        result.push_back(root->val);
        root = root->right;
    }
}

**2. 链表表示法（无序存储）**

struct TreeNode {
    int val;
    TreeNode* left, *right;
};

TreeNode* createNode(int val) {
    TreeNode* node = new TreeNode{val};
    return node;
}

// 创建链式二叉树
TreeNode* buildBinaryTree(vector<int> &values) {
    // 使用迭代或递归创建二叉树
}

// 遍历
void inorderTraversal(TreeNode* root, vector<int>& result) {
    stack<TreeNode*> s;
    while (root || !s.empty()) {
        while (root) {
            s.push(root);
            root = root->left;
        }
        root = s.top();
        s.pop();
        result.push_back(root->val);
        root = root->right;
    }
}

**3. 线索化二叉树（链式存储）**
线索化主要是为了简化查找失败的情况处理，如前驱、后继节点。这里仅展示部分更新线索的部分：

void linkify(TreeNode*& node) {
    if (node && node->left) {
        node->left->prev = node;
    }
    if (node && node->right) {
        node->right->next = node;
    }
}

// 删除节点时更新线索
void deleteNode(TreeNode*& root, TreeNode* node) {
    if (node->left) {
        node->left->prev = node->prev;
    }
    if (node->right) {
        node->right->next = node->next;
    }
    if (node->prev) {
        node->prev->next = node->next;
    }
    if (node->next) {
        node->next->prev = node->prev;
    }
    delete node;
}

**相关问题--:**
1. 顺序存储和链式存储各自的优点和缺点是什么？
2. 怎么样判断一个二叉树是否是平衡二叉树？
3. 二叉树线索化的具体应用场景有哪些？