C++定义函数复制二叉树
时间: 2023-10-29 17:07:17 浏览: 40
以下是一个 C++ 函数,可以复制一个二叉树:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* copyTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
TreeNode* newRoot = new TreeNode(root->val);
newRoot->left = copyTree(root->left);
newRoot->right = copyTree(root->right);
return newRoot;
}
```
该函数使用递归方式复制二叉树。对于给定的二叉树根节点 `root`,首先创建一个新的节点 `newRoot`,并将其值设置为 `root` 节点的值。然后,递归地复制左子树和右子树,并将它们设置为 `newRoot` 的左子树和右子树。最后返回 `newRoot`,即为新复制的二叉树的根节点。
相关问题
用c/c++定义一个二叉树
可以使用如下的结构体定义二叉树:
```c
typedef struct node{
int value;
struct node *left;
struct node *right;
} Node;
```
其中 `value` 表示节点的值, `left` 和 `right` 分别表示左右子节点的指针。
创建一个二叉树时,可以使用如下的代码:
```c
Node* create_tree(int value,Node* left,Node* right){
Node* root=(Node*)malloc(sizeof(Node));
root->value=value;
root->left=left;
root->right=right;
return root;
}
```
这个函数接受三个参数:节点值、左子节点、右子节点,返回创建好的根节点指针。
例如,可以创建一个如下的二叉树:
```
1
/ \
2 3
/ \
4 5
```
通过以下代码:
```c
Node* leaf1=create_tree(2,NULL,NULL);
Node* leaf2=create_tree(4,NULL,NULL);
Node* leaf3=create_tree(5,NULL,NULL);
Node* node1=create_tree(3,leaf2,leaf3);
Node* root=create_tree(1,leaf1,node1);
```
这样就创建好了这个二叉树。
注意,在实际使用中应该考虑节点的内存管理等问题,这里只是为了展示用法。
c++排序二叉树打印函数
以下是C++中排序二叉树打印函数的实现:
```cpp
#include <iostream>
using namespace std;
// 定义二叉树节点结构体
struct Node {
int _key;
Node* _left;
Node* _right;
Node(int key) : _key(key), _left(nullptr), _right(nullptr) {}
};
// 定义排序二叉树类
class BST {
public:
BST() : _root(nullptr) {}
~BST() {}
// 插入节点
void Insert(int key) {
if (_root == nullptr) {
_root = new Node(key);
return;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur != nullptr) {
parent = cur;
if (key < cur->_key) {
cur = cur->_left;
} else if (key > cur->_key) {
cur = cur->_right;
} else {
return;
}
}
cur = new Node(key);
if (key < parent->_key) {
parent->_left = cur;
} else {
parent->_right = cur;
}
}
// 中序遍历打印
void InOrderPrint() {
_InOrder(_root);
cout << endl;
}
private:
Node* _root;
// 中序遍历
void _InOrder(Node* root) {
if (root == nullptr) {
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
};
// 测试
int main() {
BST bst;
bst.Insert(5);
bst.Insert(3);
bst.Insert(7);
bst.Insert(1);
bst.Insert(9);
bst.InOrderPrint(); // 输出:1 3 5 7 9
return 0;
}
```