### 思路
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;
}