### 思路
1. **插入新结点**：在二叉排序树中插入新结点。
2. **遍历二叉树**：实现前序、中序、后序遍历。
3. **中序遍历的非递归算法**：使用栈实现中序遍历。
4. **层次遍历二叉树**：使用队列实现层次遍历。
5. **查找给定关键字**：在二叉树中查找指定关键字。
6. **交换各结点的左右子树**：递归交换每个结点的左右子树。
7. **求二叉树的深度**：递归计算二叉树的深度。
8. **叶子结点数**：递归计算叶子结点的数量。
### 伪代码
1. **插入新结点**
```
function insert(root, key):
if root is null:
return new Node(key)
if key < root.value:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
```
2. **前序遍历**
```
function preorder(root):
if root is not null:
print(root.value)
preorder(root.left)
preorder(root.right)
```
3. **中序遍历**
```
function inorder(root):
if root is not null:
inorder(root.left)
print(root.value)
inorder(root.right)
```
4. **后序遍历**
```
function postorder(root):
if root is not null:
postorder(root.left)
postorder(root.right)
print(root.value)
```
5. **中序遍历的非递归算法**
```
function inorder_non_recursive(root):
stack = empty stack
current = root
while current is not null or stack is not empty:
while current is not null:
stack.push(current)
current = current.left
current = stack.pop()
print(current.value)
current = current.right
```
6. **层次遍历**
```
function level_order(root):
queue = empty queue
queue.enqueue(root)
while queue is not empty:
node = queue.dequeue()
print(node.value)
if node.left is not null:
queue.enqueue(node.left)
if node.right is not null:
queue.enqueue(node.right)
```
7. **查找给定关键字**
```
function search(root, key):
if root is null:
return 0
if root.value == key:
return 1
if key < root.value:
return search(root.left, key)
else:
return search(root.right, key)
```
8. **交换各结点的左右子树**
```
function swap_children(root):
if root is not null:
swap(root.left, root.right)
swap_children(root.left)
swap_children(root.right)
```
9. **求二叉树的深度**
```
function depth(root):
if root is null:
return 0
return 1 + max(depth(root.left), depth(root.right))
```
10. **叶子结点数**
```
function leaf_count(root):
if root is null:
return 0
if root.left is null and root.right is null:
return 1
return leaf_count(root.left) + leaf_count(root.right)
```
### C++代码
#include <iostream>
#include <queue>
#include <stack>
using namespace std;struct Node {int value;Node* left;Node* right;Node(int val) : value(val), left(nullptr), right(nullptr) {}
};Node* insert(Node* root, int key) {if (root == nullptr) return new Node(key);if (key < root->value) root->left = insert(root->left, key);else root->right = insert(root->right, key);return root;
}void preorder(Node* root) {if (root != nullptr) {cout << root->value << " ";preorder(root->left);preorder(root->right);}
}void inorder(Node* root) {if (root != nullptr) {inorder(root->left);cout << root->value << " ";inorder(root->right);}
}void postorder(Node* root) {if (root != nullptr) {postorder(root->left);postorder(root->right);cout << root->value << " ";}
}void inorder_non_recursive(Node* root) {stack<Node*> s;Node* current = root;while (current != nullptr || !s.empty()) {while (current != nullptr) {s.push(current);current = current->left;}current = s.top();s.pop();cout << current->value << " ";current = current->right;}
}void level_order(Node* root) {if (root == nullptr) return;queue<Node*> q;q.push(root);while (!q.empty()) {Node* node = q.front();q.pop();cout << node->value << " ";if (node->left != nullptr) q.push(node->left);if (node->right != nullptr) q.push(node->right);}
}int search(Node* root, int key) {if (root == nullptr) return 0;if (root->value == key) return 1;if (key < root->value) return search(root->left, key);else return search(root->right, key);
}void swap_children(Node* root) {if (root != nullptr) {swap(root->left, root->right);swap_children(root->left);swap_children(root->right);}
}int depth(Node* root) {if (root == nullptr) return 0;return 1 + max(depth(root->left), depth(root->right));
}int leaf_count(Node* root) {if (root == nullptr) return 0;if (root->left == nullptr && root->right == nullptr) return 1;return leaf_count(root->left) + leaf_count(root->right);
}int main() {int n;cin >> n;Node* root = nullptr;for (int i = 0; i < n; ++i) {int value;cin >> value;root = insert(root, value);}int key1, key2, insert_key;cin >> key1 >> key2 >> insert_key;preorder(root);cout << endl;inorder(root);cout << endl;postorder(root);cout << endl;cout << search(root, key1) << endl;cout << search(root, key2) << endl;root = insert(root, insert_key);preorder(root);cout << endl;inorder(root);cout << endl;postorder(root);cout << endl;inorder_non_recursive(root);cout << endl;level_order(root);cout << endl;swap_children(root);preorder(root);cout << endl;inorder(root);cout << endl;postorder(root);cout << endl;swap_children(root);preorder(root);cout << endl;inorder(root);cout << endl;postorder(root);cout << endl;cout << depth(root) << endl;cout << leaf_count(root) << endl;return 0;
}
