采用递归方法建立一颗含有n个节点的二叉树，采用二叉链表存储

二叉树的递归建树算法如下：

1. 如果n为0，返回NULL。

2. 新建一个节点p。

3. 递归建立左子树，将左子树的根节点赋值给p的左指针。

4. 递归建立右子树，将右子树的根节点赋值给p的右指针。

5. 返回p。

代码实现如下：

typedef struct node {
    int data;
    struct node* left;
    struct node* right;
} Node;

Node* buildTree(int n) {
    if (n == 0) {
        return NULL;
    }
    Node* p = (Node*)malloc(sizeof(Node));
    p->data = n;
    p->left = buildTree(n-1);
    p->right = buildTree(n-1);
    return p;
}

其中，n为节点数目，buildTree函数返回一颗含有n个节点的二叉树的根节点。在此基础上，我们可以采用二叉链表存储二叉树，即每个节点包含数据域和左右指针域，指向其左右子节点。

相关问题

建立一棵含有n个结点的二叉树，并采用二叉链表存储 C语言

定义二叉树结构体节点类型：

typedef struct TreeNode {
    int val; // 节点值
    struct TreeNode* left; // 左子树指针
    struct TreeNode* right; // 右子树指针
} TreeNode;

定义二叉树的创建函数，以先序遍历的方式输入二叉树节点的值：

// 创建二叉树
TreeNode* createBinaryTree(int arr[], int n, int i)
{
    if (i >= n || arr[i] == -1) { // 如果节点为-1或者i>=n，返回NULL
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); // 创建节点
    root->val = arr[i]; // 节点赋值
    root->left = createBinaryTree(arr, n, 2 * i + 1); // 递归创建左子树
    root->right = createBinaryTree(arr, n, 2 * i + 2); // 递归创建右子树
    return root; // 返回根节点
}

其中，arr是节点值数组，n是节点个数，i是当前节点索引。

例如，创建一个如下所示的二叉树：

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

可以用以下代码创建：

int arr[] = {1, 2, 3, 4, 5, 6, 7};
int n = 7;
TreeNode* root = createBinaryTree(arr, n, 0);

用C++实现以下功能，建立一棵含有n个结点的二叉树，采用二叉链表存储； ⑵ 输出前序、中序、后序遍历该二叉树的遍历结果

以下是C++实现代码：

#include <iostream>
using namespace std;

// 二叉树结点结构体
struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

// 构建二叉树
Node* buildTree(int n) {
    if (n == 0) return nullptr;
    int rootVal;
    cin >> rootVal;   // 输入根节点的值
    Node* root = new Node(rootVal);
    root->left = buildTree(n/2);   // 递归构建左子树
    root->right = buildTree(n-n/2-1);   // 递归构建右子树
    return root;
}

// 前序遍历
void preOrder(Node* root) {
    if (!root) return;
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

// 中序遍历
void inOrder(Node* root) {
    if (!root) return;
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

// 后序遍历
void postOrder(Node* root) {
    if (!root) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << " ";
}

int main() {
    int n;
    cout << "请输入二叉树的结点个数：";
    cin >> n;
    cout << "请按照前序遍历的顺序输入结点的值：" << endl;
    Node* root = buildTree(n);
    cout << "前序遍历结果为：";
    preOrder(root);
    cout << endl << "中序遍历结果为：";
    inOrder(root);
    cout << endl << "后序遍历结果为：";
    postOrder(root);
    cout << endl;
    return 0;
}

这里采用递归的方式构建二叉树，每次读入根节点的值，然后递归构建左子树和右子树。前序、中序、后序遍历也采用递归的方式实现。