【内部资料】二叉树的其它重要操作还有：建立一棵二叉树、插入一个结点到二叉树中、删除结点或子树等
除了“遍历”以外，二叉树的其它重要操作还有：建立一棵二叉树、插入一个结点到二叉树中、删除结点或子树等。下面用C++98语法实现 1、建立一棵二叉树 2、删除二叉树、3、插入一个结点到排序二叉树中 4、在排序二叉树中查找一个数，找到返回该结点,否则返回NULL 5．用嵌套括号表示法输出二叉树。
建立一棵二叉树：
#include <iostream>
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};
TreeNode* createBinaryTree(int data) {
return new TreeNode(data);
}删除二叉树：
void deleteBinaryTree(TreeNode* root) {
if (root) {
deleteBinaryTree(root->left);
deleteBinaryTree(root->right);
delete root;
}
}插入一个结点到排序二叉树中：
void insertNode(TreeNode*& root, int data) {
if (!root) {
root = new TreeNode(data);
return;
}
if (data < root->data) {
insertNode(root->left, data);
} else {
insertNode(root->right, data);
}
}在排序二叉树中查找一个数，找到返回该结点，否则返回NULL：
TreeNode* searchNode(TreeNode* root, int target) {
if (!root) {
return NULL;
}
if (root->data == target) {
return root;
} else if (target < root->data) {
return searchNode(root->left, target);
} else {
return searchNode(root->right, target);
}
}用嵌套括号表示法输出二叉树：
void printBinaryTree(TreeNode* root) {
if (root) {
std::cout << "(" << root->data;
if (root->left || root->right) {
std::cout << " ";
printBinaryTree(root->left);
if (root->right) {
std::cout << " ";
printBinaryTree(root->right);
}
}
std::cout << ")";
}
}使用这些函数可以创建、删除、插入、查找、输出二叉树。请注意，上述代码使用了C++98语法。
以下是一个完整的C++98示例程序，包含了主函数和示例代码：
#include <iostream>
// 定义二叉树节点结构
struct TreeNode {
int data; // 节点数据
TreeNode* left; // 左子树指针
TreeNode* right; // 右子树指针
// 构造函数
TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};
// 创建一棵二叉树，返回根节点指针
TreeNode* createBinaryTree(int data) {
return new TreeNode(data);
}
// 递归删除整棵二叉树
void deleteBinaryTree(TreeNode* root) {
if (root) {
deleteBinaryTree(root->left); // 递归删除左子树
deleteBinaryTree(root->right); // 递归删除右子树
delete root; // 删除当前节点
}
}
// 向排序二叉树中插入一个节点
void insertNode(TreeNode*& root, int data) {
if (!root) {
root = new TreeNode(data); // 创建新节点并将其设为根节点
return;
}
if (data < root->data) {
insertNode(root->left, data); // 递归插入到左子树
} else {
insertNode(root->right, data); // 递归插入到右子树
}
}
// 在排序二叉树中查找一个数，找到返回该节点指针，否则返回NULL
TreeNode* searchNode(TreeNode* root, int target) {
if (!root) {
return NULL; // 如果树为空，返回NULL
}
if (root->data == target) {
return root; // 如果当前节点的数据等于目标值，返回当前节点
} else if (target < root->data) {
return searchNode(root->left, target); // 在左子树中查找
} else {
return searchNode(root->right, target); // 在右子树中查找
}
}
// 使用嵌套括号表示法输出二叉树
void printBinaryTree(TreeNode* root) {
if (root) {
std::cout << "(" << root->data;
if (root->left || root->right) {
std::cout << " ";
printBinaryTree(root->left);
if (root->right) {
std::cout << " ";
printBinaryTree(root->right);
}
}
std::cout << ")";
}
}
int main() {
TreeNode* root = NULL;
// 创建二叉树
root = createBinaryTree(50);
insertNode(root, 30);
insertNode(root, 70);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 60);
insertNode(root, 80);
// 输出二叉树
std::cout << "Binary Tree: ";
printBinaryTree(root);
std::cout << std::endl;
// 在排序二叉树中查找结点
int target = 40;
TreeNode* foundNode = searchNode(root, target);
if (foundNode) {
std::cout << "Found " << target << " in the tree." << std::endl;
} else {
std::cout << target << " not found in the tree." << std::endl;
}
// 删除整棵二叉树
deleteBinaryTree(root);
return 0;
}![\"image.png\"/](\"/uploads/image/20231009/1696837597925405.png\" "\\"1696837597925405.png\\"")
代码示例中的printBinaryTree函数使用的是先序遍历的方式来输出二叉树。在先序遍历中，首先访问根节点，然后递归访问左子树，最后递归访问右子树。这会按照嵌套括号表示法输出二叉树的结构。
如果你希望使用其他遍历方式（如中序遍历或后序遍历），可以相应地修改代码来实现不同的输出顺序。
void insertNode(TreeNode*& root, int data) 为什么要用*& root 和用 * root 有什么区别
在C++中，*& 和 * 都涉及到指针的引用和指针的使用，但它们的含义不同：
*&表示指针的引用，即传递了指针的引用，允许函数修改调用方提供的指针的值。*表示指针，即传递了指针的副本，函数可以使用指针指向的对象，但不能修改调用方的指针本身。
在 void insertNode(TreeNode*& root, int data) 函数中使用 TreeNode*& root，是为了允许函数修改调用方提供的指针 root 的值。这样，当你在函数内部插入一个新节点时，root 指向新节点的父节点的指针会被更新，以反映新节点的插入。
如果你使用 TreeNode* root，那么只会传递指针的副本，函数内部的修改不会影响调用方提供的指针 root。
所以，使用 *& 允许函数对指针本身进行操作，而不仅仅是对指针指向的数据进行操作。这在需要在函数内部修改指针指向的位置时非常有用，比如在插入节点的情况下。
举例说明一下
当使用 *& 时，函数可以修改调用方提供的指针的值，这对于在函数内插入新节点非常有用。下面是一个示例，说明了使用 *& 的情况：
#include <iostream>
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};
// 使用 *& 插入节点
void insertNode(TreeNode*& root, int data) {
if (!root) {
root = new TreeNode(data); // 创建新节点并将其设为根节点
return;
}
if (data < root->data) {
insertNode(root->left, data); // 递归插入到左子树
} else {
insertNode(root->right, data); // 递归插入到右子树
}
}
int main() {
TreeNode* root = NULL;
// 初始状态下，根节点为 NULL
// 插入节点时，使用 *& 允许函数修改根节点的值
insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 70);
insertNode(root, 20);
insertNode(root, 40);
// 输出树的结构
std::cout << "Binary Tree: " << root->data << std::endl;
std::cout << " / \\\\" << std::endl;
std::cout << " " << root->left->data << " " << root->right->data << std::endl;
std::cout << " / /" << std::endl;
std::cout << " " << root->left->left->data << " " << root->right->left->data << std::endl;
// 注意，这里没有释放内存，为简化示例未包含删除二叉树的步骤
return 0;
}![\"image.png\"/](\"/uploads/image/20231009/1696837885162634.png\" "\\"1696837885162634.png\\"")
在上述示例中，insertNode 函数使用 *& 来插入节点，这使得函数能够修改 root 指针的值，以在树中插入新节点。在 main 函数中，你可以看到树的结构已经被成功构建。
调用方是指什么？
在编程中，"调用方" 是指调用函数的那部分代码或程序。当你调用一个函数时，你编写的代码就是调用方，而被调用的函数则是被调用方。
举例来说，在下面的代码片段中，main 函数是调用方，而 insertNode 函数是被调用方：
int main() {
TreeNode* root = NULL;
// 调用 insertNode 函数
insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 70);
insertNode(root, 20);
insertNode(root, 40);
// 其他代码...
return 0;
}
在这个例子中，main 函数调用了 insertNode 函数，因此 main 函数是调用方，而 insertNode 函数是被调用方。被调用方通常执行特定的任务或操作，并且可以接受调用方传递的参数以影响其行为。
