C++实现二叉树基础操作：插入、查找与删除

本资源是一份关于C语言实现二叉树基本操作的代码，主要包括插入、查找和删除节点的功能。首先，我们来看一下关键的部分： 1. **二叉树定义**: `TreeNode` 结构体定义了一个包含整数值`val`的二叉树节点，以及指向左右子节点的指针`left`和`right`。构造函数`TreeNode(int x)`用于初始化一个值为`x`的新节点，其中`nullptr`表示默认没有子节点。 2. **插入节点（Insertion）**: `insertNode(TreeNode* root, int val)`函数实现了向二叉搜索树中插入一个新节点的过程。如果根节点为空，就创建一个新的节点并返回；否则，根据新值与当前根节点值的大小关系，递归地将新值插入到左子树或右子树中。 3. **查找节点（Search）**: `findNode(TreeNode* root, int val)`函数用于在已有的二叉树中查找指定值的节点。它通过比较目标值与当前节点值，如果相等或当前节点为空，则返回该节点；否则，继续在相应子树中递归查找。 4. **删除节点（Deletion）**: `deleteNode(TreeNode* root, int val)`是删除具有指定值的节点的函数。首先检查根节点是否为空，然后依据删除节点的值与根节点值的关系，进行三种情况的处理： - 如果要删除的值小于根节点，递归删除左子树。 - 如果要删除的值大于根节点，递归删除右子树。 - 如果找到要删除的节点，根据其是否有子节点来区分： - 如果只有一个子节点，将其替换为另一个子节点，并删除原节点。 - 如果有两个子节点，找到右子树中的最小值节点（即右子树的最大节点），替换当前节点，然后删除找到的最小值节点。 这些代码展示了如何用C语言实现二叉树的常见操作，包括建立、搜索和调整数据结构以保持二叉搜索树的性质。它们对于理解二叉树的数据结构以及在实际编程中应用非常重要。理解这些操作有助于开发其他复杂的算法和数据结构，如排序、查找、遍历等。同时，这也有助于在面试或项目中展示对基础数据结构的扎实掌握。