21xrx.com
2025-03-30 01:29:22 Sunday
文章检索 我的文章 写文章
如何使用C++创建一颗二叉树
2023-07-05 09:09:19 深夜i     48     0
C++ 二叉树 创建 节点 指针

二叉树是一种数据结构，它由节点组成，每个节点最多只有两个孩子节点。二叉树的使用广泛，例如在排序、搜索、解析等问题中都有很好的应用。本文将探讨如何使用C++创建一颗二叉树。

首先，我们需要定义二叉树节点的结构。一个二叉树节点通常包含一个数据域和两个指针域，用于指向该节点的左右子节点。可以使用下面的代码来定义二叉树节点：

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

接下来，我们需要编写一个函数，用于创建二叉树。该函数需要按照二叉树的定义来递归创建两个子树。可以使用下面的代码来创建二叉树：

TreeNode* createTree() {
  int val;
  cin >> val;
  if (val == -1)
    return NULL;
  
  TreeNode *node = new TreeNode(val);
  node->left = createTree();
  node->right = createTree();
  return node;
}

在上面的代码中，-1 表示该节点不存在，所以当输入 -1 时，返回 NULL。

现在我们已经完成了二叉树的创建。接下来，我们需要实现一个遍历二叉树的函数。二叉树的遍历方式有三种：前序遍历、中序遍历和后序遍历。下面的代码实现了前序遍历：

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

在上面的代码中，我们先输出当前节点的值，然后递归遍历左子树和右子树。

下面的代码实现了中序遍历：

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

在上面的代码中，我们先递归遍历左子树，然后输出当前节点的值，最后递归遍历右子树。

下面的代码实现了后序遍历：

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

在上面的代码中，我们先递归遍历左子树和右子树，最后输出当前节点的值。

使用上面的函数，我们可以很方便地遍历一颗二叉树。

综上所述，我们使用 C++ 创建一颗二叉树，需要定义二叉树节点的结构，编写一个递归函数创建二叉树，以及实现三种遍历方式的函数。在实际使用中，我们可以根据实际情况来选择适当的遍历方式。

  
  

评论区

请求出错了