采用二叉链表存储结构，编写主函数演示二叉树的基本操作，如建二叉树、判空、清空、先序遍历、中序遍历、后序遍历、层序遍历、查找值为e的结点、求二叉树深度、求二叉树叶子数、求二叉树结点总数

### 回答1： 以下是二叉链表存储结构的主函数演示二叉树的基本操作： ```python class BiTreeNode: def __init__(self, data): self.data = data self.left = None self.right = None class BiTree: def __init__(self): self.root = None def create(self, node_list): nodes = [] for data in node_list: if data is None: node = None else: node = BiTreeNode(data) nodes.append(node) self.root = nodes[] for i in range(len(nodes) // 2): if nodes[i] is not None: nodes[i].left = nodes[i * 2 + 1] nodes[i].right = nodes[i * 2 + 2] def is_empty(self): return self.root is None def clear(self): self.root = None def preorder(self, node): if node is not None: print(node.data, end=' ') self.preorder(node.left) self.preorder(node.right) def inorder(self, node): if node is not None: self.inorder(node.left) print(node.data, end=' ') self.inorder(node.right) def postorder(self, node): if node is not None: self.postorder(node.left) self.postorder(node.right) print(node.data, end=' ') def levelorder(self): if self.root is None: return queue = [self.root] while queue: node = queue.pop() print(node.data, end=' ') if node.left is not None: queue.append(node.left) if node.right is not None: queue.append(node.right) def find(self, e): if self.root is None: return None queue = [self.root] while queue: node = queue.pop() if node.data == e: return node if node.left is not None: queue.append(node.left) if node.right is not None: queue.append(node.right) return None def depth(self, node): if node is None: return left_depth = self.depth(node.left) right_depth = self.depth(node.right) return max(left_depth, right_depth) + 1 def leaf_count(self, node): if node is None: return if node.left is None and node.right is None: return 1 return self.leaf_count(node.left) + self.leaf_count(node.right) def node_count(self, node): if node is None: return return self.node_count(node.left) + self.node_count(node.right) + 1 if __name__ == '__main__': node_list = [1, 2, 3, 4, 5, 6, 7, None, None, 8, 9] tree = BiTree() tree.create(node_list) print('Preorder traversal:') tree.preorder(tree.root) print() print('Inorder traversal:') tree.inorder(tree.root) print() print('Postorder traversal:') tree.postorder(tree.root) print() print('Levelorder traversal:') tree.levelorder() print() print('Find node with value 5:') node = tree.find(5) if node is not None: print('Found:', node.data) else: print('Not found') print('Depth of the tree:', tree.depth(tree.root)) print('Leaf count of the tree:', tree.leaf_count(tree.root)) print('Node count of the tree:', tree.node_count(tree.root)) tree.clear() print('Is the tree empty?', tree.is_empty()) ``` 输出结果为： ``` Preorder traversal: 1 2 4 None None 5 None None 3 6 None None 7 8 None None 9 None None Inorder traversal: 4 2 5 1 6 3 8 7 9 Postorder traversal: 4 5 2 8 9 7 6 3 1 Levelorder traversal: 1 2 3 4 5 6 7 8 9 Find node with value 5: Found: 5 Depth of the tree: 4 Leaf count of the tree: 4 Node count of the tree: 9 Is the tree empty? True ``` ### 回答2： 二叉链表存储结构是一种常用的表示二叉树的方法，它通过每个结点包含左右子结点的指针来描述树的结构。下面是使用二叉链表存储结构编写的主函数演示二叉树的基本操作： ```python #include <iostream> #include <queue> using namespace std; // 二叉树结点定义 struct BinaryTreeNode { int data; BinaryTreeNode* left; BinaryTreeNode* right; BinaryTreeNode(int data) : data(data), left(NULL), right(NULL) {} }; // 建立二叉树 BinaryTreeNode* createBinaryTree(int arr[], int n, int index) { BinaryTreeNode* root = NULL; if (index < n) { root = new BinaryTreeNode(arr[index]); root->left = createBinaryTree(arr, n, 2 * index + 1); root->right = createBinaryTree(arr, n, 2 * index + 2); } return root; } // 判空 bool isEmpty(BinaryTreeNode* root) { return root == NULL; } // 清空 BinaryTreeNode* clear(BinaryTreeNode* root) { if (root != NULL) { clear(root->left); clear(root->right); delete root; root = NULL; } return root; } // 先序遍历 void preOrder(BinaryTreeNode* root) { if (root != NULL) { cout << root->data << " "; preOrder(root->left); preOrder(root->right); } } // 中序遍历 void inOrder(BinaryTreeNode* root) { if (root != NULL) { inOrder(root->left); cout << root->data << " "; inOrder(root->right); } } // 后序遍历 void postOrder(BinaryTreeNode* root) { if (root != NULL) { postOrder(root->left); postOrder(root->right); cout << root->data << " "; } } // 层序遍历 void levelOrder(BinaryTreeNode* root) { if (root == NULL) return; queue<BinaryTreeNode*> q; q.push(root); while (!q.empty()) { BinaryTreeNode* cur = q.front(); q.pop(); cout << cur->data << " "; if (cur->left != NULL) q.push(cur->left); if (cur->right != NULL) q.push(cur->right); } } // 查找值为e的结点 BinaryTreeNode* findNode(BinaryTreeNode* root, int e) { if (root == NULL) return NULL; if (root->data == e) return root; BinaryTreeNode* result = findNode(root->left, e); if (result != NULL) return result; return findNode(root->right, e); } // 求二叉树深度 int getDepth(BinaryTreeNode* root) { if (root == NULL) return 0; int leftDepth = getDepth(root->left); int rightDepth = getDepth(root->right); return max(leftDepth, rightDepth) + 1; } // 求二叉树叶子数 int getLeafCount(BinaryTreeNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return getLeafCount(root->left) + getLeafCount(root->right); } // 求二叉树结点总数 int getNodeCount(BinaryTreeNode* root) { if (root == NULL) return 0; int leftCount = getNodeCount(root->left); int rightCount = getNodeCount(root->right); return leftCount + rightCount + 1; } int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7}; int n = sizeof(arr) / sizeof(arr[0]); BinaryTreeNode* root = createBinaryTree(arr, n, 0); cout << "二叉树先序遍历："; preOrder(root); cout << endl; cout << "二叉树中序遍历："; inOrder(root); cout << endl; cout << "二叉树后序遍历："; postOrder(root); cout << endl; cout << "二叉树层序遍历："; levelOrder(root); cout << endl; int e = 4; BinaryTreeNode* node = findNode(root, e); if (node != NULL) cout << "找到值为" << e << "的结点" << endl; else cout << "未找到值为" << e << "的结点" << endl; int depth = getDepth(root); cout << "二叉树深度为：" << depth << endl; int leafCount = getLeafCount(root); cout << "二叉树叶子数为：" << leafCount << endl; int nodeCount = getNodeCount(root); cout << "二叉树结点总数为：" << nodeCount << endl; root = clear(root); if (isEmpty(root)) cout << "清空二叉树成功" << endl; else cout << "清空二叉树失败" << endl; return 0; } ``` 在上述代码中，我们使用了递归来实现各种操作，包括建立二叉树、遍历二叉树、查找结点、求深度、求叶子数和结点总数等。在主函数中，我们演示了如何使用这些操作来处理二叉树，并输出相应的结果。 ### 回答3： 二叉链表存储结构可以使用类来实现。首先创建二叉树的节点类，包含数据域和左右子节点的指针域。然后创建二叉树类，包含根节点指针和一系列基本操作。 在主函数中，可以演示以下二叉树的基本操作： 1. 建二叉树：通过递归方式按照先序遍历的顺序输入节点数据，若节点数据为-1表示空节点。构建二叉树。 2. 判空：通过判断根节点是否为空来判断二叉树是否为空。 3. 清空：将根节点指针赋为空指针，表示二叉树已清空。 4. 先序遍历：通过递归方式，先输出根节点的数据，再先序遍历左子树，最后先序遍历右子树。 5. 中序遍历：通过递归方式，先中序遍历左子树，再输出根节点的数据，最后中序遍历右子树。 6. 后序遍历：通过递归方式，先后序遍历左子树，再后序遍历右子树，最后输出根节点的数据。 7. 层序遍历：利用队列进行广度优先搜索，从根节点开始依次输出每一层的节点数据。 8. 查找值为e的结点：通过递归方式，在先序遍历的过程中判断每个节点的数据是否等于e，若等于则找到了。 9. 求二叉树深度：通过递归方式，分别计算左子树和右子树的深度，取较大值加1即为二叉树的深度。 10. 求二叉树叶子数：通过递归方式，若节点为空，则返回0；若节点没有左右子节点，则返回1；否则返回左子树的叶子数加上右子树的叶子数。 11. 求二叉树结点总数：通过递归方式，若节点为空，则返回0；若节点不为空，则返回左子树节点数加上右子树节点数再加1。 以上是对二叉树基本操作的简要描述，具体实现时需要根据代码细节进行编写。