C++树的数据结构实现代码 |21xrx.com

C++树的数据结构实现代码

2023-06-28 13:22:10 深夜i -- --

C++ 树数据结构实现代码

C++中的树数据结构是一种非常重要的数据结构，用于模拟现实世界中的许多环境和应用程序。树数据结构被广泛应用于操作系统、编译器、数据库、图形系统和网络协议等领域。在本文中，我们将介绍C++树数据结构的实现代码。

在C++中，树是一种数据结构，其中每个节点都有零个或多个子节点。树的最上层节点称为根节点。每个子节点都只有一个父节点。树的结构使得它非常适合作为组织和嵌套数据的方式。在C++中，可以使用不同的数据结构来实现树。

首先，让我们考虑使用C++结构体(struct)来实现树。树的结构体定义如下：


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

在这里，我们定义了一个TreeNode结构体，该结构体包含整数类型的值val和指向左、右子结点的指针left和right。这个结构体还定义了一个构造函数，该构造函数接受一个整数参数并初始化它的值val和左、右子结点为空。

使用该结构体定义变量即可创建一棵树。例如：


TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);

这表示我们创建了一棵根节点为1、左子结点为2、右子结点为3的树。

除了使用结构体之外，我们还可以使用指针来实现树数据结构。在这种情况下，我们使用一个指向节点的指针和一个指向其子节点的指针来表示节点。这些指针的值可以为NULL，表示没有子树。

下面是使用指针实现的树：


class TreeNode {
public:
 int val;
 TreeNode* left;
 TreeNode* right;
 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Tree {
public:
 TreeNode* root;
 Tree() root = NULL;
 void insert(int val) {
  TreeNode* node = new TreeNode(val);
  if (root == NULL)
   root = node;
   return;
  
  TreeNode* parent = root;
  TreeNode* current = root;
  while (current != NULL) {
   parent = current;
   if (val < current->val)
    current = current->left;
    else
    current = current->right;
   
  }
  if (val < parent->val)
   parent->left = node;
   else
   parent->right = node;
  
 }
 void inorder(TreeNode* node) {
  if (node == NULL)
   return;
  
  inorder(node->left);
  cout << node->val << " ";
  inorder(node->right);
 }
};
int main() {
 Tree t;
 t.insert(3);
 t.insert(2);
 t.insert(1);
 t.insert(4);
 t.insert(5);
 t.inorder(t.root);
 return 0;
}

在这个代码中，我们定义了一个TreeNode类和一个Tree类。TreeNode类表示一个节点，包括一个值val和指向左右子节点的指针left和right。Tree类表示一棵树，包括一个指向根节点的指针root，并实现了插入和遍历(inorder)方法。

以上是一些常见的C++树数据结构的实现代码，我们可以根据具体的应用场景，选择合适的数据结构来实现自己的树。

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

下一篇: C++工程种类

评论区

()

相似文章