首页以二叉链表作为二叉树的存储结构，定义链表和二叉树，利用c语言编写以下算法： (1)统计二叉树的叶结点个数 (2)判断两棵二叉树是否相等 (3)交换二叉树每个结点的左孩子和右孩子 (4)按照层序遍历二叉树，统计树中度为1的结点个数

以二叉链表作为二叉树的存储结构，定义链表和二叉树，利用c语言编写以下算法： (1)统计二叉树的叶结点个数 (2)判断两棵二叉树是否相等 (3)交换二叉树每个结点的左孩子和右孩子 (4)按照层序遍历二叉树，统计树中度为1的结点个数

时间: 2023-10-18 08:04:16 浏览: 149

1. 统计二叉树的叶结点个数 ```c typedef struct BinaryTreeNode { int data; struct BinaryTreeNode *left; struct BinaryTreeNode *right; } BinaryTreeNode, *BinaryTree; int countLeafNodes(BinaryTree root) { if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL) { return 1; } return countLeafNodes(root->left) + countLeafNodes(root->right); } ``` 2. 判断两棵二叉树是否相等 ```c int isSameBinaryTree(BinaryTree root1, BinaryTree root2) { if (root1 == NULL && root2 == NULL) { return 1; } if (root1 == NULL || root2 == NULL) { return 0; } if (root1->data != root2->data) { return 0; } return isSameBinaryTree(root1->left, root2->left) && isSameBinaryTree(root1->right, root2->right); } ``` 3. 交换二叉树每个结点的左孩子和右孩子 ```c void swapChild(BinaryTree root) { if (root == NULL) { return; } BinaryTree temp = root->left; root->left = root->right; root->right = temp; swapChild(root->left); swapChild(root->right); } ``` 4. 按照层序遍历二叉树，统计树中度为1的结点个数 ```c int countDegree1Nodes(BinaryTree root) { if (root == NULL) { return 0; } int count = 0; Queue *queue = createQueue(); enqueue(queue, root); while (!isEmpty(queue)) { BinaryTree node = dequeue(queue); if ((node->left == NULL && node->right != NULL) || (node->left != NULL && node->right == NULL)) { count++; } if (node->left != NULL) { enqueue(queue, node->left); } if (node->right != NULL) { enqueue(queue, node->right); } } destroyQueue(queue); return count; } ```

阅读全文