二叉树——课上练（顺序存储结构）

二叉树的顺序存储结构是指使用数组来按照完全二叉树的顺序存储二叉树的各个节点。在顺序存储结构中，我们可以通过数组的索引来表示每个节点的位置关系。对于一个深度为d的二叉树，我们可以分配一个长度为2^(d+1)-1的数组来存储它。在数组中，根节点存储在索引为0的位置，其左子节点存储在索引为2i+1的位置，右子节点存储在索引为2i+2的位置（i为父节点的索引）。如果某个节点为空，则用一个特殊的符号（如'#'）表示。

相关问题

二叉树——课上练（链式存储结构）

二叉树的链式存储结构是通过定义一个含有数据和指向左右子节点的指针的结构体来实现的。每个结点都包含一个数据项和两个指针，分别指向其左子节点和右子节点。采用链式存储结构的优点是可以灵活地插入、删除和修改节点，但相应的缺点是需要更多的存储空间和额外的指针操作。

在建立二叉树时，可以按照先序遍历的顺序输入节点序列，并采用递归方式进行建立。例如，按照先序输入的节点序列为：a b c # # # d e # f # # g # #。其中，#表示空节点。通过递归方式建立二叉树可以保证节点的插入顺序与先序输入的顺序一致。

关于二叉树的一些特性和存储方式，还有以下几点：
1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个节点。
2. 若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大节点数是2^k-1。
3. 对任何一棵二叉树，如果其叶节点个数为n0，度为2的非叶节点个数为n2，则有n0 = n2 + 1。
4. 具有n个节点的完全二叉树的深度k为log2(n+1)向上取整。

已知二叉树t，分别采用顺序存储结构、二叉链表存储结构实现求二叉树的深度，并对二叉树分别进行中序遍历的代码

在计算机科学中，求解二叉树的深度以及对其进行中序遍历，可以针对两种常见的二叉树数据结构——顺序存储结构和二叉链表存储结构进行。

### 1. 顺序存储结构 (数组实现)

假设二叉树节点存储在一个一维数组`nodes[]`中，根节点在数组的第一个位置，左孩子是下标 *2*i* + 1，右孩子是下标 *2*i* + 2。我们可以通过递归的方式计算深度：

int binaryTreeDepth(int nodes[], int start, int end) {
    if (start > end)
        return 0;
    else {
        int mid = (start + end) / 2;
        return 1 + max(binaryTreeDepth(nodes, start, mid - 1), binaryTreeDepth(nodes, mid + 1, end));
    }
}

然后通过递归遍历进行中序序列：

void inorderTraversal(int nodes[], int start, int end, vector<int>& res) {
    if (start <= end) {
        inorderTraversal(nodes, start * 2 + 1, end, res); // 左子树
        res.push_back(nodes[start]); // 当前节点
        inorderTraversal(nodes, start * 2 + 2, end, res); // 右子树
    }
}

### 2. 二叉链表存储结构

对于二叉链表，每个节点包含指向左右孩子的指针`left`和`right`。我们可以直接从根节点开始计数深度，并使用迭代方式完成中序遍历：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int binaryTreeDepth(TreeNode* root) {
    if (root == nullptr)
        return 0;
    else
        return 1 + max(binaryTreeDepth(root->left), binaryTreeDepth(root->right));
}

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