完成对二叉树的以下操作:初始化二叉树,建立二叉树,销毁二叉树,计算二叉树的深度,计算二叉树的叶子结点总数,根据已有二叉树拷贝一颗新二叉树。
时间: 2023-11-14 21:12:10 浏览: 100
二叉树的相关操作,定义,初始化,几种遍历以及求深度和叶子数
5星 · 资源好评率100%
好的,我可以为您解答这些问题。以下是对二叉树的操作:
1. 初始化二叉树:
二叉树的初始化通常是将根节点指针置为NULL,表示当前二叉树为空树。
```c++
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* root = NULL; // 初始化二叉树
```
2. 建立二叉树:
我们可以通过递归的方式来建立二叉树。首先输入根节点的值,然后递归建立左右子树。
```c++
TreeNode* createTree() {
int val;
cin >> val;
if (val == -1) { // -1 代表该结点为空
return NULL;
}
TreeNode* node = new TreeNode(val);
node->left = createTree();
node->right = createTree();
return node;
}
root = createTree(); // 建立二叉树
```
3. 销毁二叉树:
二叉树的销毁通常也是通过递归的方式进行。我们先递归销毁左右子树,然后再释放当前节点的内存空间。
```c++
void destroyTree(TreeNode* node) {
if (node == NULL) {
return;
}
destroyTree(node->left);
destroyTree(node->right);
delete node;
}
destroyTree(root); // 销毁二叉树
```
4. 计算二叉树的深度:
二叉树的深度可以通过递归的方式计算。二叉树的深度等于左右子树深度的最大值加上1。
```c++
int getDepth(TreeNode* node) {
if (node == NULL) {
return 0;
}
int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
return max(leftDepth, rightDepth) + 1;
}
int depth = getDepth(root); // 计算二叉树的深度
```
5. 计算二叉树的叶子结点总数:
二叉树的叶子结点是指没有子节点的节点。我们可以通过递归的方式计算二叉树的叶子结点总数。如果当前节点是叶子节点,则返回1,否则返回左右子树叶子结点的个数之和。
```c++
int getLeafCount(TreeNode* node) {
if (node == NULL) {
return 0;
}
if (node->left == NULL && node->right == NULL) {
return 1;
}
return getLeafCount(node->left) + getLeafCount(node->right);
}
int leafCount = getLeafCount(root); // 计算二叉树的叶子结点总数
```
6. 根据已有二叉树拷贝一颗新二叉树:
我们可以通过递归的方式,先复制当前节点,然后递归复制左右子树。
```c++
TreeNode* cloneTree(TreeNode* node) {
if (node == NULL) {
return NULL;
}
TreeNode* newNode = new TreeNode(node->val);
newNode->left = cloneTree(node->left);
newNode->right = cloneTree(node->right);
return newNode;
}
TreeNode* newRoot = cloneTree(root); // 根据已有二叉树拷贝一颗新二叉树
```
以上就是对二叉树的初始化、建立、销毁、深度计算、叶子结点总数计算和拷贝的操作。希望可以帮助到您!
阅读全文