说出二叉树的两种存储方式

二叉树有两种常见的存储方式，分别是二叉链表表示法和左子节点右兄弟节点表示法。

1. 二叉链表表示法：
在二叉链表表示法中，每个节点都包含三个字段：数据域、左子节点指针和右子节点指针。通过这种方式，可以轻松地表示二叉树的结构关系。具体来说，每个节点的左子节点指针指向其左子节点，右子节点指针指向其右子节点。如果某个节点没有左子节点或右子节点，相应的指针字段则为空。

2. 左子节点右兄弟节点表示法：
在左子节点右兄弟节点表示法中，每个节点都包含两个字段：数据域和指向其第一个子节点的指针。通过这种方式，可以将二叉树转化为多叉树的形式。具体来说，每个节点的指针指向其第一个子节点，而该子节点的指针则指向其右兄弟节点。这样，可以通过节点之间的指针关系来表示二叉树的结构。

相关问题

试以两种不同的遍历方式，建立二叉树的链式存储结构。

二叉树的链式存储结构可以通过两种不同的遍历方式来建立，分别是前序遍历和中序遍历。

1. 前序遍历建立二叉树的链式存储结构

前序遍历是先访问根结点，再遍历左子树和右子树。因此，我们可以先读入根结点的值，然后递归读入左子树和右子树的值，直到遇到空结点为止。

具体实现如下：

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

TreeNode* buildTree(vector<int>& preorder) {
    if (preorder.empty()) {
        return NULL;
    }
    int val = preorder[0];
    TreeNode* root = new TreeNode(val);
    vector<int> left_preorder, right_preorder;
    for (int i = 1; i < preorder.size(); i++) {
        if (preorder[i] < val) {
            left_preorder.push_back(preorder[i]);
        } else {
            right_preorder.push_back(preorder[i]);
        }
    }
    root->left = buildTree(left_preorder);
    root->right = buildTree(right_preorder);
    return root;
}

2. 中序遍历建立二叉树的链式存储结构

中序遍历是先遍历左子树，再访问根结点和右子树。因此，我们可以递归读入左子树和右子树的值，直到遇到空结点，然后读入根结点的值。

具体实现如下：

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

TreeNode* buildTree(vector<int>& inorder, int left, int right) {
    if (left > right) {
        return NULL;
    }
    int mid = (left + right) / 2;
    TreeNode* root = new TreeNode(inorder[mid]);
    root->left = buildTree(inorder, left, mid - 1);
    root->right = buildTree(inorder, mid + 1, right);
    return root;
}

TreeNode* buildTree(vector<int>& inorder) {
    return buildTree(inorder, 0, inorder.size() - 1);
}

以上代码中，我们首先定义了一个 TreeNode 结构体，然后分别实现了前序遍历和中序遍历建立二叉树的链式存储结构的函数。其中，前序遍历函数 buildTree() 采用了递归的思想，中序遍历函数 buildTree() 采用了二分查找的思想。

二叉树的创建和三种遍历方式

二叉树是一种经常用于数据存储和搜索的数据结构。它由节点构成，每个节点最多有两个子节点，分别称为左子节点和右子节点。以下是二叉树的创建和三种遍历方式：

1. 创建二叉树

二叉树的创建可以通过递归或非递归方式实现。以下是递归方式的示例代码：

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

TreeNode* createTree(vector<int>& nums, int index) {
    if (index >= nums.size() || nums[index] == -1) {
        return NULL;
    }
    TreeNode* root = new TreeNode(nums[index]);
    root->left = createTree(nums, index * 2 + 1);
    root->right = createTree(nums, index * 2 + 2);
    return root;
}

// 调用方式：TreeNode* root = createTree(nums, 0);
// 其中 nums 是二叉树的层次遍历序列，-1 表示空节点。

2. 三种遍历方式

二叉树的遍历方式分为前序遍历、中序遍历和后序遍历。以下是递归方式的示例代码：

前序遍历：根节点 -> 左子树 -> 右子树

void preOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

// 调用方式：preOrder(root);

中序遍历：左子树 -> 根节点 -> 右子树

void inOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

// 调用方式：inOrder(root);

后序遍历：左子树 -> 右子树 -> 根节点

void postOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << " ";
}

// 调用方式：postOrder(root);