C++学习笔记——用C++实现树（区别于C）

树是一种非常重要的数据结构，它在计算机科学中的应用非常广泛。在本篇博客中，我们将介绍树的基本概念和C++中如何实现树。

目录

一、树的基本概念

2.C++中实现树

2.1创建一个树的实例，并向其添加节点

2.2三种遍历方式的实现代码

3.与C语言相比

3.1C++与C语言的一些不同之处

面向对象编程

标准库

异常处理

模板

命名空间

引用类型

类型安全性

强制类型转换

3.2一个简单的示例代码

C语言代码

C++代码

---

上一篇文章：

包含六大组件，它们分别是：

容器（Containers）：提供了数据存储的功能。有vector、list、map等常用容器。

算法（Algorithms）：提供了大量的算法，包括排序、查找、拷贝、合并等。有sort、find、copy、merge等常用算法。

迭代器（Iterators）：提供了一种访问容器元素的方式，可以对容器进行遍历。有输入迭代器、输出迭代器、正向迭代器、双向迭代器、随机访问迭代器等类型。

函数对象（Function Objects）：封装了一个函数或者函数指针，可以像使用函数一样使用它。有unary_function、binary_function等类型。

适配器（Adapters）：将一种容器或者迭代器转换为另一种容器或者迭代器。有stack、queue、priority_queue、reverse_iterator等类型。

分配器（Allocators）：管理内存分配和释放，可以自定义分配器来满足特定需求。有allocator等类型。

C++学习笔记——SLT六大组件及头文件-CSDN博客文章浏览阅读162次，点赞4次，收藏6次。GNU通用公共许可证（GNU General Public License，GPL）：GPL是GNU项目下的主要许可证，它保护了软件的自由性，确保用户在任何使用、修改和分发软件时都能保持相同的自由。自由软件（Free Software）：根据GNU的定义，自由软件是指用户可以自由地运行、复制、分发、研究、修改和改进的软件。GNU源代码开发精神的目标是让用户能够控制和定制自己使用的软件，避免对专有软件的依赖和束缚。算法（Algorithms）：提供了大量的算法，包括排序、查找、拷贝、合并等。https://blog.csdn.net/m0_62338174/article/details/135581450?spm=1001.2014.3001.5501

一、树的基本概念

在计算机科学中，树是一种非常重要的数据结构，它由一组节点和连接这些节点的边组成。树的一个节点称为根节点，它没有父节点；除了根节点外，每个节点都有且只有一个父节点。同时，每个节点可以有任意多个子节点。如果一个节点没有子节点，则称为叶子节点。

树具有以下特点：

• 每个节点最多只有一个父节点。
• 每个节点可以有任意多个子节点。
• 每个节点都有唯一的路径从根节点到达。
• 除了根节点外，每个节点都有唯一的路径到达。

由于树的这些特点，它被广泛应用于各种场景，例如文件系统、网站导航、数据结构中的二叉树等。

2.C++中实现树

在C++中，我们可以使用类来表示树。树的每个节点可以使用一个包含指向其父节点和子节点的指针的结构体或类来表示。下面是一个示例代码：

class Node {
public:int data; // 节点存储的数据Node* parent; // 指向父节点的指针std::vector<Node*> children; // 子节点的指针数组Node(int data) {this->data = data;this->parent = nullptr;this->children = std::vector<Node*>();}
};

在上面的代码中，我们定义了一个名为Node的类，它具有以下成员变量：

• data：节点存储的数据。
• parent：指向父节点的指针。如果当前节点是根节点，则该指针为nullptr。
• children：子节点的指针数组。

2.1创建一个树的实例，并向其添加节点

下面是一个示例代码：

int main() {// 创建根节点Node* root = new Node(1);// 添加子节点Node* node2 = new Node(2);root->children.push_back(node2);node2->parent = root;Node* node3 = new Node(3);root->children.push_back(node3);node3->parent = root;Node* node4 = new Node(4);node2->children.push_back(node4);node4->parent = node2;// 遍历树std::cout << "Preorder Traversal: ";preorder(root);std::cout << std::endl;std::cout << "Postorder Traversal: ";postorder(root);std::cout << std::endl;std::cout << "Inorder Traversal: ";inorder(root);std::cout << std::endl;return 0;
}

在上述代码中，我们首先创建了一个根节点，并向其添加了三个子节点，其中node2和node3是根节点的直接子节点，而node4是node2的子节点。然后，我们使用三种不同的方式遍历树：前序遍历、后序遍历和中序遍历。

2.2三种遍历方式的实现代码

• // 前序遍历
  void preorder(Node* node) {if (node == nullptr) return;std::cout << node->data << " ";for (Node* child : node->children) {preorder(child);}
  }// 后序遍历
  void postorder(Node* node) {if (node == nullptr) return;for (Node* child : node->children) {postorder(child);}std::cout << node->data << " ";
  }// 中序遍历
  void inorder(Node* node) {if (node == nullptr) return;if (node->children.size() >= 1) {inorder(node->children[0]);}std::cout << node->data << " ";for (int i = 1; i < node->children.size(); i++) {inorder(node->children[i]);}
  }
  

在上述代码中，我们使用递归方式遍历树的所有节点，并将它们的值输出到控制台上。

树是一种非常重要的数据结构，它在计算机科学中应用非常广泛。在C++中，我们可以使用类来表示树，并通过递归遍历方式来访问树的所有节点。

3.与C语言相比

C++是一种更加现代化和功能强大的编程语言，它在C语言的基础上进行了扩展和改进。以下是

3.1C++与C语言的一些不同之处

面向对象编程

C++支持面向对象编程（OOP），可以使用类、对象、继承、多态等概念来组织和管理代码。而C语言是过程式编程语言，没有内置的面向对象特性。

标准库

C++提供了丰富的标准库，例如容器（如vector、list、map）、算法（如排序、查找）、字符串处理、输入输出等。这些库提供了许多高级和方便的功能，可以加速开发过程。C语言的标准库相对较小，功能相对有限。

异常处理

C++引入了异常处理机制，可以在程序中捕获和处理异常情况，从而增加代码的健壮性和可靠性。C语言没有内置的异常处理机制。

模板

C++支持泛型编程，通过模板可以实现通用的数据结构和算法。模板可以在编译时进行类型检查和实例化，使得代码更加灵活和可重用。C语言没有模板这样的特性。

命名空间

C++引入了命名空间的概念，可以将代码组织为不同的命名空间，避免命名冲突和重复。C语言没有命名空间的概念。

引用类型

C++引入了引用类型，可以创建引用变量，它们相当于别名，可以方便地操作和修改变量的值。C语言没有引用类型。

类型安全性

C++在类型检查方面更为严格，通过静态类型检查来捕获潜在的类型错误，减少运行时错误的可能性。C语言对类型的检查较为宽松。

强制类型转换

C++提供了四种强制类型转换运算符（static_cast、dynamic_cast、reinterpret_cast、const_cast），可以在类型之间进行显式的转换。C语言只有隐式和显式的类型转换。

需要注意的是，尽管C++具有上述扩展和改进，但它仍然兼容C语言的语法和大部分特性，可以直接使用C代码，并且C++代码也可以通过使用extern "C"来与C代码进行互操作。

3.2一个简单的示例代码

展示了C语言和C++语言之间的一些不同之处：

C语言代码

#include <stdio.h>// 函数原型可以省略参数列表
int add();int main() {printf("%d\n", add(3, 5)); // 在函数调用时不进行参数类型检查return 0;
}// 函数定义需要在函数原型之后
int add(int a, int b) {return a + b;
}

C++代码

#include <iostream>// 函数原型必须包含参数列表
int add(int a, int b); int main() {std::cout << add(3, 5) << std::endl; // 在函数调用时要求参数类型匹配return 0;
}// 函数定义可以在函数原型之前或之后
int add(int a, int b) {return a + b;
}

在上述代码中，可以看到以下不同之处：

1. C语言中的头文件使用#include <stdio.h>，而C++中的头文件使用#include <iostream>。

2. C语言中的函数原型可以省略参数列表，而C++中的函数原型必须包含参数列表。

3. 在C语言中，函数的定义可以在函数原型之前或之后，而在C++中，函数的定义可以在函数原型之前或之后。

4. C语言使用printf函数来输出结果，而C++使用std::cout对象和<<操作符进行输出。

5. 在C语言中，函数调用时不进行参数类型检查，而在C++中要求函数调用时参数类型要匹配。

这些是C语言和C++语言之间的一些基本区别，其中还有更多的差异，包括面向对象编程、异常处理、命名空间等特性。