1.统计二叉树的叶结点个数。2.判别两棵树是否相等。3.交换二叉树每个结点的左孩子和右孩子。4.设计二叉树的双序遍历算法。
时间: 2024-05-24 20:14:03 浏览: 16
好的,您的四个问题我都可以回答。请看下面的解释:
1. 统计二叉树的叶结点个数
答:统计二叉树的叶结点个数可以采用递归的方式。如果二叉树为空,则叶节点个数为0,如果二叉树不为空且左右子树均为空,则当前节点为叶节点,个数为1,否则叶节点个数等于左子树的叶节点个数加右子树的叶节点个数。
代码实现:
int CountLeaf(Node *root)
{
if(root == NULL)
return 0;
if(root->left == NULL && root->right == NULL)
return 1;
return CountLeaf(root->left) + CountLeaf(root->right);
}
2. 判别两棵树是否相等
答:判别两棵树是否相等也可以采用递归的方式。若两棵树均为空,则它们相等。如果两棵树都不为空,那么如果它们的根结点值相等,且左子树和右子树分别相等,则两棵树相等。
代码实现:
bool IsEqual(Node *root1, Node *root2)
{
if(root1 == NULL && root2 == NULL)
return true;
if(root1 != NULL && root2 != NULL)
{
if(root1->value == root2->value &&
IsEqual(root1->left, root2->left) &&
IsEqual(root1->right, root2->right))
return true;
}
return false;
}
3. 交换二叉树每个结点的左孩子和右孩子
答:交换二叉树每个结点的左孩子和右孩子同样可以采用递归的方式。如果当前节点不为空,则交换当前节点的左孩子和右孩子,然后递归处理左子树和右子树。
代码实现:
void Mirror(Node *root)
{
if(root == NULL)
return;
Node *temp = root->left;
root->left = root->right;
root->right = temp;
Mirror(root->left);
Mirror(root->right);
}
4. 设计二叉树的双序遍历算法
答:双序遍历算法可以同时遍历二叉树的前序序列和后序序列。在遍历前序序列的同时,记录当前节点在后序序列中的位置。对于每个节点,先输出其前序值,然后判断其左子树和右子树在后序序列中出现的位置关系,进而输出其后序值。具体实现过程如下:
void DoubleOrder(Node *root, int pre[], int post[], int &pre_index, int &post_index)
{
if(root == NULL)
return;
// 输出前序值
cout << root->value << " ";
pre[pre_index++] = root->value;
if(root->left != NULL)
DoubleOrder(root->left, pre, post, pre_index, post_index);
if(root->right != NULL)
DoubleOrder(root->right, pre, post, pre_index, post_index);
// 判断左右子树是否为空
if(root->left == NULL && root->right == NULL)
return;
// 输出后序值
while(post_index >= 0 && post[post_index] != root->left->value && post[post_index] != root->right->value)
cout << post[post_index--] << " ";
if(post[post_index] == root->left->value)
DoubleOrder(root->left, pre, post, pre_index, post_index);
if(post[post_index] == root->right->value)
DoubleOrder(root->right, pre, post, pre_index, post_index);
cout << root->value << " ";
}
其中,pre和post分别为前序序列和后序序列的数组,pre_index和post_index分别指向当前节点在前序序列和后序序列中的位置。在输出后序值时,需要根据当前节点的左右子树在后序序列中的位置来决定先输出哪个子树的后序值,这里可以采用一个while循环来处理。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)