C++中如何定义二叉树 |21xrx.com

C++中如何定义二叉树

2023-07-11 15:43:22 深夜i -- --

C++ 二叉树定义

二叉树是一种重要的数据结构，广泛应用于算法、数据处理和问题求解等领域。在C++中，我们可以使用结构体定义二叉树，也可以使用类定义二叉树。下面分别介绍两种方式。

一、使用结构体定义二叉树

我们需要定义一个二叉树节点的结构体，包含数据域、左子树指针和右子树指针。


struct TreeNode
{
  int data;
  TreeNode* left;
  TreeNode* right;
};

接着，我们可以使用递归方法定义二叉树。例如，以下代码定义了一个简单的二叉树。


TreeNode* createTree()
{
  TreeNode* root = new TreeNode;
  root->data = 1;
  root->left = new TreeNode;
  root->left->data = 2;
  root->left->left = NULL;
  root->left->right = NULL;
  root->right = new TreeNode;
  root->right->data = 3;
  root->right->left = NULL;
  root->right->right = NULL;
  return root;
}

这个二叉树的结构如下：

1 / \ 2 3

二、使用类定义二叉树

我们可以定义一个类，将二叉树的节点、根节点和各种操作封装在类里。


class BinaryTree
{
private:
  struct TreeNode
  {
    int data;
    TreeNode* left;
    TreeNode* right;
  };
  TreeNode* root;
  
  TreeNode* createTreeHelper(vector<int>& nums, int start, int end)
  {
    if(start > end)
    
      return NULL;
    
    int mid = (start + end) / 2;
    TreeNode* node = new TreeNode;
    node->data = nums[mid];
    node->left = createTreeHelper(nums, start, mid-1);
    node->right = createTreeHelper(nums, mid+1, end);
    return node;
  }
  
public:
  BinaryTree()
  
    root = NULL;
  
  
  void createTree(vector<int>& nums)
  {
    root = createTreeHelper(nums, 0, nums.size()-1);
  }
  
  bool isEmpty()
  {
    return (root == NULL);
  }
  
  void printInOrder(TreeNode* node)
  {
    if(node != NULL)
    {
      printInOrder(node->left);
      cout << node->data << " ";
      printInOrder(node->right);
    }
  }
};

在这个类中，我们使用“递归”的方法创建二叉树；通过`printInOrder`函数实现二叉树的中序遍历。

总结

以上就是使用C++定义二叉树的两种方法。通过使用结构体和类，我们可以方便地操作二叉树。如果你正在学习数据结构和算法，建议多多练习二叉树的实现。

上一篇: idea打包java可执行jar包

下一篇: 使用C++编写一个圣诞树程序

评论区

()

相似文章